Distributed deadlock and recovery

Distributed deadlock

A deadlock is a state in which each transaction in a set is waiting for a lock held by another transaction in the set, so none can proceed. It is shown by a cycle in the wait-for graph (nodes are transactions, an edge T → U means T waits for U).

A distributed deadlock occurs when the wait-for cycle spans several servers. Each server sees only a part of the graph (a local wait-for graph without a local cycle), but the global graph has a cycle.

Example: T holds a lock on A at server X, and U holds a lock on B at server Y. T now requests B at Y (so T waits for U), and U requests A at X (so U waits for T).

Server X: U -> T  (U waits for T on A)
Server Y: T -> U  (T waits for U on B)
Global:   T -> U -> T   (cycle = deadlock)

Detection and resolution

Detection can be done by:

• Centralized detection: servers send local wait-for graphs to a coordinator, which builds the global graph and looks for cycles. It is simple, but the coordinator is a single point of failure, the message cost is high, and it may report phantom deadlocks (see below).
• Distributed detection by edge chasing (Chandy-Misra-Haas): when T starts waiting for U, a probe message carrying the path (T → U) is sent along the wait-for edges to the server where U is blocked. Each server extends the probe with the next waiting transaction. If the probe returns to its initiator (a transaction appears twice), a cycle (deadlock) is detected. No global graph is needed.

T waits for U at X: probe <T->U> sent to Y
U waits for V at Y: probe becomes <T->U->V>
...
probe reaches T again => deadlock

Resolution (recovery): pick a victim transaction on the cycle and abort it, releasing its locks. The victim is chosen by priority, age or least work done. In edge chasing, transactions are given priorities (e.g. by timestamp), and the lowest-priority transaction in the cycle (e.g. the youngest) is aborted, so that every server that detects the cycle picks the same victim and only one transaction is aborted.

A phantom deadlock is a detected cycle that no longer exists because a transaction in it has released its locks in the meantime (e.g. it aborted). To avoid it, the detection information must be consistent and up to date.