Classical Concurrency Control Theory

Pillar: concurrency-control-theory | Date: May 2026
Scope: Foundational CS theory applied to concurrent code modification: two-phase locking (2PL), multi-version concurrency control (MVCC), optimistic concurrency control (OCC) theoretical foundations, serializability, conflict vs data isolation, vector clocks and happened-before ordering, intent locks, lock compatibility matrices, and transaction isolation levels from database systems.
Sources: 31 gathered, consolidated, synthesized.

Table of Contents

1. Overview: The Three Families of Concurrency Control
2. Two-Phase Locking (2PL)
3. Multi-Version Concurrency Control (MVCC)
4. Optimistic Concurrency Control (OCC)
5. Timestamp Ordering (T/O) Protocol
6. Serializability Theory
7. Transaction Isolation Levels and Anomalies
8. Lock Compatibility Matrices
9. Multiple Granularity Locking and Intent Locks
10. Vector Clocks and Happened-Before Ordering
11. Deadlock Theory, Detection, and Prevention
12. Serializable Snapshot Isolation (SSI)
13. OS-Level Concurrency: Readers-Writers and File Locking

Section 1: Overview — The Three Families of Concurrency Control

Classical concurrency control theory partitions protocols into three families based on how they handle the fundamental tension between correctness and throughput. Pessimistic protocols (2PL and its variants) acquire locks before accessing data, paying upfront blocking costs to prevent conflicts. Optimistic protocols (OCC, timestamp ordering) operate freely on private copies or under timestamp discipline, paying a validation or abort cost at commit time. Multi-version protocols (MVCC) retain prior data versions so reads never block writes, at a storage overhead cost.^[1][3][2]

The correctness target is serializability — the highest isolation level, defined as a schedule equivalent to some serial execution. For approximately 30 years after its 1976 introduction, Two-Phase Locking was the dominant algorithm for achieving serializability in database systems.^[1][11]

Protocol Lineage and Theoretical Relationships

Key finding: Timestamp Ordering (T/O) provides the theoretical building blocks for both OCC and MVCC. OCC = T/O with all validation deferred to commit time; MVCC = T/O with multiple versions retained to allow reads to always succeed. Together with 2PL, these three form the complete foundation of classical concurrency control theory.^[31]

Section 2: Two-Phase Locking (2PL)

Two-Phase Locking is a pessimistic concurrency control method that guarantees conflict-serializability by dividing transaction execution into a growing phase (locks acquired only) and a shrinking phase (locks released only). Introduced in 1976 by K.P. Eswaran, J. Gray, R.A. Lorie, and I. Traiger, it remained the dominant serializability algorithm for approximately 30 years.^[1][11][20]

Core Protocol Mechanics

The protocol imposes one rule: "a transaction must never acquire a lock after it has released a lock."^[1] The lock point marks the moment all needed locks are acquired; after this point the transaction can only release locks.^[1][11] Two fundamental lock types govern access:

• Shared Lock (S / Read Lock): Multiple transactions may hold simultaneously; compatible with other S locks.
• Exclusive Lock (X / Write Lock): Only one transaction at a time; incompatible with all other lock types including other X locks.^[1][28]

2PL Protocol Variants

(Sources:^[11][20])

Conservative 2PL prevents deadlocks by eliminating the hold-and-wait condition — transactions must declare all read-sets and write-sets in advance. Rarely implemented in practice due to this advance-knowledge requirement.^[1][11][29]

SS2PL (Rigorous 2PL) is the most widely used variant in commercial database management systems. It provides the strongest consistency guarantees while simplifying recovery — a transaction effectively only has a growing phase until completion.^[1][11]

Theoretical Correctness

Key finding: Any schedule produced under the basic 2PL protocol is conflict serializable. The serialization order of transactions is determined by topological sort of the precedence graph of the schedule. This establishes 2PL as a sufficient condition for serializability — but not a necessary one: serializable schedules exist that no valid 2PL execution produces.^[1][11][20]

Known Limitations

• Deadlocks: Transactions can become stuck awaiting each other's locks; detection or prevention mechanisms are required.^[1]
• Cascading Rollbacks: In basic 2PL, failure of one transaction can cascade to others that read its uncommitted writes.^[11]
• Lock Contention: Competing for identical locks degrades throughput under high concurrency.^[1]
• Reader-Writer Interference: S locks are incompatible with X locks, causing read operations to block write operations and vice versa — a key contrast with MVCC.^[20][21]

Key Foundational References

• Eswaran, Gray, Lorie, Traiger (1976): Original 2PL paper^{[Eswaran 1976]}
• Bernstein, Hadzilacos & Goodman (1987): Concurrency Control and Recovery in Database Systems
• Gray & Reuter (1993): Transaction Processing: Concepts and Techniques
• Weikum & Vossen (2002): Transactional Information Systems^[1]

Section 3: Multi-Version Concurrency Control (MVCC)

MVCC is a non-locking concurrency control method that maintains multiple versions of data items simultaneously. Rather than overwriting data on write, MVCC creates a new version — readers access older committed versions while writers create newer ones. The fundamental property: readers never block writers; writers never block readers.^[2][12][21]

Historical Development

Core Mechanics: Version Chains and Snapshot Isolation

The DBMS maintains a version chain per logical tuple — a linked list of versions sorted by timestamp. Each version carries:^[12][21]

• Write Timestamp (WTS): Timestamp of the transaction that wrote this version
• Read Timestamp (RTS): Largest timestamp of any transaction that has read this version

