true serializability and predicate locking

I have a question regarding true serializability and predicate locking.
There's some context on the wiki page:

http://wiki.postgresql.org/wiki/Serializable

under the heading "Predicate Locking".

If you have the following DDL:

create table mytable(mycircle circle);
create index mytable_mycircle_idx on mytable
using gist (mycircle);

and two transactions:

T1:
BEGIN;
SELECT * FROM mytable WHERE mycircle && '<(0, 0), 10>';
-- if any rows are returned, ROLLBACK
INSERT INTO mytable(mycircle) VALUES('<(0, 0), 10>');
COMMIT;

T2:
BEGIN;
SELECT * FROM mytable WHERE mycircle && '<(5, 5), 5>';
-- if any rows are returned, ROLLBACK
INSERT INTO mytable(mycircle) VALUES('<(5, 5), 5>');
COMMIT;

Clearly one of those transactions should abort, because that will happen
in either serialized order. But I don't see where any lock is stored,
nor how the conflict is detected.

There has been a lot of theoretical discussion on this matter, but I'd
like to know how it will work in this specific case. You can't merely
lock a few index pages, because the INSERT might put the tuple in
another page.

I'm still trying to catch up on this discussion as well as relevant
papers, but this question has been on my mind.

One approach that might work for GiST is to get some kind of lock
(SIREAD?) on the predicates for the pages that the search does not
match. That way, the conflict can be detected if an INSERT tries to
update the predicate of a page to something that the search may have
matched.

If the index was GIN instead of GiST, I think the fastupdate feature
would cause a problem, though (as Greg brought up). Fastupdate may need
to be disabled when using truly serializable transactions.

Regards,
Jeff Davis