Symptom
Two transactions transfer money. T1 moves 100 from A to B, T2 moves 50 from B to A. Both commit. The total across A and B changes.
You add a lock around each account update. The total is now preserved, but a report transaction reading both balances sometimes sees 100 in flight — debited from A, not yet credited to B. So you hold the locks longer. Now two transfers in opposite directions deadlock.
Each fix creates the next problem, and you have no way to tell when you are done. What you are missing is a definition of correct. “Concurrent transactions behave like serial ones” is the intent, but checking it requires knowing which interleavings are equivalent to which serial orders, and there are a lot of interleavings: three transactions of four operations each admit $\frac{12!}{(4!)^3} = 34{,}650$ schedules against only $3! = 6$ serial orders. Testing is hopeless. You need a criterion you can enforce.
Statement
Two operations conflict if they belong to different transactions, touch the same item, and at least one is a write. A schedule is conflict serializable if it can be transformed into a serial schedule by repeatedly swapping adjacent non-conflicting operations.
The conflict graph criterion. Build a graph with one node per transaction and an edge $T_i \to T_j$ whenever an operation of $T_i$ conflicts with and precedes an operation of $T_j$. The schedule is conflict serializable if and only if this graph is acyclic, and any topological order of it is an equivalent serial order.
Two-phase locking. If every transaction acquires all its locks before releasing any (a growing phase followed by a shrinking phase), then every schedule it produces is conflict serializable.
The pairing is the point. The first is a test on a completed schedule, which is useless at runtime because you cannot check a schedule you have not finished running. The second is a protocol enforceable locally by each transaction with no global knowledge, and it guarantees the test would have passed.
Argument
Why the acyclicity test is exactly right. Swapping adjacent non-conflicting operations never changes any transaction’s reads or the final database state, since the pair either touches different items or both only read. So conflict-equivalent schedules are genuinely interchangeable.
If the conflict graph is acyclic, topologically sort it and use bubble-sort-like adjacent swaps to bring the schedule into that order. Every swap you need is between non-conflicting operations, because a conflicting pair is exactly an edge and the sort respects all edges. If the graph has a cycle $T_1 \to T_2 \to \dots \to T_1$, then any equivalent serial schedule would need $T_1$ before $T_2$ before $\dots$ before $T_1$, which no total order provides.
Why 2PL implies acyclicity. Give each transaction its lock point: the instant it acquires its last lock, which exists and is unique because the two phases do not interleave.
Suppose $T_i \to T_j$ is a conflict edge. Then $T_i$ performed a conflicting operation on some item $x$ before $T_j$ did, so $T_i$ held a lock on $x$ that $T_j$ later needed and therefore $T_i$ released before $T_j$ acquired it. Since $T_i$ released a lock, $T_i$ was already in its shrinking phase, so its lock point precedes that release. And $T_j$ acquired a lock afterwards, so $T_j$’s lock point comes after. Hence every conflict edge points forward in lock-point order.
A cycle in the conflict graph would give a cycle in lock-point order on the real line, which is impossible. The graph is acyclic, so the schedule is conflict serializable — and serializable in lock-point order, which is a stronger and more useful statement than mere existence.
That the serialization order is the lock-point order is what makes 2PL feel principled instead of accidental. The protocol chooses the equivalent serial order, and it chooses it by the moment each transaction stopped acquiring.
Why plain 2PL is not enough in practice. 2PL gives serializability, not recoverability. If $T_1$ releases a lock during its shrinking phase, $T_2$ reads what $T_1$ wrote, and then $T_1$ aborts, $T_2$ has read a value that never existed — a dirty read — and must abort too, cascading.
Strict 2PL fixes it: hold all write locks until commit or abort. Rigorous 2PL holds all locks until commit. Essentially every lock-based database implements strict or rigorous 2PL, so “2PL” in a real system means the shrinking phase is a single instant at commit. That collapse is why deadlock, rather than cascading abort, is the failure mode you actually meet.
Deadlock is not a bug in 2PL, it is the cost of it. Two transfers in opposite
directions each hold one account and want the other. 2PL cannot prevent this
without either lock ordering or restricting concurrency. Real systems detect it:
PostgreSQL runs a wait-for-graph cycle detector after deadlock_timeout,
defaulting to one second, then aborts the cheapest victim. MySQL InnoDB detects
immediately on the wait-for graph. Abort and retry is the accepted answer, and
it is why serializable workloads need retry loops in application code.
Isolation levels are 2PL with locks released early, and the anomalies are exactly what that buys. This is the framing that makes the levels memorable rather than a table to be memorized.
| Level | Locking behaviour | Permits |
|---|---|---|
| Read uncommitted | no read locks, no write-lock respect | dirty read |
| Read committed | read locks released immediately after read | non-repeatable read |
| Repeatable read | read locks held to commit, no range locks | phantom |
| Serializable | full 2PL with range/predicate locks | nothing |
Every anomaly corresponds to a specific violation of the two-phase discipline. Releasing a read lock early is precisely what admits a non-repeatable read. Locking only existing rows, not the gaps between them, is precisely what admits a phantom, which is why InnoDB has next-key locks. The anomaly list is not arbitrary and does not need memorizing once you can derive it.
The optimistic alternative, and why it won in some places. Serializable
Snapshot Isolation takes no read locks at all. Each transaction reads a
consistent snapshot and the system detects, at commit, whether a dangerous
structure of read-write dependencies formed — specifically two consecutive
rw-antidependency edges, which Cahill showed is necessary for any
snapshot-isolation anomaly. PostgreSQL’s SERIALIZABLE is this, not 2PL, and
it gives full serializability with readers never blocking writers, at the cost of
aborts under contention rather than waits.
The relation to linearizability (T055) is the one people most often get
backwards. Serializability orders transactions and says nothing about real
time: a serializable database may legally order a transaction that committed an
hour ago after one committed a second ago. Linearizability orders single
operations and pins them to real time. Neither implies the other, and their
conjunction is strict serializability, which is what Spanner and FoundationDB
provide and what most people incorrectly assume SERIALIZABLE means.
Forbids
A cycle in the conflict graph, under any correct protocol. This is the complete characterization; there is nothing else to check.
Releasing a lock and then acquiring another, in a serializable transaction. That single violation breaks the lock-point argument and admits non-serializable schedules.
Deadlock-free 2PL without additional structure. Deadlock avoidance requires lock ordering, timeouts, or wound-wait style preemption. The protocol alone cannot promise progress.
Repeatable read preventing phantoms by itself. Row locks do not lock non-existent rows. Preventing a phantom requires predicate or range locks, and this is a real and common production surprise.
Does not forbid
It does not forbid non-conflict-serializable schedules that are nonetheless correct, and this is the standard over-reading. Conflict serializability is sufficient, not necessary; view serializability is strictly weaker and admits schedules with blind writes that conflict serializability rejects. It is NP-complete to test, which is why no system uses it, but the theoretical gap is real: a rejected schedule is not automatically a wrong one.
It does not require serializable isolation for correctness. Most applications run at read committed and are fine, because their invariants do not span the anomalies that level permits. PostgreSQL and Oracle default to read committed; MySQL defaults to repeatable read. The engineering question is which anomalies your invariants tolerate, not which level sounds safest.
It does not require locking. MVCC serves readers from versions so they never block writers. PostgreSQL, Oracle, and MySQL InnoDB are all MVCC, and their serializable levels use snapshot-based detection or extra locking on top rather than classical 2PL.
It does not mean serializable is unusably slow. For low-conflict workloads SSI costs very little, since the abort rate tracks actual conflict. FoundationDB and CockroachDB ship serializable as the only level, on the argument that weaker levels move the difficulty into application code where it is not checked.
It does not forbid distributed transactions. 2PL extends across nodes; the complication is atomic commit, which is two-phase commit, an unrelated protocol with a confusingly similar name. Spanner runs 2PL for writes plus Paxos for replication plus TrueTime for real-time order.
Boundary
- Sufficient, not necessary. View serializability is weaker and untestable in practice.
- Says nothing about deadlock or progress. Safety only.
- Item-level conflicts only. Predicates and ranges need explicit predicate locking; classical theory assumes a fixed set of items.
- No real-time guarantee. Serializability is not strict serializability.
- Anomalies outside the standard list exist. Write skew is permitted by snapshot isolation and is not any of the classic three, which is why the ANSI SQL anomaly-based definitions were shown by Berenson et al. to be inadequate as specifications.
The trade to carry: 2PL converts a global property nobody can check into a local discipline every transaction can follow, and it charges for it in deadlocks and waiting. Every weaker isolation level is the same protocol with the discipline relaxed at one specific point, and the anomaly you get is derivable from which point.