Distributed deadlock detection

Step through what each site sees on its own, then what happens once you merge all three. Site A alone: no cycle. Adding Site B: still no cycle, just a chain. Only once Site C's edge closes the loop does a cycle appear — and it was there the whole time, just split across machines that never compared notes.

• Wait-for edge $p \to q$ — process $p$ is blocked, waiting for a resource held by $q$.
• Local view — one site's own slice of the global wait-for graph: only the edges touching resources it manages.
• Merged graph — the union of every site's local view, with duplicate edges collapsed.
• Deadlock — a directed cycle in the merged graph. No cycle, no deadlock — a long wait-for chain (like P4 → P5) is just an ordinary, resolvable wait.

1. A cycle can be invisible locally and still be real

   Nothing requires a cycle to live inside one site's edges. It only has to exist once every site's edges are combined — which is exactly why a distributed detector can't just ask "does any one node have a cycle?" and stop there.

2. Merging is a union, not a vote

   Combining local views isn't about resolving disagreement — every site's reported edges are simply true, from its own vantage point. The merge is a plain union; duplicates (the same edge reported by two sites) are removed, not double-counted.

3. Not every merged edge belongs to a cycle

   P4 → P5 stays a straight-line wait no matter how many sites you merge in — P5 never waits on anyone, so that edge can never close into a loop. Detecting deadlock means finding a cycle, not just finding edges.

Toggle sites on and off freely. Try any two at once — Site A + Site B, or Site A + Site C. Watch the readout: no pair ever produces a cycle. Only when all three are switched on does the loop close and the cycle light up.

Three sites, five processes, edges reported as: Site A → (P1, P2), Site B → (P2, P3), Site C → (P3, P1) and (P4, P5).

1. Check each site alone

   • Site A: P1 → P2 alone isn't a cycle
   • Site B: P2 → P3 alone isn't a cycle
   • Site C: P3 → P1 alone isn't a cycle, and P4 → P5 never will be — P5 has no outgoing wait-for edge in this scenario
2. Merge all local views

   Union of all edges:

   • P1 → P2
   • P2 → P3
   • P3 → P1
   • P4 → P5

   Four edges, no duplicates to collapse here (no two sites reported the same pair).

3. Search the merged graph for a cycle

   Starting a depth-first search from P1: P1 → P2 → P3 → P1 closes a loop back to a node already on the current search path. That's the cycle: P1, P2, P3. Separately, P4 → P5 is a dead end — P5 has no outgoing edge, so no search starting there can ever cycle back.