A transaction always reads the latest version whose WTS ≤ TS(Tᵢ) — this is snapshot isolation.^[2][12][21]

Academic Classification of MVCC Methods

From Bernstein, Hadzilacos & Goodman (1987):^[12]

The Write Skew Anomaly: MVCC's Key Limitation

Most MVCC implementations provide Snapshot Isolation (SI) by default — not full serializability. The write skew anomaly exposes this gap: two concurrent transactions read overlapping data, each writes to a different part, and the combined result violates a constraint that neither write alone would violate. No write-write conflict is detected under SI; both transactions commit.^[2][12] Serializable Snapshot Isolation (SSI) was developed in 2008 to close this gap.^[30]

Garbage Collection Challenge

Obsolete versions accumulate and must be reclaimed. A version is reclaimable when no active transaction can see it, or when created by an aborted transaction.^[2][12][21] Key GC strategies:

• PostgreSQL VACUUM FREEZE: Stop-the-world traversal of entire tables; can cause operational pauses. Also faces the XID wraparound problem where 32-bit transaction IDs overflow.^[12]
• Undo logs (MySQL InnoDB, Oracle): Risk exhaustion under update-intensive workloads.^[12]
• Background GC threads: Some databases use continuous cleanup threads to avoid pauses.^[2]

A side benefit: without GC, MVCC supports time-travel queries — querying the database as of a past snapshot.^[2][12][21]

MVCC vs. 2PL Comparison

(Sources:^[2][21])

Real-World Implementations

Key finding: Many modern database systems combine MVCC for reads with locking for write-write conflicts — gaining the non-blocking read properties of MVCC while retaining the write-ordering guarantees of 2PL.^[21]

Section 4: Optimistic Concurrency Control (OCC)

OCC assumes transactions complete without conflict most of the time. Rather than acquiring locks, transactions operate freely on private data copies, then validate at commit time that no conflicts occurred. The approach is "optimistic" in that it relies primarily on transaction rollback as a control mechanism, "hoping" conflicts will not occur.^[3][13][22]

Historical Development

• First proposed: 1979 — H.T. Kung and John T. Robinson, Carnegie Mellon University; presented at VLDB 1979
• Seminal paper: 1981 — "On Optimistic Methods for Concurrency Control," ACM TODS Vol. 6, No. 2, pp. 213–226^{[Kung 1981]}
• Citation count: Over 1,556 citations — among the most influential papers in database systems theory^[13][22]

The Four Phases of OCC

(Sources:^[3][13][22])

Kung & Robinson Serializability Conditions

For transaction Tᵢ to precede Tⱼ in the equivalent serial order, at least one of the following must hold:^[3]

1. Tᵢ completes all writes before Tⱼ starts reading — zero overlap
2. write_set(Tᵢ) ∩ read_set(Tⱼ) = ∅, AND Tᵢ completes writes before Tⱼ starts writes
3. write_set(Tᵢ) ∩ (read_set(Tⱼ) ∪ write_set(Tⱼ)) = ∅, AND Tᵢ completes reads before Tⱼ completes reads

Validation Techniques

Performance Characteristics

Low-contention environments: OCC excels — transactions avoid lock management overhead and eliminate waiting periods, producing superior throughput compared to locking approaches.^[3][13]

High-contention environments: Performance degrades severely. Per Kung & Robinson: "repeatedly restarting transactions hurts performance significantly." Thrashing occurs when the same transactions repeatedly conflict and abort. Starvation is possible — a transaction with a long read phase must check write sets of all transactions that committed while it was active, potentially requiring unbounded buffer space.^[3][22]

Notable Implementations

Google App Engine Datastore, Apache Solr (via _version_ field), Elasticsearch (document updates), CouchDB (document revisions via _rev fields), MonetDB, Software Transactional Memory (STM) systems, DynamoDB and MongoDB (conditional updates), Mimer SQL, Rails and Grails web frameworks.^[13][22]

In web applications, HTTP's stateless architecture makes traditional locking impractical. OCC is implemented via ETags in HTTP headers, hidden form fields with checksums/tokens, and version numbers in database records.^[3]

Key finding: OCC eliminates deadlocks entirely (no locks held during execution) and avoids all blocking, but at the cost of potential transaction restarts. The 1981 Kung & Robinson paper spawned Snapshot Isolation, Serializable Snapshot Isolation (SSI), and Software Transactional Memory (STM) — the three most important descendants in modern concurrency control.^[3][22]

Section 5: Timestamp Ordering (T/O) Protocol

Timestamp Ordering is a concurrency control protocol where the DBMS uses timestamps — rather than locks — to determine the serialization order of transactions. Each transaction Tᵢ receives a unique, monotonically increasing timestamp TS(Tᵢ). Classified as optimistic in that conflicts are assumed rare, but unlike OCC, conflicts trigger immediate abort rather than deferred validation.^[9][31]

Per-Data-Item Timestamps and Protocol Rules

Each data item Q maintains two timestamps:^[9][31]

• WTS(Q): Timestamp of the most recent successful write to Q
• RTS(Q): Timestamp of the most recent successful read of Q

(Sources:^[9][31])

Important limitation: Every read requires writing a new RTS(Q) value — every read becomes a write operation, creating significant overhead.^[9][31]

The Thomas Write Rule (1979)

Robert H. Thomas (1979) — "A majority consensus approach to concurrency control for multiple copy databases," ACM TODS 4(2): 180–209 — proposed ignoring outdated writes rather than aborting them:^[9]

