Deadlocks in Databases

A deadlock is a state in which a set of transactions $\{T_1, T_2, \dots, T_n\}$ each wait for a resource (lock) held by another transaction in the set, forming a cycle of waiting with no way out without external intervention. Formally, transaction $T_i$ is blocked waiting for a lock held by $T_j$; if this "waits-for" relation contains a cycle $T_1 \to T_2 \to \cdots \to T_k \to T_1$, every transaction on the cycle is permanently stuck, since each can only proceed once the next one releases a lock — which will never happen. Deadlock requires four conditions to hold simultaneously, a classical characterization (originally from operating systems, and equally applicable to database locking): 1. Mutual exclusion — a lock can be held by at most one transaction (for exclusive locks). 2. Hold-and-wait — a transaction holds some locks while waiting for others. 3. No preemption — a lock cannot be forcibly taken from a transaction; it must release voluntarily. 4. Circular wait — there exists a cycle of transactions each waiting on the next. Under Two-Phase Locking, conditions 1–3 are essentially unavoidable: exclusive locks are mutual exclusion, growing-phase lock acquisition is hold-and-wait, and locks are only released at commit/abort, never preempted. This means the only condition left to control is circular wait — and that is exactly where both major strategies aim their effort. Deadlock prevention restructures how transactions request locks so that a circular wait can never arise (attacking condition 4 structurally). Deadlock detection lets circular waits happen but periodically checks for them and breaks any that are found (accepting condition 4 but bounding its damage). A crucial distinction from an unrelated pathology is worth stating cleanly: starvation is a transaction perpetually failing to acquire a lock even though no cycle exists — for example, if the scheduler always favors other transactions. Deadlock is a structural graph property (a cycle); starvation is a fairness failure with no cycle required. Both need distinct fixes, and later remedies for one (e.g., always aborting the youngest transaction) can inadvertently create the other if not designed carefully.

Building the wait-for graph

The central data structure for detection is the wait-for graph $G = (V, E)$: vertices are active transactions, and there is a directed edge $T_i \to T_j$ if $T_i$ is blocked waiting to acquire a lock currently held by $T_j$. The graph is maintained incrementally by the lock manager:

• When $T_i$ requests a lock held (incompatibly) by $T_j$, add edge $T_i \to T_j$ and block $T_i$.
• When $T_j$ releases a lock and $T_i$ acquires it, remove edge $T_i \to T_j$.
• When a transaction commits or aborts, remove all its edges (incoming and outgoing).

Claim: the system is deadlocked if and only if the wait-for graph contains a directed cycle. Proof sketch. ($\Leftarrow$) Suppose a cycle $T_1 \to T_2 \to \cdots \to T_k \to T_1$ exists. By definition of the edge relation, $T_1$ cannot proceed until $T_2$ releases a lock, $T_2$ cannot proceed until $T_3$ releases a lock, ..., $T_k$ cannot proceed until $T_1$ releases a lock. Under 2PL no transaction releases a lock before it can proceed (locks are released only after the transaction resumes execution and reaches commit/abort). So no transaction on the cycle can ever make progress — this is precisely a deadlock. ($\Rightarrow$) Suppose the system is deadlocked: some non-empty set $S$ of transactions are permanently blocked. Each blocked transaction has at least one outgoing wait-for edge (it is waiting for some lock held by someone). Follow outgoing edges starting from any $T \in S$: since $S$ is finite and every transaction visited is also blocked (blocked transactions can only be waiting on other transactions that are, transitively, part of the stuck set — a transaction holding the needed lock and not blocked would eventually release it), the walk must revisit a transaction, producing a cycle. $\blacksquare$ This iff-characterization is what makes detection exact: no false positives, no false negatives, provided the graph is maintained correctly.

Detection algorithm

``` // Wait-for graph maintained by the lock manager as transactions // request, acquire, and release locks. structure WaitForGraph: nodes: set of active transaction IDs edges: set of (Ti, Tj) meaning "Ti waits for Tj" function ADD_WAIT(Ti, Tj): edges.add((Ti, Tj)) function REMOVE_TRANSACTION(Ti): edges.remove_all_incident_to(Ti) nodes.remove(Ti) // Run periodically (fixed interval) or when a new wait edge is added. function DETECT_DEADLOCK(graph): visited = {} // GRAY = on current DFS stack, BLACK = fully done cycle_found = [] function DFS(u, stack): visited[u] = GRAY stack.push(u) for each edge (u, v) in graph.edges: if visited[v] == GRAY: // v is an ancestor on the current path -> cycle idx = stack.index_of(v) cycle_found = stack[idx:] // extract the cycle return true if visited[v] is undefined: if DFS(v, stack): return true stack.pop() visited[u] = BLACK return false for each node u in graph.nodes: if visited[u] is undefined: if DFS(u, []): return cycle_found // a deadlock cycle return NONE // no deadlock function RESOLVE(cycle): victim = CHOOSE_VICTIM(cycle) // e.g., youngest transaction, // fewest locks held, least work done ABORT(victim) RELEASE_ALL_LOCKS(victim) REMOVE_TRANSACTION(victim) // update wait-for graph // remaining transactions in the cycle can now proceed ``` This is a standard depth-first-search cycle detector on a directed graph, with the coloring scheme WHITE (unvisited) / GRAY (in progress, on the recursion stack) / BLACK (finished) used to distinguish a back edge (to a GRAY node — a real cycle) from a cross/forward edge (to a BLACK node — no cycle through here). Real systems rarely rerun full detection from scratch on every lock request; instead they run it periodically (every few hundred milliseconds) or incrementally re-check only the portion of the graph reachable from the transaction that just got blocked, since a new edge is the only way a new cycle can appear.

