Wait-For Graph Analysis¶

Analytical tool — instantiates Deadlock Resolution

Draws every participant as a node and every "is waiting for" as a directed edge, then finds the cycle that proves the system is deadlocked and marks where it must be cut.

Before you can break a deadlock you have to prove there is one and see its shape. Wait-For Graph Analysis represents each process, transaction, or actor as a node and each "A is blocked waiting on something B holds" as a directed edge from A to B. A system is deadlocked if and only if this graph contains a directed cycle — so detection reduces to cycle-finding, and the cycle itself is the map of who is stuck on whom. Its defining move is that it is formal and mechanical: it doesn't ask anyone to narrate their side, it computes the loop from the wait relation, and every edge on that loop is a candidate link to sever. That is what separates it from the human, narrative tracing that its sibling Blocked Dependency Trace does — here the cycle is derived, not interviewed.

Example¶

A database is running two concurrent transactions. T1 holds a write lock on the orders row and now needs the inventory row; T2 holds the write lock on inventory and now needs orders. Neither can proceed, and every new query on those rows joins the pile. The lock manager doesn't debate intent — it maintains a wait-for graph: an edge T1→T2 (T1 waits on a lock T2 holds) and an edge T2→T1. On its next detection sweep it finds the two-node cycle T1→T2→T1, which is proof, not suspicion, that this is a deadlock and not merely a slow query.

The graph does one more thing: it names the break points. Every edge on the cycle is a link that, if cut, dissolves the loop, so the manager can now hand a shortlist — "abort T1 or abort T2" — to whatever policy picks the victim. The output is a verdict plus a menu: "deadlocked cycle {T1, T2}; cutting either edge frees both." It says nothing about which to cut or how to recover — only where a cut would work.

How it works¶

The distinguishing logic is that detection and structure fall out of one construction:

Build the wait relation. For every waiting participant, add a directed edge to whoever holds the thing it is blocked on. Multi-instance resources use the wait-for graph's richer cousin (a resource-allocation graph) where a plain cycle only signals possible deadlock.
Search for a directed cycle. A depth-first search that finds a back edge is a deadlock certificate; no cycle means the stall is something else (starvation, slowness, a linear chain still making progress).
Enumerate the cycle's edges as break candidates. Each edge on the loop is a spot where a release, preemption, or abort would restore progress — the raw material break-point selection then ranks.

Tuning parameters¶

Detection cadence — continuous, on every wait, versus a periodic sweep. Frequent detection catches deadlocks fast but burns cycles; periodic is cheaper but lets a deadlock sit.
Graph scope — a single resource manager's local graph versus a global graph stitched across nodes. Global detection is complete but expensive and can race with a changing state; local detection is cheap but misses cross-node cycles.
Single- vs. multi-instance modeling — whether a cycle is proof of deadlock or only a warning requiring a further reduction check. Getting this wrong yields false alarms on pooled resources.
Candidate ranking hint — whether the tool merely lists cycle edges or annotates them with cost/rollback weight to steer victim choice downstream.

When it helps, and when it misleads¶

Its strength is turning "the system feels stuck" into a decidable question with a definite answer and a definite location. On the classic circular-wait condition it is exact: a cycle in the wait-for graph is the deadlock,^[1] and the cycle doubles as the shared picture and the break-point shortlist.

It misleads when the model doesn't match reality. On multi-instance or pooled resources a bare cycle can be a false positive, and a stale snapshot can report a cycle that has already cleared or miss one forming between sweeps. Its deeper limit is scope: it can only see waits it was told to record, so a deadlock whose blocking condition is a human approval, a social commitment, or an out-of-band dependency simply never appears as an edge — which is exactly the ground Blocked Dependency Trace covers. The discipline is to keep the graph's inputs honest and current, and to treat a detected cycle as a diagnosis handed to a break-and-recover mechanism, never as the fix itself.

How it implements the components¶

Wait-For Graph Analysis fills the detection-and-mapping side of the archetype — the components a diagnostic can produce, not the ones that act:

deadlock_detection — a directed cycle is the formal certificate that separates true circular blocking from ordinary delay.
cycle_map — the graph is the shared structural picture of who holds what and where the loop closes.
break_point_selection — every edge on the cycle is enumerated as a candidate link to cut, feeding the choice of victim.

It does not name the blocking conditions in human terms (held_condition_inventory, evidence_record) — that's Blocked Dependency Trace — and it neither executes a break nor recovers state; the bounded_break_action, recovery_path, and resolver_authority components belong to the acting siblings such as Lock Preemption and Rollback to Safe State.

Instantiates: Deadlock Resolution — supplies the detection and break-point map every acting mechanism depends on.
Sibling mechanisms: Blocked Dependency Trace · Lock Preemption · Process Kill or Restart · Rollback to Safe State · Timeout and Retry Recovery · Forced Release Protocol · Escalation to Authority · Arbitration Decision · Mediation or Renegotiation · Tie-Break Rule

Notes¶

The graph is a diagnosis, not a cure: it proves a deadlock exists and points at cuttable edges but performs no cut and preserves no state. Pairing it with a recovery-aware acting mechanism is essential — cutting an edge chosen purely for graph convenience, with no thought to which victim is cheapest to roll back, is how deadlock recovery turns into data loss.

References¶

[1] Circular wait is one of the four Coffman conditions jointly necessary for deadlock (with mutual exclusion, hold-and-wait, and no preemption). The wait-for graph is precisely the tool that tests for the circular-wait condition; breaking any one Coffman condition — here, cutting the cycle — dissolves the deadlock. ↩