The Thomas Write Rule trades conflict-serializability for view-serializability, gaining concurrency at the cost of a harder correctness check — determining view-serializability is NP-complete.^[9]

Strict Timestamp Ordering

To avoid cascading rollbacks, the strict variant delays (rather than aborts) operations that would violate timestamp order, executing them once all conflicting operations of older transactions have committed or aborted.^[31]

T/O vs. 2PL Comparison

Key finding: T/O provides the theoretical bridge between locking-based and version-based concurrency. MVCC is a multiversion extension of T/O that eliminates most read violations by allowing reads to always find an appropriate older version — transforming aborts into version selects.^[9][31]

Section 6: Serializability Theory

Serializability is the fundamental correctness criterion for concurrent database transactions: a schedule is serializable if it is equivalent to some serial schedule — i.e., it produces the same result as if transactions executed one at a time. It is the highest level of isolation between transactions.^[4][14][23] A schedule (or history) is the ordered list of operations from multiple transactions: reads (r₁[x]), writes (w₁[x]), commits (c₁), and aborts (a₁).^[4]

Conflict Classification

Two operations are in conflict if and only if: (1) they belong to different transactions, (2) at least one is a write, and (3) they access the same object. Conflicting operations are non-commutative — swapping their order changes the outcome.^[4][14]

Conflict Serializability and the Precedence Graph

Two schedules are conflict-equivalent if they maintain identical transaction actions and identical ordering of every conflicting operation pair. A schedule is conflict-serializable when its precedence graph is acyclic.^[4][14][23]

Precedence graph construction: one node per transaction; directed edge Tᵢ → Tⱼ if Tᵢ has a conflicting operation that precedes one in Tⱼ. A topological sort on the acyclic graph yields the equivalent serial schedule. This is the foundational theorem backing both 2PL correctness proofs and SSI cycle detection.^[4][14]

View Serializability

A weaker equivalence that requires: (1) identical initial value reads, (2) preserved read-from relationships, and (3) matching final write assignments. All conflict-serializable schedules are view-serializable; the converse is false — view-serializable schedules with blind writes exist that are not conflict-serializable. Determining view-serializability is NP-complete, which is why practical systems target conflict-serializability exclusively.^[4][14][23]

Schedule Containment Hierarchy

Recovery Classifications

Methods for Enforcing Conflict Serializability

1. Two-Phase Locking (2PL) — proven sufficient condition; lock compatibility enforces conflict ordering^[14]
2. Timestamp Ordering (TO) — orders operations by transaction timestamp; aborts violations^[14]
3. Serializable Snapshot Isolation (SSI) — MVCC-based; detects dangerous structures in the dependency graph^[14]
4. Abort cycles — abort any transaction forming a cycle in the precedence graph^[14]

Strict Serializability in Distributed Systems

Even combining standard serializability and linearizability can still result in unexpected anomalies such as causal reversal. A stale read — failing to see effects of a completed write — is common in distributed systems. Strict serializability adds real-time ordering requirements to ensure transactions respect wall-clock ordering, eliminating stale reads.^[23]

Industry Reality on Serializability Adoption

Key finding: In a survey of 18 SQL and "NewSQL" databases, only 3 of 18 provided serializability by default, and 8 — including Oracle and SAP — did not offer full serializability at all. Oracle's "SERIALIZABLE" isolation mode actually provides Snapshot Isolation, not true serializability.^[4][14][23]
Primary source: Bailis, P., Fekete, A., Ghodsi, A., Hellerstein, J.M., and Stoica, I. (2013). Highly Available Transactions: Virtues and Limitations. Proceedings of the VLDB Endowment 7(3):181–192.

Section 7: Transaction Isolation Levels and Anomalies

Isolation is the "I" in ACID. The four ANSI/ISO SQL standard isolation levels trade concurrency for correctness: lower isolation yields higher concurrency and more anomalies; higher isolation yields fewer anomalies with greater resource consumption.^[8][17]

ANSI SQL Anomaly Definitions (Formal Notation from Berenson et al. 1995)

Anomaly Prevention by Isolation Level

(Sources:^{[8][14][17][23][26]})

Locking Implementation of Isolation Levels

Additional Anomalies Beyond the ANSI Standard

Berenson et al. 1995 (ACM SIGMOD) identified phenomena missing from the original ANSI specification:^[26][8][17]

The Berenson et al. 1995 Critique

Authors: Hal Berenson, Philip A. Bernstein, Jim Gray, Jim Melton, Elizabeth J. O'Neil, Patrick E. O'Neil. Published ACM SIGMOD 1995. Key findings:^{[8][17][26][Berenson 1995]}

1. ANSI definitions are ambiguous — strict and broad interpretations both have weaknesses
2. ANSI definitions are incomplete — miss Dirty Write (P0) entirely
3. Definitions "rely in subtle ways on an assumption that a locking schema is used" — rendering semantics ill-defined for OCC or MVCC systems
4. Even under strictest interpretation, ANSI anomalies don't cover all isolation failures
5. Snapshot Isolation is not captured by any ANSI level
6. Oracle's "SERIALIZABLE" mode actually provides Snapshot Isolation

The paper formalized Cursor Stability (between READ COMMITTED and REPEATABLE READ; prevents lost update for cursor operations) and Snapshot Isolation as explicit levels.^[17][26]

Conflict Isolation vs. Data Isolation

