Looking for workaround to avoid deadlock when using exclusion constraint

Hi,

Following code demonstrates an attempt to circumvent an unexpected
deadlock (cf. BUG #15026) when using exclusion constraints.

CREATE TABLE locked
(
key text NOT NULL,
EXCLUDE USING gist (key WITH =)
);

DO $$
DECLARE
id locked.key%TYPE;
BEGIN
WHILE id IS NULL
LOOP
BEGIN
SELECT key FROM locked WHERE key = 'a' INTO STRICT id;
EXCEPTION
WHEN no_data_found THEN
BEGIN
INSERT INTO locked(key) values('a') RETURNING key INTO id;
EXCEPTION
WHEN deadlock_detected THEN
RAISE WARNING 'Deadlock!! (t=%)', clock_timestamp();
END;
END;
END LOOP;
END;
$$;

This (imperfect) code works fine when two sesions compete for the record,
but will NEVER finish if three sessions compete!

To demonstrate this, first run following code from a 4th psql session:

DROP TABLE IF EXISTS locked;
CREATE TABLE locked
(
key text NOT NULL,
EXCLUDE USING gist (key WITH =)
);
BEGIN;
INSERT INTO locked(key) values('a');

Then run the DO block above from three sessions. They will wait on a
(share) lock as expected.
Now performing a ROLLBACK in the 4th session, results in a never ending
sequence of dead-lock exceptions plus retries in the other sessions.

Only "solution" I can think of is to introduce an exclusive lock on some
other entity just before doing the INSERT.

Questions:
- Anyone better ideas?
- What happens within Postgresql (special to Exclusion constraints) that
causes this deadlock and why is it (too) hard to fix it within the
backend?

Please check my two posts in pgsql-bugs on "BUG #15026: Deadlock using
GIST index" for more info including a comment from backend source code
where the dead-lock is predicted, but i.m.o underestimated.

Regards,

Mark