Foreign Keys and Deadlocks

Howdy,

We have a process that's deadlocking frequently. It's basically multiple threads inserting data into a single table.

That table has FK constraints to 3 other tables.

I understand how an FK check will cause a sharelock to be acquired on the reference table and in some instances that
leads to or at least participates in a deadlock.

I don't think that's the case here, (or at least not the entire case) but I could use some assistance in helping
to convince my developers of that ;). They'd like to just remove the FK and be done with it.

I've had this link sent to me probably 100 times in the past day or so to support the theory that postgres is just
deadlocking itself:  http://archives.postgresql.org/pgsql-general/2004-01/msg00272.php
I think that's a misinterpretation, and I also assume PGs come quite a ways since then (i'm on PG9.0).

The actual error is:
Nov 1 13:59:19 db001 postgres-dev[480]: [5470-1] user=x,db=y,pid=480,2011-11-01 20:59:19 UTC ERROR: deadlock detected
Nov 1 13:59:19 db001 postgres-dev[480]: [5470-2] user=x,db=y,pid=480,2011-11-01 20:59:19 UTC DETAIL: Process 480 waits
forShareLock on transaction 4537069; blocked by process 471. 
Nov 1 13:59:19 db001 postgres-dev[480]: [5470-3] #011Process 471 waits for ShareLock on transaction 4537063; blocked by
process480. 
Nov 1 13:59:19 db001 postgres-dev[480]: [5470-4] #011Process 480: insert into a (col1, col2, col3, col4) values ($1,
$2,$3, $4) 
Nov 1 13:59:19 db001 postgres-dev[480]: [5470-5] #011Process 471: insert into  a (col1, col2, col3, col4) values ($1,
$2,$3, $4) 
Nov 1 13:59:19 db001 postgres-dev[480]: [5470-6] user=x,db=y,pid=480,2011-11-01 20:59:19 UTC HINT: See server log for
querydetails. 

Here's the scenario

table a ( int col1 references b,
          int col2 references c,
          int col3 references d,
          text col4 )


The app, basically, does a ton of parallel, possibly duplicate, inserts into table a.
That's all it's supposed to be doing (hibernate's involved though, so anything goes).

Nothing else touches those tables.

Is it possible for a deadlock to occur under those circumstances?

I suspect that it has to be a transaction, and that further up in the TX is an update to one of
the reference tables in each TX.

If we remove the FKs we no longer get the deadlock, but I'd actually like to know the
cause.

Thanks

Dave