--- title: "Distributed deadlock and recovery" subject: "Distributed System" chapter: 8 key: "semester_7/distributed_system:distributed-deadlock-note" source: https://www.bctengineer.com/q/semester_7/distributed_system/distributed-deadlock-note site: BCT Engineering --- # Distributed deadlock and recovery Distributed System · Chapter 8: Transaction and Concurrency Control - Asked in: 2075 Chaitra, 4 marks; 2074 Asoj, 4 marks; Model question (asked 3 times) - Video: [DS19:Distributed Deadlock Detection | Resource vs Communication Deadlocks distributed system](https://www.youtube.com/watch?v=IbmOd-v6ME4) — University Academy - Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14 - Page: https://www.bctengineer.com/q/semester_7/distributed_system/distributed-deadlock-note - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-8 ## Question Write a short note on distributed deadlock (and recovery). Define distributed deadlock in distributed transaction. Explain the deadlock resolution technique with an example. ## Short answer A distributed deadlock is a cycle in the global wait-for graph across servers. Detection uses edge chasing: probes follow wait-for edges; if a probe returns to the initiator, deadlock is found. Resolution aborts a victim transaction (e.g., youngest) in the cycle to release locks. ## Answer #### 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). ```text 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. ```text T waits for U at X: probe U> sent to Y U waits for V at Y: probe becomes 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. ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. What is a distributed deadlock? A. A wait-for cycle that spans several servers while each server sees only a part without a local cycle B. A deadlock in a single server only C. A network cable failure D. A transaction that aborts itself Answer: A. Each server has a local wait-for graph without a cycle, but the global graph contains a cycle. (Key point: Definition of distributed deadlock) 2. How does edge chasing detect a deadlock? A. Servers send all local graphs to one coordinator B. A probe carrying the wait path is forwarded along wait-for edges; if it returns to its initiator, a cycle exists C. Each transaction polls the network D. It assumes deadlock after a fixed timeout Answer: B. The probe is extended at each server, and a transaction appearing twice in it means a cycle, without needing a global graph. (Key point: Edge chasing) 3. How is a detected deadlock resolved? A. Abort a victim transaction on the cycle to release its locks B. Wait indefinitely C. Commit all transactions in the cycle D. Delete the data items Answer: A. A victim is chosen by priority, age or least work done; choosing, e.g., the highest id ensures all servers pick the same one. (Key point: Deadlock resolution) 4. What is a phantom deadlock? A. A real deadlock that is never detected B. A detected cycle that no longer exists because a transaction released its lock meanwhile C. A deadlock among only two servers D. A deadlock caused by timestamps Answer: B. Inconsistent or outdated wait-for information may report a cycle that has already disappeared, as in centralized detection. (Key point: Phantom deadlock) ## Related in Distributed System - [Need of transaction; phantom deadlock](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atransaction-deadlock-phantom) — Distributed System, chapter 8 - [Transaction recovery techniques](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atransaction-recovery) — Distributed System, chapter 8 - [Byzantine generals; recovery technique](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Abyzantine-recovery) — Distributed System, chapter 9 - [Distributed deadlock; two-phase commit](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-deadlock-2pc) — Distributed System, chapter 8 - [Lock; distributed CC; deadlock situation](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Alock-cc-deadlock-situation) — Distributed System, chapter 8 - [Approaches to avoid distributed deadlock](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adeadlock-avoidance-approaches) — Distributed System, chapter 8 ## Related in other subjects - [Deadlock conditions; recovery methods](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-resource-conditions-recovery) — Operating System, chapter 7 - [Four deadlock conditions; prevention, recovery](https://www.bctengineer.com/question.md?key=semester_6%2Foperating_system%3Adeadlock-conditions-prevention-recovery) — Operating System, chapter 7 - [Recovery from log: deferred vs immediate](https://www.bctengineer.com/question.md?key=semester_6%2Fdatabase_management_system%3Alog-recovery-deferred-immediate) — Database Management System, chapter 8