Foreign Key Deadlocking

Hi, we're using Postgres 8.1.4.

We've been seeing deadlock errors of this form, sometimes as often as
several times per hour:

Apr 17 13:39:50 postgres[53643]: [4-1] ERROR: deadlock detected
Apr 17 13:39:50 postgres[53643]: [4-2] DETAIL: Process 53643 waits for
ShareLock on transaction 111283280; blocked by process 53447.
Apr 17 13:39:50 postgres[53643]: [4-3] Process 53447 waits for ShareLock
on transaction 111282124; blocked by process 53242.
Apr 17 13:39:50 postgres[53643]: [4-4] Process 53242 waits for ShareLock
on transaction 111282970; blocked by process 53240.
Apr 17 13:39:50 postgres[53643]: [4-5] Process 53240 waits for ShareLock
on transaction 111282935; blocked by process 53168.
Apr 17 13:39:50 postgres[53643]: [4-6] Process 53168 waits for ShareLock
on transaction 111282707; blocked by process 53643.

The deadlocks almost always seem to involve 4 or 5 processes.

After observing the behaviour of the locks table, and searching the
newsgroup and elsewhere, I'm fairly certain I know what the problem is.
There is extremely high update activity by a dozen or more processes on a
table which has FK references into two other tables. Each process may
update 10s or 100s of rows and there is really no predictable access
pattern.

This blurb is from a previous discussion I found:
-----
postgres performs a lock (share lock) on the tuples to which the foreign
keys point, apparently to prevent other transactions from modifying the
foreign key before this transaction commits. it is practically impossible to
cause the references to be always in the same order, so a deadlock can
occur.
-----

I also see claims that this problem is fixed in 8.2, and if the fix is what
I think it is, it's also in 8.1.6.

Release 8.1.6
Changes
* Fix bug causing needless deadlock errors on row-level locks (Tom)

Upgrading to 8.2 is not realistic at this point of our project cycle, but if
the fix is indeed in 8.1.6, I can push to upgrade to 8.1.latest.

Can someone confirm that I've identified the right fix?

Thanks,
Steve