Two distinct theoretical frameworks define what it means for a concurrency control protocol to be "correct," and they are not equivalent. Conflict-based isolation, exemplified by 2PL, prevents conflicting operations (read-write, write-read, write-write pairs on the same object from different transactions) from interleaving. A schedule is correct under this framework if and only if its precedence graph is acyclic — i.e., it is conflict-serializable.^[4][14] Data-based (anomaly-based) isolation, the framework of the ANSI SQL standard and its critique by Berenson et al. 1995, defines correctness by the absence of specific observable anomalies: dirty reads (A1), fuzzy reads (A2), phantoms (A3), and the additional phenomena (P0, P4, A5A, A5B) not captured by the original ANSI definitions.^[8][26]

The two frameworks are not equivalent. Conflict-serializability implies anomaly-freedom: any conflict-serializable schedule is free of all classical ANSI anomalies. But anomaly-freedom does not imply conflict-serializability. The canonical example is Snapshot Isolation: SI prevents dirty reads (A1), fuzzy reads (A2), and phantoms (A3) — satisfying the ANSI SERIALIZABLE anomaly criteria in their strict interpretation — yet SI is not conflict-serializable, because it permits write skew (A5B). Two concurrent transactions can each read overlapping data, write to disjoint parts, and both commit under SI without any write-write conflict being detected; the resulting schedule cannot be produced by any serial execution. This is precisely the gap that motivated Berenson et al.’s 1995 critique — the ANSI definitions, relying implicitly on locking semantics, fail to capture SI as a distinct isolation level — and the subsequent development of Serializable Snapshot Isolation (SSI) in 2008 to restore full conflict-serializability without sacrificing SI’s non-blocking read properties.^{[8][17][26][30]}

Gray (1976) Degrees of Consistency — Historical Precursor

Gray et al. 1976 introduced "degrees of consistency," the precursor to SQL isolation levels:^[7][18][24]

Key finding: Snapshot Isolation is strictly stronger than READ COMMITTED and incomparable to REPEATABLE READ — it prevents read skew (which REPEATABLE READ at the row level does not), but permits write skew (which SERIALIZABLE prevents). This incomparability was the central motivation for Berenson et al.'s critique.^[8][17][26]

Section 8: Lock Compatibility Matrices

Lock compatibility matrices formalize which lock types can be held simultaneously by different transactions. The matrix directly enforces conflict-serializability: incompatible lock requests block the requesting transaction, preventing out-of-order conflicting operations.^[1][28]

Basic S/X Lock Compatibility

(Sources:^[1][11][28])

Lock acquisition rules (Berkeley CS186 formulation):^[28]

1. Transactions must acquire S lock before reading
2. Transactions must acquire X lock before writing
3. Transactions cannot acquire new locks after releasing any lock — this is the 2PL constraint that enforces serializability

If a requested lock is incompatible with a held lock, the requesting transaction waits until all incompatible locks are released.^[28]

Lock Upgrades and Downgrades

Upgrading: Conversion from S to X lock. The Lock Manager places upgrade requests at the front of the queue — ahead of new S lock requests — to reduce starvation risk for upgrading transactions.^[28]

Downgrading: Conversion from X to S lock; allowed during the shrinking phase.^[28]

Connection Between Lock Compatibility and Conflict Serializability

The three conflict types map directly to incompatibilities in the matrix:^[28]

• RW conflicts: X lock prevents concurrent S lock acquisition
• WR conflicts: S lock prevents concurrent X lock acquisition
• WW conflicts: X lock prevents any concurrent X lock acquisition

Full Six-Mode Compatibility Matrix (with Intention Locks)

For hierarchical resource locking, six lock modes are required:^[6][16][28]

(Sources:^[6][16][28])

Key observations from Gray 1976:^[7][18]

• IS and IS are compatible — both intend to read different descendants
• IX and IX are compatible — both intend to modify different descendants
• IX and S are incompatible — one intends fine-grained writes; the other has taken a coarse read
• SIX and SIX are incompatible — both would take exclusive locks below

Some sources (raw_24) present a 5-mode matrix omitting NL, treating "no lock" as implicit rather than a named mode. Both representations are equivalent.^[24]

Key finding: The lock compatibility matrix is the algorithmic heart of 2PL: the three conflict types (RW, WR, WW) that define conflict-serializability map one-to-one onto incompatibilities in the S/X matrix, making the matrix + 2PL protocol a complete mechanical enforcement of conflict-serializable schedules.^[28]

Section 9: Multiple Granularity Locking and Intent Locks

Multiple Granularity Locking (MGL) allows transactions to lock data at different levels of a resource hierarchy — from fine-grained individual rows to coarse-grained entire tables. Without MGL, locking a table exclusively would require scanning all rows for existing locks: O(n) per check. With intent locks on the parent node, conflict detection becomes O(1).^[6][16][24]

Foundational Papers

• Gray, Lorie, Putzolu (1975) — "Granularity of Locks in a Shared Data Base," 1st VLDB Conference, pp. 428–451: introduced the intent lock concept
• Gray, Lorie, Putzolu, Traiger (1976) — "Granularity of Locks and Degrees of Consistency in a Shared Data Base," IFIP Working Conference on Modelling of Data Base Management Systems, pp. 695–723: combined intent locks with degrees of consistency (the isolation level precursor)^{[6][7][16][18]}

The Core Tension in Lock Granularity

Database resource hierarchy: Database → Files/Tables → Pages → Records/Rows → Fields^[6][16]

The Six Lock Modes

Lock Acquisition and Release Protocol

