Killing Deadlocks Before They Form: Wait-Die vs Wound-Wait Schemes
In relational database systems running under Two-Phase Locking (2PL), deadlock is an inevitable side effect of concurrent lock acquisition.
Traditionally, databases employ Deadlock Detection : the engine builds a Wait-For Graph in memory, runs cycle-detection algorithms (e.g., Tarjan's or DFS), and selects a victim to abort when a cycle forms.
However, in ultra-high-throughput systems, constantly searching for cycles introduces significant locking overhead.
Instead, database engines can employ Timestamp-Based Deadlock Prevention : Wait-Die and Wound-Wait .
1. The Timestamp Precedence Rule
Every transaction T_i is assigned a monotonically increasing timestamp TS(T_i) when it begins.
If TS(T_i) < TS(T_j) , T_i is older (senior).
If TS(T_i) > TS(T_j) , T_i is younger (junior).
A deadlock requires a cyclic dependency chain:
T₁ → T₂ → ...…