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 on transaction; 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 two processes 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 bravo with the same PK value that process 24342 is trying to insert. But process 23912 never even touches that table, so I am 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 to wait 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 possible deadlock while trying to acquire tuple locks in EvalPlanQual processing" - but I guess that does not refer to a deadlock on "user level".

Any ideas?
Thomas