Detecting Deadlock Across Nodes Without a Shared Wait-For Graph

A single-node deadlock detector works on a wait-for graph it can see entirely. Every lock manager knows who holds each lock and who is queued for it, so a cycle in that graph is a fact about the local state, and breaking it by aborting a victim is safe. Distribute the locks across nodes and the graph fragments. Each node sees only the edges whose waiters are local, and a cycle that spans three nodes appears at none of them.

The graph that no node can see

Take a transaction T1 running on node A that holds a row lock and waits for a row locked by T2, which is running on node B. From A’s perspective, the edge T1 → T2 exists. But A does not know what T2 is waiting for, because T2’s waits are recorded on B. If T2 waits for T3 on C, and T3 waits for T1 on A, the cycle is T1 → T2 → T3 → T1. Node A sees one edge of it, node B sees one, node C sees one.

A global detector would need the union. The naive approach is to collect the full graph periodically: every node ships its local wait-for edges to a central site, which joins them and looks for cycles. This works and is what early distributed database systems did, but it has three problems.

The graph is a snapshot of a moving object. Between the moment a node serialises its edges and the moment the central site joins them, transactions commit, abort, and acquire new locks. The union may contain edges that never coexisted. A cycle found in such a union may be a cycle that never existed, which is the phantom deadlock problem.

The central site is a single point of failure and a scaling bottleneck. Every node must ship its edge set on a schedule, and the message volume grows with the number of waiting transactions, which grows exactly when the system is congested.

The graph is large. A busy system can have thousands of waiters, and the cost of joining edge sets is proportional to the total edge count, which is paid repeatedly for a condition that is rare.

Edge chasing as an alternative

The better-known distributed algorithm avoids the central site. Each node, when it observes a local wait, sends a probe along the wait-for edge to the node where the blocker is running. The probe carries the identity of the transaction that originated it. When the probe reaches a node, that node checks whether the transaction it names is itself waiting, and if so forwards the probe along its own outgoing edge. If a probe returns to its origin, a cycle exists.

The cost is proportional to the length of the cycle times the number of probes in flight, not to the size of the global graph. A node only does work when a wait actually occurs, which is the right trigger: no deadlock can form without a wait, so a detector that runs on waits pays only when there is something to detect.

There is a subtlety in the bookkeeping. Probes must not be duplicated indefinitely, so each node records which probe origins it has already forwarded and suppresses repeats. This record is per-transaction and must be discarded when the transaction ends, or it becomes a leak. The record is also the mechanism by which a node can answer “have I already seen this probe from this origin”, which turns the search into a bounded traversal rather than a flood.

The probe carries one identifier, so the amount of state is small: a set of origin identifiers per blocked transaction. Compare that with shipping the edge set, which is proportional to the number of waiters.

Why phantom deadlocks appear anyway

Neither approach escapes a deeper problem: the wait-for graph is not stable, and an edge that is real when observed may be gone when acted on.

Consider the edge T1 → T2 on node A. T1 waits for a lock held by T2. Before the detector acts, T2 aborts for an unrelated reason and releases the lock. T1 acquires it and proceeds. Meanwhile a probe or a collected edge set still records T1 → T2, and a cycle is reported that involves T1 and some other transaction. Aborting T1 as a deadlock victim would be a false positive: there was no deadlock, only a stale edge.

The consequence of a phantom deadlock is not correctness damage, since aborting a transaction that is not deadlocked is always safe: abort is the default outcome. The cost is wasted work and, worse, a pattern: if the detector is prone to phantoms under load, it aborts transactions that were making progress, which reduces throughput exactly when throughput is scarce and can produce a livelock where the same transactions are repeatedly chosen.

The standard mitigation is to re-verify before aborting. When a cycle is suspected, the detector asks the nodes involved whether the edges still exist, or it delays the abort until it has confirmation from the participants. Verification costs another round trip but reduces false positives substantially. It cannot eliminate them: between the verification and the abort, the graph can change again.