Acquisition direction: Top-down (root to leaf)
Release direction: Bottom-up (leaf to root) — a node can only be unlocked after all its children are unlocked.^{[6][7][16][18][24]}

For DAGs (nodes with multiple parents): before requesting IX, SIX, or X, all immediate parent nodes must hold IX or greater — not just one.^[24]

Correctness and Lock Escalation

Gray et al. prove that if two lock graphs are compatible, the implicit locks on the leaves are also compatible — the intent-lock hierarchy is provably equivalent to naive leaf-level locking without the O(n) overhead.^[24] If too many fine-grained locks accumulate, the DBMS can escalate to a coarser granularity (e.g., row locks → table lock) to reduce overhead.^[24]

Real-World Implementations

Key finding: The fundamental insight of Multiple Granularity Locking — "announce intentions at coarsest granularity, execute at finest" — reduces coarse-grained conflict detection from O(n) leaf scans to O(1) parent-node checks, making scalable fine-grained locking practical in production database systems.^[6][16]

Section 10: Vector Clocks and Happened-Before Ordering

In distributed systems with no global clock, ordering events across nodes requires logical time. The foundational insight from Lamport (1978): "It is not important that all processes agree on what the actual time is, but that they agree on the order in which events occur."^[5][15][25]

The Happened-Before Relation (Lamport 1978)

Formalized by Leslie Lamport in "Time, Clocks, and the Ordering of Events in a Distributed System" (CACM 21(7), 1978). The happens-before relation → is defined by:^[5][15][25]

1. If a and b are events in the same process and a precedes b, then a → b
2. If a is the sending of a message and b is its receipt, then a → b
3. Transitivity: a → b and b → c implies a → c
4. If neither a → b nor b → a, then a and b are concurrent (denoted a ↔ b or a ∥ b)

Lamport Clocks: Scalar Logical Time

A numerical counter per process; rules:^[5][15][25]

1. Increment local counter before each event
2. When sending a message, attach current counter value
3. When receiving a message with timestamp t: set local counter to max(local, t) + 1

Key property: If a → b then C(a) < C(b).
Critical limitation: The converse does NOT hold. If C(a) < C(b), we CANNOT conclude a → b. Lamport clocks cannot detect concurrency — only enforce known ordering.^[5][15][25]

Vector Clocks: Complete Causal Tracking

A vector clock is an array of N logical clocks — one per process in an N-process system. Process Pᵢ maintains vector VCᵢ where VCᵢ[i] counts Pᵢ's own events and VCᵢ[j] records what Pᵢ knows about Pⱼ's event count.^[5][15][25]

Algorithm:

1. Initialize all clocks to [0, 0, …, 0]
2. Internal events: Pᵢ increments VCᵢ[i] before executing
3. Send message: Pᵢ increments VCᵢ[i]; attaches current VCᵢ as timestamp ts(m)
4. Receive message: Pⱼ sets VCⱼ[k] ← max(VCⱼ[k], ts(m)[k]) for each k, then increments VCⱼ[j]

Causality Detection via Vector Comparison

Example: [2,3,1] vs [3,0,0] — first slot of second is greater (3>2) but second slot of first is greater (3>0). Neither dominates → concurrent events, flag as potential conflict.^[5][15]

The complete bidirectional property: VC(a) < VC(b) if and only if a happened-before b. This is what Lamport clocks cannot provide — vector clocks enable true conflict detection, not just ordering.^[5][15]

Lamport vs. Vector Clocks Comparison

(Sources:^[5][15][25])

Historical Development

• Lamport (1978): Scalar logical clocks
• Colin Fidge (1988): Independently developed vector time generalization
• Friedemann Mattern (1988): Independently developed vector clocks, established mathematical properties
• At least 6 papers independently developed the concept; Fidge and Mattern are the canonical citations for naming and formalizing "vector clocks"^[5][15][25]

Applications in Concurrency Control

• Amazon Dynamo: Version vectors for conflict detection in key-value storage^[25]
• Riak: Vector clocks for causal tracking of object versions^[25]
• CouchDB: Revision vectors for MVCC across replicas^[5]
• Git: DAG structure equivalent to vector clocks for file history and merge conflict detection^[5][25]
• Collaborative editing: Operational Transformation (OT) and CRDTs use causality tracking for concurrent document modifications^[25]
• Parallel code modification: When two agents modify independent files, vector clocks determine whether changes are concurrent (potentially conflicting) or causally ordered (safe to chain)^[25]

Relationship to Concurrency Control Theory

Happened-before provides the formal foundation for detecting write-write conflicts in distributed systems. The partial order defined by happened-before maps directly to the serializability graph concept. In MVCC distributed databases, each write carries its vector; when replicas exchange versions, if neither vector dominates the other, the writes were concurrent — the store keeps both as siblings for application-level merging.^[25]

Scaling Concerns and Variants

Vector clock size grows linearly with the number of processes — a real overhead in large, dynamic clusters.^[5][15] Variants addressing this:

Key finding: Vector clocks are the minimum logical data structure that enables complete bidirectional causality detection in distributed systems. Lamport clocks can establish a total order but cannot distinguish causal precedence from concurrence — the distinction that matters for conflict detection in parallel code modification, distributed databases, and CRDT-based collaborative editing.^[5][15]

Section 11: Deadlock Theory, Detection, and Prevention

A deadlock occurs when two or more transactions each hold resources the other needs, creating a standstill where none can proceed. Classic example: Transaction A holds Resource 1 and waits for Resource 2; Transaction B holds Resource 2 and waits for Resource 1.^[10][29]

