--- title: "Distributed deadlock; two-phase commit" subject: "Distributed System" chapter: 8 key: "semester_7/distributed_system:distributed-deadlock-2pc" source: https://www.bctengineer.com/q/semester_7/distributed_system/distributed-deadlock-2pc site: BCT Engineering --- # Distributed deadlock; two-phase commit Distributed System · Chapter 8: Transaction and Concurrency Control - Asked in: 2069 Chaitra, 2+5 marks - Video: [Two phase Commit Protocol | Transaction | Distributed Systems | Lec-61 | Bhanu Priya](https://www.youtube.com/watch?v=W-TadPbi--A) — Education 4u - 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-2pc - Whole chapter: https://www.bctengineer.com/md/semester_7/distributed_system/chapter-8 ## Question What do you mean by Distributed Deadlock? Explain the two-phase commit protocol of handling distributed transaction. ## Short answer Distributed deadlock occurs when a wait-for cycle involves multiple servers; detection uses edge chasing (probe messages) or a global wait-for graph. Two-phase commit: a coordinator sends canCommit? to participants; if all vote Yes, it orders doCommit, else doAbort, ensuring all commit or abort atomically. ## 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) ``` Such deadlocks are detected by edge chasing or a global wait-for graph, and resolved by aborting a transaction in the cycle. #### Two-phase commit protocol The **two-phase commit protocol (2PC)** makes sure that all servers (participants) of a distributed transaction either all commit or all abort. One server acts as the **coordinator** (usually the one that the client contacted); others are **participants**. **Phase 1: voting** 1. The coordinator sends **canCommit?** to every participant. 2. Each participant replies **Yes** (it has saved the transaction's changes to permanent storage and is prepared; it can no longer unilaterally abort) or **No** (it aborts at once). **Phase 2: completion** 3. If all votes (including the coordinator's own) are Yes, the coordinator records the decision and sends **doCommit**; if any vote is No or a timeout occurs, it sends **doAbort**. 4. Participants carry out the decision and send **haveCommitted** to the coordinator. ```text Coordinator Participants |--- canCommit? ------->| |<------ Yes / No ------| | (decide, log) | |--- doCommit/doAbort ->| |<---- haveCommitted ---| ``` **Failures** - If a participant crashes before voting, the coordinator times out and aborts. - A participant that has voted Yes is in the **uncertain** state; if the coordinator fails it must wait (it blocks) or ask other participants for the decision. - On recovery, servers use their logs to complete the protocol. **Drawbacks**: blocking if the coordinator fails, and extra messages and delays (about 3N messages for N participants). ## Check yourself The answer's key points as multiple-choice questions, with the correct option and why. 1. In a wait-for graph, what does an edge T -> U mean? A. T holds a lock that U wants B. T waits for a lock held by U C. T started before U D. T and U are on the same server Answer: B. Edges point from the waiting transaction to the one holding the lock; a cycle indicates deadlock. (Key point: Wait-for graph) 2. T holds A at server X and U holds B at server Y. T requests B and U requests A. What is the situation? A. No deadlock since each server has no local cycle B. A distributed deadlock: global cycle T -> U -> T although each local graph has none C. T will commit first D. A phantom deadlock Answer: B. Server Y shows T waiting for U and X shows U waiting for T; combined they form a global cycle. (Key point: Distributed deadlock example) 3. Which sequence describes 2PC correctly? A. doCommit, canCommit?, haveCommitted B. canCommit? and votes, then doCommit/doAbort, then haveCommitted C. Participants decide, coordinator obeys D. Only one message from coordinator Answer: B. Phase 1 collects votes; phase 2 sends the decision and participants confirm with haveCommitted. (Key point: 2PC phases) 4. When does the coordinator send doAbort? A. If any vote is No or a timeout occurs B. Only if all votes are No C. Never D. Only after haveCommitted Answer: A. Commit needs all Yes; a single No or a timeout leads to abort everywhere. (Key point: Abort condition) ## Related in Distributed System - [Nested vs distributed transaction; 2PC](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Anested-vs-distributed-2pc) — Distributed System, chapter 8, asked 2× - [Short note: Two-phase commit](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atwo-phase-commit-note) — Distributed System, chapter 8, asked 2× - [Cascading aborts; atomic commit protocol](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acascading-aborts-acp) — Distributed System, chapter 8 - [Need of transaction; phantom deadlock](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Atransaction-deadlock-phantom) — Distributed System, chapter 8 - [Cascading aborts; three-phase commit](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Acascading-aborts-3pc) — Distributed System, chapter 8 - [Distributed deadlock and recovery](https://www.bctengineer.com/question.md?key=semester_7%2Fdistributed_system%3Adistributed-deadlock-note) — Distributed System, chapter 8, asked 3× ## Related in other subjects - [Parallelism, IPC deadlock and OS role](https://www.bctengineer.com/question.md?key=semester_4%2Fmicroprocessor%3Aparallelism-deadlock-os-role) — Microprocessor, chapter 6 - [Two-phase simplex method max:Z=3x₁−x₂](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Atwo-phase-simplex-method-max-z) — Mathematics III, chapter 5, asked 15× - [Material handling and factors to consider](https://www.bctengineer.com/question.md?key=semester_8%2Fconstruction_management%3Amaterial-handling-factors) — Construction Management, chapter 6 - [Handling voluminous data](https://www.bctengineer.com/question.md?key=semester_8%2Finformation_system%3Avoluminous-data-techniques-challenges) — Information System, chapter 8