A second mitigation is to prefer victims whose abort is cheap and whose wait is long. A transaction that has been waiting for a long time is more likely to be part of a real cycle than one that just started waiting, and a transaction with few writes is cheaper to roll back. Both heuristics are approximations, and both bias the detector toward aborting the transactions least likely to be doing useful work.

Timeouts and what they actually buy

Most production systems do not run a distributed detector at all. They use a lock timeout: a statement that waits longer than a configured interval is cancelled, and its transaction is aborted. This is what a single-node database does as a backstop, and it works across nodes without any global view.

The timeout’s guarantee is weaker than detection in one direction and stronger in another. It is weaker because it fires on any long wait, deadlocked or not. A transaction waiting behind a long-running batch job is aborted just as a deadlocked one is. That converts a scheduling problem into a correctness-neutral but wasteful abort, and it means the timeout must be set above the longest legitimate wait, which is a value nobody knows.

It is stronger because it needs no distributed coordination and cannot produce phantom aborts from stale state. There is no graph to be inconsistent, no probe to be misrouted, and no central site to fail. For systems where deadlocks are rare and long waits are rarer, the timeout is the cheaper engineering choice, and its cost is bounded by the timeout value rather than by the size of the system.

The interaction with two-phase commit is where timeouts get dangerous. A timeout that aborts a transaction before it votes is safe. A timeout that fires on a prepared transaction is not a timeout at all, because the participant cannot abort: it has voted. The wait must continue regardless of any local timer, as described in in-doubt transactions and blocking. A lock timeout setting that applies uniformly to prepared transactions is therefore either ineffective or, if it is allowed to abort them, a violation of atomicity.

The priority and ordering complications

Detectors that abort a victim must choose one, and the choice is not arbitrary in a distributed system. If two nodes independently detect the same cycle and each picks a local victim, both victims abort, which is a double abort: more work lost than necessary, though still correct.

The standard fix is a total order on transactions, typically by timestamp, with the rule that the youngest transaction in a cycle is the victim. If both detectors see the same cycle and both apply the same order, they pick the same victim, and the duplicate abort is harmless because the second one finds the transaction already gone.

The order must be global, which brings back the problem that distributed systems do not have a shared clock. Timestamps assigned by different nodes can collide or invert, and a detector that orders by a local counter will pick different victims on different nodes. The ordering machinery is the subject of timestamp oracles and global transaction order, and deadlock victim selection is one of the places where its absence is directly observable as duplicated work rather than as a subtle anomaly.

A related ordering issue arises with lock acquisition order. If every transaction acquires locks in a globally agreed order, cycles cannot form at all, which is the classic prevention approach. The order must be agreed across nodes, which means the lock identifiers must be globally comparable, which in a sharded system means the shard identifier must participate in the ordering. When it does not, two transactions can each hold what the other needs on different shards, and no local detector will ever see the full cycle.

Choosing a mechanism

The decision reduces to three options with different cost profiles.

Global detection by periodic collection is simple to implement and works for small clusters. Its cost scales with the number of waiters and its false positive rate scales with the collection interval relative to transaction duration. It is a reasonable choice for a handful of nodes with long transactions.

Edge chasing is the better fit for larger systems: it costs per wait rather than per waiter, needs no central site, and its state is small. Its weakness is the verification problem, which requires care to avoid acting on stale edges.

Timeouts are the fallback that every system has, and the right default when deadlocks are rare. They are not a detection mechanism in the formal sense, since they cannot distinguish deadlock from slow progress, but they bound the damage of any wait and require no distributed state at all.

What none of them solve is the case where the cycle involves a prepared transaction. A prepared transaction cannot be aborted by the detector, so the cycle it participates in cannot be broken by victim selection. The detector’s only recourse is to wait for the decision, which means the deadlock is really an in-doubt transaction wearing a different hat. Recognising that early is the difference between a detector that resolves contention and one that spins while the real problem is an unreachable coordinator.