Distributed Deadlock Detection (Wait-For Graph)

Answer first: A distributed wait-for graph represents transactions as vertices and blocking dependencies as directed edges; a cycle is evidence of deadlock only when the detector handles stale or causally inconsistent edges. Edge-chasing sends probes along dependencies, while centralised detectors merge graph fragments and must guard against phantom cycles.

Primary references: A Distributed Algorithm for Deadlock Detection and Resolution and the CockroachDB SIGMOD paper. Related KBY concept: distributed locking.

In single-node databases, deadlock detection is trivial: the lock manager owns a complete wait-for graph and can run cycle detection (typically DFS) whenever a new edge is added. In a distributed system, transaction T1 on node A may block waiting for a lock held by T2, while T2 on node B is blocked waiting for a lock held by T1 — the cycle only becomes visible if the partial graphs on A and B are merged. Doing this correctly, without excessive coordination overhead, is the core problem.

The classic solution is the Chandy-Misra-Haas edge-chasing algorithm: instead of constructing a global graph centrally, nodes propagate probe messages along the wait-for edges. A probe carries the identity of the transaction that initiated it; if a probe returns to its initiator, a cycle (deadlock) exists. This avoids a single point of failure and scales with the depth of the wait chain rather than the total system size. Alternative designs use a centralized deadlock detector service that periodically collects local wait-for graph fragments from all nodes and performs global cycle detection — simpler to reason about, but introduces detection latency and a scalability bottleneck at high transaction rates.

The dominant failure mode is the phantom deadlock: because wait-for edges are collected asynchronously across nodes with unsynchronized clocks and in-flight messages, a detector can observe a cycle that never actually existed simultaneously — e.g., T2 released its lock on B moments before the stale edge was reported by A. Precise detection requires either a causally consistent snapshot of the global graph (analogous to a Chandy-Lamport snapshot) or generation/epoch tagging on edges so stale information is discarded. Systems that skip this rigor tend to compensate with victim-selection heuristics (abort the youngest transaction, or the one with least accumulated work) applied conservatively to bound false-positive damage.

• Timeout-based avoidance is the common alternative to true detection: instead of building any graph, a transaction blocked longer than a threshold is unilaterally aborted. This trades precision for simplicity but wastes throughput under legitimate long-held locks and can still miss deadlocks that resolve just under the timeout window.
• Wound-wait / wait-die schemes prevent deadlocks proactively using transaction timestamps rather than detecting them after formation, avoiding the graph-construction cost entirely at the price of more aggressive aborts.
• Distributed SQL engines (e.g., CockroachDB’s txnWaitQueue) implement a hybrid: local wait-for graphs per range, with push-based queries to the lock holder’s node to walk the chain when a wait exceeds a threshold, converging toward Chandy-Misra-Haas behavior without a global coordinator.

Architecturally, the decision to implement precise distributed deadlock detection versus timeout-based avoidance is a direct latency/throughput/complexity tradeoff: precise detection minimizes unnecessary aborts under contention but adds message overhead and snapshot-consistency engineering; timeout-based avoidance is operationally simpler but degrades badly under workloads with legitimate long transactions or high lock fan-out. Systems exposing pessimistic locking across shards or partitions should make this tradeoff explicit, since silent reliance on per-node timeouts is a common source of mysterious, load-dependent transaction abort storms in production.