Distributed Deadlock Detection: Wait-For Graphs & Edge Chasing Algorithms

In a single database instance, deadlock detection is straightforward: the engine maintains an in-memory Wait-For Graph (WFG) where nodes represent active transactions and directed edges represent lock wait dependencies (T_1 o T_2 means T_1 is waiting for a lock held by T_2). A background thread runs cycle detection (O(V+E) DFS); if a cycle exists (T_1 o T_2 o T_3 o T_1), the engine aborts the lowest-cost 'Victim' transaction. However, in distributed databases or microservice architectures, Transaction 1 on Node A waits for Transaction 2 on Node B, which waits for Transaction 3 on Node C, which waits for Transaction 1 on Node A. No single node sees the full graph. Distributed systems solve this using Edge Chasing Algorithms (Mitchell-Merritt / Chandy-Misra-Haas): when a transaction blocks, it propagates a small 'Probe' token along lock dependency edges. If a transaction receives its own probe token back, a distributed cycle is mathematically proven, prompting an immediate deterministic victim abort.