The Four Necessary Conditions (Coffman Conditions)

A deadlock can only occur when all four conditions hold simultaneously — breaking any single condition prevents deadlock:^[10][29]

1. Mutual Exclusion: Only one transaction can hold a particular resource at a time
2. Hold and Wait: Transactions holding resources may request additional resources held by others
3. No Preemption: Resources cannot be forcibly taken from the holding transaction
4. Circular Wait: A cycle of transactions exists where each waits for a resource held by the next

Deadlock Detection: Wait-For Graph (WFG)

The wait-for graph is a directed graph where nodes are active transactions and an edge Tᵢ → Tⱼ means Tᵢ is waiting for a lock held by Tⱼ. A cycle in the graph indicates a deadlock.^[10][29]

Example cycle: T1 waits for T3's lock on X; T3 waits for T2's lock on Y; T2 waits for T1's lock on Z → deadlock.^[10]

Limitation: Suitable only for systems where transactions are lightweight with few resource instances. In distributed systems, deadlocks span multiple nodes and require a global wait-for graph with a central coordinator — or distributed detection algorithms.^[10]

Deadlock Resolution After Detection

Victim selection criteria: minimum work done, fewest resources held, fewest remaining operations, lowest rollback cost.^[29] Recovery options:

• Total rollback: Abort entire transaction, restart from beginning
• Partial rollback: Roll back to a savepoint that avoids the deadlock^[10]

Timestamp-Based Deadlock Prevention Protocols

Both Wait-Die and Wound-Wait assign priorities based on transaction timestamps — older transaction = lower timestamp = higher priority. In both protocols, the younger transaction is always aborted.^[10][29]

(Sources:^[10][29])

Starvation prevention: Rolled-back transactions restart with the same timestamp — not a new one. This means they eventually become the oldest active transaction and receive highest priority, ensuring progress.^[29]

No-Wait Scheme: If a transaction cannot immediately acquire all needed locks, it aborts and retries — no waiting. Eliminates deadlock by eliminating the hold-and-wait condition entirely.^[10]

Conservative 2PL as Deadlock Prevention

Conservative 2PL prevents deadlocks by requiring all locks to be acquired before execution begins. If a transaction cannot acquire all needed locks, it waits without holding any — eliminating hold-and-wait. Requires advance declaration of all data access patterns, making it impractical for most database workloads.^[10][29]

Deadlock Avoidance

Deadlock avoidance tests each proposed lock acquisition before granting it. If granting the lock could lead to a future deadlock state, the request is denied — the transaction must wait or abort without holding any conflicting resources.^[10] This strategy requires advance knowledge of each transaction’s future resource needs, making it impractical for most database workloads. In practice, detection is generally preferred: allow deadlocks to occur, then detect and resolve them reactively via the wait-for graph.

Distributed Deadlock Handling

Deadlock, Livelock, and Starvation Distinguished

Relationship to Concurrency Control Methods

• 2PL: Inherently enables deadlocks — two transactions can hold complementary locks and each request the other's^[29]
• MVCC: Reduces deadlocks — readers don't acquire shared locks, eliminating reader-writer lock cycles^[29]
• OCC: Eliminates deadlocks entirely — no locks held during execution, so no lock-based cycles possible^[29]
• SS2PL: Reduces cascading rollbacks but does not eliminate deadlocks^[29]

Key finding: Both Wait-Die and Wound-Wait prevent both deadlock and starvation — the same timestamp reuse on restart ensures eventual progress. The key difference is whether the older or younger transaction plays the active role: in Wait-Die, old waits and young dies; in Wound-Wait, old wounds (preempts) young, and young waits.^[10][29]

Section 12: Serializable Snapshot Isolation (SSI)

Serializable Snapshot Isolation closes the gap between Snapshot Isolation and full serializability without introducing reader-writer blocking. It was proposed in the landmark paper: Michael J. Cahill, Uwe Röhm, and Alan D. Fekete. 2008. "Serializable isolation for snapshot databases." SIGMOD '08, pp. 729–738.^{[30][Cahill 2008]}

The Write Skew Problem That Motivated SSI

Until Cahill et al. 2008, the only ways to prevent write skew under Snapshot Isolation were: (1) modify applications with artificial locking, (2) introduce fake update conflicts, or (3) carefully analyze all transaction pairs — all requiring deep application-level knowledge and fragile maintenance.^[30]

Classic Write Skew Example (Cahill et al. 2008): Two bank balances V1 and V2 with constraint V1 + V2 ≥ 0. Both start at $100:^[30]

• T1: Reads V1=$100, V2=$100; withdraws $200 from V1; checks constraint ($0 ≥ 0); commits
• T2: Reads V1=$100, V2=$100; withdraws $200 from V2; checks constraint ($0 ≥ 0); commits
• Result: V1=-$100, V2=-$100 — constraint violated. Neither transaction saw the other's write.

Why 2PL prevents this: Under 2PL, T1 holds S locks on V1 and V2; T2's attempt to acquire X lock on V2 is blocked by T1's S lock — transactions must serialize. Under SI without SSI, both transactions read from independent snapshots (no locks held), both proceed, both commit.^[30]

The SSI Detection Mechanism

SSI detects "dangerous structures" in the MVCC serialization graph:^[30]

• A dangerous structure = two consecutive rw anti-dependency arcs in the MV-serialization graph
• This structure is a necessary condition for a cycle (non-serializable execution)
• Detecting the structure → abort one transaction → prevent the cycle

