How would you model a set of blocked threads as a graph to prove they are deadlocked, and when is finding a cycle in that graph not enough to conclude deadlock?

## The wait-for graph The standard formal model of a blocked system is the **wait-for graph**. Each node is a participant - a thread, process, or transaction. A directed edge T1 -> T2 exists exactly when T1 is blocked requesting a resource that T2 currently holds. The graph is a snapshot: it describes the system at one instant, and it changes as threads acquire and release. With this model the deadlock question becomes a graph question. If T1 -> T2 -> T3 -> T1, then T1 cannot proceed until T2 does, T2 not until T3, T3 not until T1: no member of the cycle can ever move, and since none moves, none releases. That is precisely the definition of deadlock. Detection is a plain cycle search (depth-first search marking nodes in-progress and finished, O(V+E)), which is why database engines and runtime deadlock detectors can afford to run it. ## The richer model: resource-allocation graph The wait-for graph is a projection of a two-kind graph. In a **resource-allocation graph** there are process nodes and resource nodes: an *assignment* edge points from a resource instance to the holder, and a *request* edge from a process to a resource type. Collapsing resource nodes (following request edge then assignment edge) gives the wait-for graph. The distinction matters because a resource type may have several interchangeable instances - ten connections in a pool, N permits in a semaphore, four slots in a bounded queue. Then a cycle no longer proves deadlock: a process outside the cycle may hold an instance of the contested type and release it, satisfying somebody in the cycle and unravelling it. In this setting a cycle is **necessary but not sufficient**. The test that works is **graph reduction**: repeatedly find any process whose outstanding request can be satisfied from currently free instances, assume it runs to completion, and release everything it holds back to the free pool. Repeat. If the graph reduces to nothing, the state is not deadlocked; whichever processes remain irreducible are the deadlocked set. This is the same shape of argument as a safety check over resource vectors. ## Request semantics change the criterion The model above assumes a thread blocks on exactly one thing (or on all of a set - an AND-request). Some systems allow **OR-requests**: wake me when any one of several resources is available (waiting on any of several queues, or on the first of several replies). Under OR semantics a cycle is not enough, because one satisfiable branch is an escape; the correct criterion is a **knot** - a subgraph in which every node reachable from any node can reach every other, so no branch leads out. ## Distributed wait-for graphs Across machines, no one holds the whole graph, and there is no instantaneous global snapshot. Two families of technique are used. **Centralized detection** ships local edges to a coordinator that assembles a global graph, which is prone to *phantom deadlocks*: edges recorded at different instants can compose into a cycle that never existed simultaneously, and aborting on it wastes work. **Edge chasing** sends a probe message along wait-for edges carrying the initiator's identity; if a probe returns to its initiator, a real cycle exists. Many production systems dodge the problem entirely by using a timeout heuristic: waiting longer than X is treated as deadlock. That is cheap and needs no graph, but it conflates deadlock with slowness and produces false positives under load. ## Building the graph in practice To populate the edges you need two facts per blocked thread: which resource it is waiting on, and who holds that resource. Runtime lock implementations usually record the owner, so stack snapshots can expose both and a detector can construct the graph automatically. Resources managed by application code - a permit in your own pool, a slot in your own queue - carry no such ownership metadata, so no automatic detector sees them, and you must reconstruct the edges by hand from instrumentation or from what each blocked thread was doing.