Prevention: wait-die and wound-wait

An alternative to detection is to prevent cycles from forming at all, using a global order — the transaction's timestamp (assigned at start, monotonically increasing, so older transactions have smaller timestamps). When $T_i$ requests a lock held by $T_j$, one of two symmetric rules is applied:

Wait-die (non-preemptive — older transactions wait, never preempt): ``` if timestamp(Ti) < timestamp(Tj): // Ti is older Ti waits for Tj else: // Ti is younger Ti dies (aborts), restarts later with the SAME timestamp ```

Wound-wait (preemptive — older transactions preempt younger ones): ``` if timestamp(Ti) < timestamp(Tj): // Ti is older Ti wounds Tj: Tj is aborted (unless Tj already committing), Ti proceeds else: // Ti is younger Ti waits for Tj ``` Both schemes guarantee no deadlock. The key invariant: in wait-die, waiting always flows from younger timestamps waiting for effectively-younger — actually the invariant is that along any wait-for edge, timestamps strictly decrease in the direction of waiting (older waits for younger is impossible; the older one never waits, it kills). In wound-wait, along any wait-for edge, timestamps strictly increase (younger waits for older, and older transactions never wait — they wound). Either way, wait-for edges are consistent with a strict total order (timestamps, which are unique and never reused for a restarted transaction retaining its original stamp), so no cycle can form — a cycle would require timestamps to both increase and decrease around the loop, a contradiction. Both schemes require a restarted transaction to keep its original timestamp, which guarantees that a transaction restarted enough times eventually becomes the oldest in the system and stops being aborted — this is what prevents starvation, a subtlety many descriptions omit.

Detection (DFS cycle check). Let $V$ = number of active transactions (nodes) and $E$ = number of outstanding wait-for edges. Standard DFS visits every node once and every edge once:

Space is $O(V + E)$ for the adjacency representation plus $O(V)$ for the color array and recursion stack. Since in practice each transaction waits for at most a handful of locks at a time (bounded by concurrency degree), $E = O(V)$ in typical workloads, making detection effectively linear in the number of active transactions. Running detection on every single lock request would cost $O(V+E)$ each time, which is wasteful; production systems amortize this by running detection on a timer (e.g., every 1–5 seconds) or only triggering a check when a new wait edge is added (since only new edges can create new cycles, you only need to search for a cycle reachable from the newly blocked transaction, not re-scan the whole graph) — this localized recheck costs $O(V+E)$ in the worst case but is typically far cheaper.

Correctness of detection. Already proven above: cycle in wait-for graph $\iff$ deadlock. This is airtight provided the graph reflects the true, current locking state — a real engineering subtlety, since distributed systems must be careful about propagation delay (a phantom deadlock: a cycle appears to exist based on stale information, but has already resolved itself). Centralized, single-node lock managers avoid this entirely since the graph is updated atomically with the lock table under the same mutex.

Prevention (wait-die / wound-wait). No graph is maintained at all — checking a rule against two timestamps is $O(1)$ per lock conflict. The tradeoff is more aborts than strictly necessary: prevention schemes may abort a transaction even in situations where, had the request simply been queued, no cycle would ever have formed (Prevention is conservative: it forbids cycles by forbidding some non-cycles too). Detection is more permissive (it allows waiting until a cycle would actually occur) but pays the cost of graph maintenance and periodic scanning, plus the latency of only discovering the problem after it has already happened (transactions sit blocked until the next detection pass).

Timeout-based pseudo-detection. The cheapest fallback: abort any transaction that has waited longer than threshold $\tau$. This costs $O(1)$ bookkeeping per lock wait (a timer) but is neither necessary nor sufficient as a deadlock test — a transaction can wait past $\tau$ due to ordinary contention with no cycle (false positive, wasted abort), and a cycle can form and persist for less than $\tau$ before... no, actually a real cycle never resolves on its own, so eventually a true deadlock will trigger a timeout, but only after unnecessary delay, and short-lived high-contention (non-cyclic) waits are frequently misclassified as deadlocks. This is a heuristic traded for simplicity, common in systems where the overhead of a real wait-for graph is judged not worth it.