The problem is reduced from detecting entire cycles (expensive global graph traversal) to detecting specific two-arc structures (cheap per-transaction tracking). SSI is an optimistic technique: transactions continue in hopes everything will be fine, aborting only when a dangerous structure is detected.^[30]

SSI vs. 2PL

(Sources:^[30])

PostgreSQL SSI Implementation (v9.1, 2011)

Based on Dan Ports (VLDB 2012) extending Cahill et al., PostgreSQL's implementation added:^[30]

• Integration with replication, crash recovery, and two-phase commit
• Subtransactions and savepoints
• Memory bounding via transaction summarization (bounded memory even with many concurrent transactions)
• Phantom handling via SIREAD locks on index ranges — predicate read/write conflicts to catch phantom-based write skew

Limitations of SSI

• False positives remain — some non-conflicting transactions are aborted due to conservative detection^[30]
• B-tree level conflicts inflate abort rates^[30]
• Adapting to distributed systems is non-trivial^[30]

Formal Foundation

Snapshot Isolation was first formally defined in Berenson et al. 1995. SSI builds directly on this foundation — taking SI's favorable read-write non-blocking properties and MVCC storage model, then adding the minimum detection machinery required for full serializability guarantees.^[30]

Key finding: SSI is the first practical algorithm to achieve full serializability without introducing any read-write lock conflicts. It is categorically superior to 2PL on read-write contention (neither direction blocks) while being essentially equivalent in the absence of conflicts — making it the theoretically optimal isolation mechanism for mixed workloads as of 2011.^[30]

Section 13: OS-Level Concurrency — Readers-Writers Problem and File Locking

The theoretical foundations of database concurrency control are mirrored at the operating system level, where the same fundamental correctness problems appear in file access coordination.^[19][27]

The Readers-Writers Problem

Formalized by Courtois, Heymans, and Parnas in 1971, "Concurrent Control with 'Readers' and 'Writers'" (CACM). The constraint: multiple readers may access a shared resource simultaneously (reads are non-destructive), but no thread may access while a writer is active.^[19]

This maps directly to the S/X lock distinction: Readers ↔ Shared (S) locks; Writers ↔ Exclusive (X) locks.^[19]

Priority Policies

Advanced OS Solutions

Read-Copy-Update (RCU): Wait-free for readers. Writers copy data, modify the copy, atomically swap the pointer. Readers see either old or new version but never partial state. Used extensively in the Linux kernel.^[19][27]

Seqlock (Linux kernel): Optimized for few writers. Readers note a sequence counter before and after reading; if the counter changed, a write occurred and the read is retried (OCC-style validation). Writers increment counter: odd = writing in progress, even = complete.^[19]

File Locking: Historical Origins and OS Primitives

IBM pioneered file locking in 1963 for mainframe OS/360 ("exclusive control"). The concept became universal across all major operating systems.^[27]

Advisory vs. Mandatory locking: Unix/Linux defaults to advisory locking — processes voluntarily acquire and check locks; non-cooperating processes are not blocked. Windows uses mandatory semantics — the OS enforces locking automatically, blocking conflicting accesses regardless of cooperation.^[27]

File System Granularity

A "lock" in file systems may be associated with one or more data blocks, files, directories, volumes, or disk drives. Most OSes support record locking: individual records within a file may be locked independently, enabling higher concurrency for update-intensive file applications.^[27]

2PL in the OS Scheduler Context

2PL is applied at the OS level: the scheduler acquires all necessary locks in the growing phase and releases them in the shrinking phase — checking each operation for conflicts with existing locks before granting or delaying.^[27]

Theoretical Unification

File system locking implements the same fundamental concepts as database concurrency control:^[27]

• Shared/Exclusive locks ≡ Database S/X locks
• Record-level locking ≡ Row-level database locks
• Byte-range locking ≡ Partial object locking
• Two-phase locking discipline ≡ Database 2PL protocol

NFS portability: NFS (Network File System) has historically poor lock support across network boundaries — a significant operational difference from local file system locking that forces distributed applications to implement application-level coordination.^[27]

Key finding: The theoretical foundations of concurrency control are domain-independent: the S/X lock compatibility matrix, two-phase locking discipline, and readers-writers priority policies appear identically in OS file locking (1963), database systems (1976), and distributed key-value stores (2007+). Only the granularity, advisory/mandatory semantics, and network-transparency requirements differ across domains.^[19][27]

References

1. Eswaran, K.P., Gray, J.N., Lorie, R.A., and Traiger, I.L. (1976). The notions of consistency and predicate locks in a database system. Communications of the ACM 19(11):624–633. doi:10.1145/360363.360369
2. Gray, J.N., Lorie, R.A., Putzolu, G.R., and Traiger, I.L. (1976). Granularity of locks and degrees of consistency in a shared database. In Proceedings of the IFIP Working Conference on Modelling of Data Base Management Systems, pp. 695–723.
3. Reed, D.P. (1978). Naming and synchronization in a decentralized computer system. Ph.D. dissertation, Massachusetts Institute of Technology.
4. Kung, H.T. and Robinson, J.T. (1981). On optimistic methods for concurrency control. ACM Transactions on Database Systems 6(2):213–226. doi:10.1145/319566.319567
5. Berenson, H., Bernstein, P., Gray, J., Melton, J., O’Neil, E., and O’Neil, P. (1995). A critique of ANSI SQL isolation levels. In Proceedings of ACM SIGMOD International Conference on Management of Data, pp. 1–10. doi:10.1145/223784.223785
6. Cahill, M.J., Röhm, U., and Fekete, A.D. (2008). Serializable isolation for snapshot databases. In Proceedings of ACM SIGMOD International Conference on Management of Data (SIGMOD ’08), pp. 729–738. doi:10.1145/1376616.1376690
7. Bailis, P., Fekete, A., Ghodsi, A., Hellerstein, J.M., and Stoica, I. (2013). Highly available transactions: Virtues and limitations. Proceedings of the VLDB Endowment 7(3):181–192. doi:10.14778/2732232.2732237

