How Is Deadlock Detected in a Distributed System?
Learn how distributed deadlock detection works — edge-chasing, Chandy-Misra-Haas, and recovery — with examples and interview questions.
Expected Interview Answer
Distributed deadlock detection builds a wait-for graph across multiple machines and searches for a cycle spanning nodes, most commonly using the Chandy-Misra-Haas edge-chasing algorithm, since no single machine has the full picture of who is waiting on whom the way a local OS does.
Unlike single-machine deadlock detection, which can inspect one in-memory wait-for graph directly, a distributed system has each process's resource dependencies scattered across nodes, so detecting a cycle requires message passing. In the Chandy-Misra-Haas algorithm, when a process blocks waiting for a resource held by a process on another node, it sends a probe message carrying the initiator's ID along the edge of the wait-for graph; each process that receives a probe while blocked forwards it to the processes it is waiting on, and if the probe ever returns to its original initiator, a cycle (deadlock) has been confirmed. Centralized detection instead has every node periodically report its local wait-for edges to a global coordinator that merges them into one graph and runs cycle detection, which is simpler to reason about but creates a bottleneck and single point of failure, and can suffer from phantom deadlocks if edges are reported at inconsistent times. Once a real cycle is confirmed, recovery requires picking a victim process to abort or preempt, and the choice matters because aborting the wrong process can needlessly waste work already completed.
- Solves cycles that span machines, invisible to any single node's local graph
- Edge-chasing (Chandy-Misra-Haas) avoids a central bottleneck and single point of failure
- Detects true deadlock without needing global synchronized snapshots
- Directly informs victim-selection and recovery strategy in distributed databases
AI Mentor Explanation
Distributed deadlock detection is like several grounds each having a groundskeeper who is stuck waiting for equipment held at another ground, with no single person seeing the full picture. In the edge-chasing approach, each stuck groundskeeper sends a runner carrying a note with the original requester’s name to whichever ground holds what they need; if that note ever loops back to the ground that first sent it, everyone knows there is a genuine circular wait, confirming a deadlock across grounds.
Step-by-Step Explanation
Step 1
Block detected
A process blocks waiting for a resource held by a process on a remote node, creating a wait-for edge that no single machine fully sees.
Step 2
Probe sent
The blocked process (Chandy-Misra-Haas) sends a probe tagged with the original initiator's ID along the wait-for edge to the resource holder.
Step 3
Probe forwarded
Any process receiving a probe while itself blocked forwards it further along its own wait-for edges to the processes it depends on.
Step 4
Cycle confirmed
If the probe returns to the process that originally sent it, a genuine cross-node cycle exists, confirming deadlock and triggering recovery (victim selection and abort).
What Interviewer Expects
- Explanation of why distributed deadlock needs message passing, not a single in-memory graph
- Correct description of the Chandy-Misra-Haas edge-chasing (probe) algorithm
- Awareness of centralized detection's bottleneck and phantom-deadlock risk
- Understanding of recovery: victim selection and preemption after detection
Common Mistakes
- Assuming a distributed system can use a single local wait-for graph like a single-machine OS
- Not knowing what a phantom deadlock is in centralized detection
- Confusing deadlock detection with deadlock prevention/avoidance
- Forgetting recovery still requires picking a victim to abort after detection
Best Answer (HR Friendly)
“Distributed deadlock detection is about spotting a circular wait that spans multiple machines, where no single machine can see the whole picture on its own. A common approach passes a tagged message hand to hand along the chain of who is waiting on whom, and if that message ever comes back to whoever started it, that confirms a real deadlock across the machines involved.”
Code Example
struct probe { int initiator_id; int sender_id; };
int my_id;
int blocked_on[MAX_DEPS]; /* processes this node is waiting on */
int blocked_count;
void send_probe(int initiator) {
for (int i = 0; i < blocked_count; i++) {
struct probe p = { initiator, my_id };
network_send(blocked_on[i], &p, sizeof(p));
}
}
void on_probe_received(struct probe p) {
if (p.initiator_id == my_id) {
report_deadlock(); /* probe looped back: cycle confirmed */
return;
}
if (is_blocked(my_id)) {
send_probe(p.initiator_id); /* forward along our own wait-for edges */
}
}Follow-up Questions
- What is a phantom deadlock and why does centralized detection risk it?
- How does the Chandy-Misra-Haas algorithm terminate if no deadlock exists?
- How is a victim process chosen once a distributed deadlock is confirmed?
- How does distributed deadlock detection differ from deadlock avoidance (e.g., the Banker's algorithm)?
MCQ Practice
1. In the Chandy-Misra-Haas algorithm, what confirms a deadlock?
When a forwarded probe eventually returns to its original initiator, that proves a genuine cycle exists across nodes.
2. Why can centralized distributed deadlock detection report phantom deadlocks?
If edges are gathered asynchronously, a stale combination of edges can appear cyclic even though no such cycle existed at any single instant.
3. What must happen after a distributed deadlock is confirmed?
Detection only identifies the cycle; recovery requires choosing a victim to abort or have its resources preempted to break the deadlock.
Flash Cards
Why is distributed deadlock detection harder than single-machine detection? — No single node has the full wait-for graph; dependencies span machines, requiring message passing.
What is the Chandy-Misra-Haas algorithm? — An edge-chasing algorithm where blocked processes forward tagged probes; a probe returning to its initiator confirms a cycle.
What is a phantom deadlock? — A falsely detected deadlock caused by inconsistent timing of centrally collected wait-for edges.
What must follow deadlock detection? — Recovery via victim selection — aborting or preempting a process to break the cycle.