Why would executing individual update statements on two unrelated tables each within their own transaction cause deadlock?

Question

I've searched the stackoverflow network, but couldn't find anything similar to the scenario detailed below. It doesn't make sense how deadlock could occur, but we're seeing logs from the database indicating that deadlocks are in fact happening. It's not a constant occurrence, but happens every once in a while. We started noticing more deadlocks than usual after deploying our latest code changes to our Staging environment, which isn't under heavy load. We therefore need to investigate the cause before releasing the current code to the Production environment.

PostgreSQL version: 11.7

The following holds true for both tables being updated:

• Both tables are involved in the apparent deadlock
• Neither table has any foreign keys (not to the other table and also not to a shared table)

The following holds true for both statements being executed:

• Each UPDATE statement is executing in its own transaction
• Each UPDATE statement is the only statement being executed in its transaction
• Each UPDATE statement is updating a single row in its respective table by specifying the primary key in the WHERE clause

We are seeing these type of messages being logged every once in a while:

2022-07-04 04:50:25 UTC [125066]: LOG:  process 125066 detected deadlock while waiting for ShareLock on transaction 109899769 after 1000.091 ms
2022-07-04 04:50:25 UTC [125066]: DETAIL:  Process holding the lock: 29727. Wait queue: .
2022-07-04 04:50:25 UTC [125066]: CONTEXT:  while updating tuple (24,3) in relation "tx_device"
2022-07-04 04:50:25 UTC [125066]: STATEMENT:  update core.tx_device set ad_verified = $1 where core.tx_device.id = $2
2022-07-04 04:50:25 UTC [125066]: ERROR:  deadlock detected
2022-07-04 04:50:25 UTC [125066]: DETAIL:
      Process 125066 waits for ShareLock on transaction 109899769; blocked by process 29727.
      Process  29727 waits for ShareLock on transaction 109899771; blocked by process 125066.
      Process 125066: update core.tx_device set ad_verified = $1 where core.tx_device.id = $2
      Process  29727: update core.device set ou = $1, name = $2, ad_user = $3, ad_verified = $4 where core.device.id = $5
2022-07-04 04:50:25 UTC [125066]: HINT:  See server log for query details.
2022-07-04 04:50:25 UTC [125066]: CONTEXT:  while updating tuple (24,3) in relation "tx_device"
2022-07-04 04:50:25 UTC [125066]: STATEMENT:  update core.tx_device set ad_verified = $1 where core.tx_device.id = $2

Here are the DDLs (simplified) for the two tables:

create table core.device (
    id bytea not null constraint device_pkey primary key,
    name varchar(255),
    ad_user boolean default true not null,
    ou varchar(255),
    ad_verified boolean default true not null
);

create table core.tx_device (
    id bytea not null constraint tx_device_pkey primary key,
    ad_device boolean not null,
    host_name varchar(255),
    ad_verified boolean default false not null
);

There are various indexes on each table; let me know if you're interested in seeing that.

If my understanding is correct then we've adhered to the three guidelines provided by Erwin in this answer.

I have not been able to simulate the deadlock using manual transactions in separate connections/sessions.

I would like to understand why we are experiencing deadlock in this scenario?

I've looked at this unanswered question, but we don't have foreign keys as in that scenario.