Wait-for graph

In computer science, a system that allows concurrent operation of multiple processes and locking of resources and which does not provide mechanisms to avoid or prevent deadlock must support a mechanism to detect deadlocks and an algorithm for recovering from them.

One such deadlock detection algorithm makes use of a wait-for graph to track which other processes a process is currently blocking on. In a wait-for graph, processes are represented as nodes, and an edge from process ${\displaystyle P_{i}}$ to ${\displaystyle P_{j}}$ implies ${\displaystyle P_{j}}$ is holding a resource that ${\displaystyle P_{i}}$ needs and thus ${\displaystyle P_{i}}$ is waiting for ${\displaystyle P_{j}}$ to release its lock on that resource. If the process is waiting for more than a single resource to become available (the trivial case), multiple edges may represent a conjunctive (and) or disjunctive (or) set of different resources or a

A wait-for graph is a graph of conflicts blocked by locks from being materialized; it can be also defined as the graph of non-materialized conflicts; conflicts not materialized are not reflected in the precedence graph and do not affect serializability.

The wait-for-graph scheme is not applicable to a resource allocation system with multiple instances of each resource type.

An arc from a transaction T1 to another transaction T2 represents that T1 waits for T2 to release a lock (i.e., T1 acquired a lock which is incompatible with a previously acquired lock from T2). A lock is incompatible with another if they are on the same object, one is a write, and they are from different transactions.