Confusing deadlock report

Hello,

we have a strange (at least to me) deadlock situation which does not seem to fall into the "usual" deadlock category.

The error as reported in the Postgres log file is this:

2016-03-12 13:51:29.305 CET [23912]: [1-1] user=arthur,db=prod,app=[unknown] ERROR: deadlock detected
2016-03-12 13:51:29.305 CET [23912]: [2-1] user=arthur,db=prod,app=[unknown] DETAIL: Process 23912 waits for ShareLock
ontransaction; blocked by process 24342.  
        Process 24342 waits for ShareLock on transaction 39632974; blocked by process 23912.
        Process 23912: UPDATE alpha SET some_flag = $1 WHERE (id = $2)
        Process 24342: INSERT INTO bravo (..., alpha_id) VALUES ($1, $2, $3, $4, $5, $6, $7, $8, $9, $10)

(I have "obfuscated" the table names)


Process 24342 did update table alpha in an earlier step, but a different row than Process 23912 updated.
Table bravo has a foreign key to table alpha.

My understanding of the deadlock report is that the statements shown in the log are the actual statements on which the
twoprocesses were waiting.  

What I think is unusual in this situation is the INSERT statement that is part of the deadlock situation.

The only way I can think of how a deadlock could happen during an insert, is if process 23912 had inserted a row into
bravowith the same PK value that process 24342 is trying to insert. But process 23912 never even touches that table, so
Iam a bit confused on how this can happen.  

Can the foreign key between bravo and alpha play a role here? With some simple test setups I could not get the insert
towait even if it was referencing the row that the other process has updated.  

This happened on 9.3.10 running on Debian

The only changes I have found regarding "locks" or "deadlocks" after 9.3.10 is one change in 9.4.1 that says "Avoid
possibledeadlock while trying to acquire tuple locks in EvalPlanQual processing" - but I guess that does not refer to a
deadlockon "user level". 

Any ideas?
Thomas