Victim selection and correctness of recovery. Aborting any transaction on the discovered cycle breaks that cycle (removing one node removes at least one edge from every cycle through it), so correctness of recovery is trivial — the harder engineering question is which victim minimizes wasted work and avoids repeatedly picking the same transaction (which would starve it). Common cost functions: amount of work already done (prefer to abort transactions that just started), number of locks held, number of transactions that would need to be aborted transitively. A well-designed victim-selection policy folds in "age" (like wait-die's timestamp) specifically to guarantee that a transaction is never picked as victim infinitely many times — otherwise deadlock recovery merely converts deadlock into perpetual starvation of one unlucky transaction.

Consider three transactions operating on accounts $A, B, C$ with exclusive locks under strict 2PL.

At $t_6$ the edge $T_3 \to T_1$ closes the cycle $T_1 \to T_2 \to T_3 \to T_1$. Running `DETECT_DEADLOCK` (as scheduled, say at $t_7$) performs DFS from $T_1$: ``` DFS(T1): color T1 GRAY, push [T1] edge T1 -> T2: T2 unvisited -> DFS(T2) DFS(T2): color T2 GRAY, push [T1, T2] edge T2 -> T3: T3 unvisited -> DFS(T3) DFS(T3): color T3 GRAY, push [T1, T2, T3] edge T3 -> T1: T1 is GRAY -> BACK EDGE -> cycle found cycle = stack[index_of(T1):] = [T1, T2, T3] return true return true return true return true result: cycle_found = [T1, T2, T3] ``` The scheduler now calls `CHOOSE_VICTIM([T1, T2, T3])`. Suppose $T_3$ has done the least work (just started, holds only lock on $C$, no writes yet applied). $T_3$ is aborted: its lock on $C$ is released, and the edge $T_2 \to T_3$ (and $T_3 \to T_1$) is removed. $T_2$ now acquires $C$ and proceeds to completion, then releases $B$; $T_1$ acquires $B$ and proceeds. The cycle is broken with a single, minimal-cost abort — exactly what the correctness argument guarantees (removing any one node from a cycle destroys that cycle).

Contrast with prevention (wound-wait). Suppose instead timestamps are assigned at start: $\text{ts}(T_1) = 100 < \text{ts}(T_2) = 105 < \text{ts}(T_3) = 110$ (lower = older). At $t_6$, when $T_3$ requests $A$ held by $T_1$: since $\text{ts}(T_3) > \text{ts}(T_1)$, $T_3$ is younger, so $T_3$ waits rather than wounding — wait, under wound-wait the requester must be older to wound; here $T_3$ (younger) is the requester and $T_1$ (older) holds the lock, so $T_3$ must wait. But at $t_5$, $T_2$ (younger, ts 105) requested $C$ held by $T_3$ (older is $T_2$? No — $\text{ts}(T_2)=105 < \text{ts}(T_3)=110$ means $T_2$ is older) — so $T_2$ wounds $T_3$, aborting $T_3$ immediately at $t_5$, before the cycle-closing edge at $t_6$ ever has a chance to form. The cycle is prevented structurally, not detected after the fact — illustrating the core tradeoff: prevention pays its cost earlier (an eager abort at $t_5$) in exchange for never needing a wait-for graph at all.

The foundational vocabulary of deadlock — mutual exclusion, hold-and-wait, no preemption, circular wait — originated in operating systems research on resource allocation, then was carried directly into database concurrency control once locking-based schedulers (2PL) became standard. The wait-die and wound-wait schemes were formalized as part of the broader theory of concurrency control developed alongside serializability theory in the 1970s, when database researchers needed provably deadlock-free alternatives to detection for systems where graph maintenance was too expensive.

Every production RDBMS with lock-based concurrency control — PostgreSQL, MySQL/InnoDB, Oracle, Microsoft SQL Server, IBM Db2 — ships a background deadlock detector that periodically scans the internal lock manager's wait graph and aborts a chosen victim, surfacing it to the application as a serialization error the app is expected to retry. Distributed and geo-replicated systems (e.g., distributed SQL databases like CockroachDB or Google Spanner-style systems) must additionally solve the distributed version of detection, where wait-for edges live on different machines and need a coordinator or a token-passing protocol to assemble a global picture without false phantom cycles. Prevention-style timestamp schemes appear in optimistic and hybrid concurrency control designs where the cost of maintaining a live graph is considered too high relative to occasional wasted restarts. Application frameworks that wrap database transactions (ORMs, connection pools) build automatic retry-on-deadlock logic directly into their transaction decorators, because deadlock — unlike a logic bug — is an expected, recoverable event in any sufficiently concurrent locking system, and understanding it precisely is what lets engineers write correct retry loops instead of treating it as a mysterious failure.

Ask the tutor: How would a wait-for graph detector need to change if the database used shared (read) locks in addition to exclusive (write) locks?