Concurrency Control

Deadlock Is a Wait-for Cycle

A cycle in the wait-for graph is a deadlock.

highlighted = computed this step

Deadlock is a wait-for cycle

A wait-for graph has one node per transaction and one edge from waiter to holder. Deadlock is detected by a graph cycle. Note: the verdict caption falls out of the cycle check.

cycle means deadlock\text{cycle means deadlock}

Cycle highlighted

The deadlock example has 2 wait-for edges and a cycle of length 2. Note: cycle edges are highlighted in the graph.

edges=2,cycle length=2\text{edges}=2,\quad \text{cycle length}=2

2PL and MVCC are exact protocol traces on tiny schedules; real lock managers, deadlock avoidance/timeouts, version garbage-collection, and isolation-level tuning are beyond these traces - no product claims.

Deadlock cycleitemmodeholderswaitersAXT1T2:XBXT2T1:X deadlock: yes; cycle: T1,T2T1T2

Acyclic wait contrast

The contrast schedule has cycle length 0. Note: a wait without a cycle is rendered with no highlighted cycle edges.

cycle length=0\text{cycle length}=0

2PL and MVCC are exact protocol traces on tiny schedules; real lock managers, deadlock avoidance/timeouts, version garbage-collection, and isolation-level tuning are beyond these traces - no product claims.

Acyclic waititemmodeholderswaitersAXT1T2:XBXT2- deadlock: noT1T2

Summary

The deadlock verdict is a deterministic wait-for cycle check. Note: 2PL and MVCC are exact protocol traces here; real lock managers, timeouts, garbage collection, and isolation tuning are beyond these traces.

deadlock by cycle\text{deadlock by cycle}