Sources

The following 31 source documents are the consolidated research corpus for this pillar. Inline citations [1]–[31] link to these entries.

1. Two-Phase Locking — Wikipedia. https://en.wikipedia.org/wiki/Two-phase_locking
2. Multiversion Concurrency Control — Wikipedia. https://en.wikipedia.org/wiki/Multiversion_concurrency_control
3. Optimistic Concurrency Control — Wikipedia. https://en.wikipedia.org/wiki/Optimistic_concurrency_control
4. Serializability — Wikipedia. https://en.wikipedia.org/wiki/Serializability
5. Vector Clock — Wikipedia. https://en.wikipedia.org/wiki/Vector_clock
6. Multiple Granularity Locking — Wikipedia. https://en.wikipedia.org/wiki/Multiple_granularity_locking
7. Gray, J.N., Lorie, R.A., Putzolu, G.R., and Traiger, I.L. (1976). Granularity of Locks and Degrees of Consistency in a Shared Database. Rendered at https://mwhittaker.github.io/papers/html/gray1976granularity.html
8. Isolation (database systems) — Wikipedia. https://en.wikipedia.org/wiki/Isolation_(database_systems)
9. Timestamp-Based Concurrency Control — Wikipedia. https://en.wikipedia.org/wiki/Timestamp-based_concurrency_control
10. Wait-For Graph — Wikipedia. https://en.wikipedia.org/wiki/Wait-for_graph
11. Two-Phase Locking — Wikipedia (second corpus copy; adds variants table). https://en.wikipedia.org/wiki/Two-phase_locking
12. Multiversion Concurrency Control — Wikipedia (second corpus copy; adds academic classification, XID wraparound). https://en.wikipedia.org/wiki/Multiversion_concurrency_control
13. Optimistic Concurrency Control — Wikipedia (second corpus copy; adds implementations list). https://en.wikipedia.org/wiki/Optimistic_concurrency_control
14. Database Transaction Schedule (Serializability) — Wikipedia (second corpus copy; adds formal notation). https://en.wikipedia.org/wiki/Serializability
15. Vector Clock — Wikipedia (second corpus copy; adds algorithm details, extensions). https://en.wikipedia.org/wiki/Vector_clock
16. Multiple Granularity Locking — Wikipedia (second corpus copy; adds NL mode detail). https://en.wikipedia.org/wiki/Multiple_granularity_locking
17. Isolation (database systems) — Wikipedia (second corpus copy; adds Cursor Stability, SSI mention). https://en.wikipedia.org/wiki/Isolation_(database_systems)
18. Gray 1976 — Granularity of Locks (second corpus copy; adds detailed compatibility matrix entries). https://mwhittaker.github.io/papers/html/gray1976granularity.html
19. Readers–Writers Problem — Wikipedia. https://en.wikipedia.org/wiki/Readers–writers_problem
20. Two-Phase Locking — Wikipedia (third corpus copy; adds 1976 historical context, 2PL vs 2PC). https://en.wikipedia.org/wiki/Two-phase_locking
21. Multiversion Concurrency Control — Wikipedia (third corpus copy; adds MVCC vs 2PL comparison). https://en.wikipedia.org/wiki/Multiversion_concurrency_control
22. Optimistic Concurrency Control — Wikipedia / Kung & Robinson 1981 (third corpus copy; adds transaction number timing, starvation detail). https://en.wikipedia.org/wiki/Optimistic_concurrency_control
23. Serializability — Wikipedia (third corpus copy; adds distributed databases, strict serializability). https://en.wikipedia.org/wiki/Serializability
24. Multiple Granularity Locking — Wikipedia / Gray 1975 (third corpus copy; adds DAG generalization, correctness proof, lock escalation). https://en.wikipedia.org/wiki/Multiple_granularity_locking
25. Vector Clock — Wikipedia (third corpus copy; adds CC theory relationship, DynamoDB/Riak/CouchDB applications, HLC). https://en.wikipedia.org/wiki/Vector_clock
26. Berenson, H., Bernstein, P., Gray, J., Melton, J., O'Neil, E., and O'Neil, P. (1995). A Critique of ANSI SQL Isolation Levels. ACM SIGMOD 1995. https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/tr-95-51.pdf
27. File Locking — Wikipedia. https://en.wikipedia.org/wiki/File_locking
28. Lock Compatibility Matrix — Berkeley CS186 Course Notes. https://cs186berkeley.net/notes/note12/
29. Deadlock (Computer Science) — Wikipedia. https://en.wikipedia.org/wiki/Deadlock_(computer_science)
30. Snapshot Isolation / Serializable Snapshot Isolation — Wikipedia (includes Cahill et al. 2008 content). https://en.wikipedia.org/wiki/Snapshot_isolation
31. Timestamp-Based Concurrency Control — Wikipedia (second corpus copy; adds strict T/O protocol, T/O vs OCC/MVCC comparison). https://en.wikipedia.org/wiki/Timestamp-based_concurrency_control

Home