1. Foundations of Concurrency Control

Concurrency control is the discipline of designing systems so that overlapping operations yield results that match a permitted, logically consistent execution. When multiple threads or transactions proceed at the same time, their actions may interleave in ways that are not equivalent to any simple, sequential order. Concurrency control introduces coordination rules that restrict or interpret those interleavings.

1.1 Why concurrency breaks correctness

In a single-threaded execution, program steps follow a predictable sequence. With concurrency, operations such as reads and writes to shared state can occur in an order different from the programmer’s assumed timeline. Even if each operation is correct in isolation, their overlap can create outcomes that would never appear in a sequential run. The root cause is interference: one operation can observe or modify data in the middle of another operation’s progress.

1.2 Consistency and correctness goals

Concurrency control aims to ensure that outcomes satisfy a defined correctness criterion. Depending on the system, this criterion may be framed as:

  • The final state matches the effect of some permitted ordering of operations.
  • Each operation observes data that is consistent with a snapshot or a restricted view.
  • Invariants over shared resources remain preserved despite parallel access.

These goals are often balanced against performance requirements, because stronger guarantees typically require more coordination.

1.3 Concurrency models and execution overlap

A concurrency model specifies how operations overlap and how interleavings are interpreted. At a high level, models distinguish:

  • Threads sharing memory directly (multithreaded programs).
  • Transactions operating over a database abstraction.
  • Distributed transactions spanning multiple nodes and communication links.

In all cases, the essential element is that operations can overlap in time, producing combined behaviors that must be governed by the system.

1.3.1 Interleavings and logical ordering

An interleaving is an ordering of the individual read/write steps from concurrent operations. Many concurrency control techniques do not force a single physical execution order; instead, they ensure that the observed effects correspond to some valid logical order. This view separates “how steps occur” from “which outcomes are considered correct.”

2. Concurrency Anomalies

Concurrency anomalies describe specific kinds of incorrect or surprising outcomes that arise when operations overlap without sufficient coordination.

2.1 Read/write interference

Read/write interference occurs when one transaction reads data while another is concurrently modifying it. The reader may see partially updated state or data that will later be rolled back, depending on the system’s rules. Correct behavior requires either preventing such overlap or constraining what the reader is allowed to observe.

2.2 Lost updates

Lost updates happen when two transactions both read the same initial value and then write back changes computed from that value. If the second write overwrites the first without accounting for it, one update effectively disappears. The anomaly is particularly common in “read-modify-write” workflows that lack proper synchronization.

2.3 Inconsistent reads

Inconsistent reads occur when a transaction reads multiple items, but the items reflect different points in time due to concurrent updates by other transactions. The transaction can observe a state that never existed as a whole, violating application-level invariants that assumed internal consistency.

2.4 Phantom reads

Phantom reads arise when a transaction repeats a query that matches a predicate (e.g., “all orders in a time range”) and obtains a different set of rows on the second query. Even if individual rows are protected, new rows inserted concurrently can create “phantoms” that change the result set.

2.5 Serialization and conflict interpretation

A common way to reason about anomalies is to relate an execution to serial execution. Serialization means that concurrent effects can be mapped to an equivalent sequential order. Conflict interpretation identifies which operations “conflict” (typically reads vs writes and writes vs writes) and uses that information to determine whether an observed outcome can be represented as a valid serialized schedule.

3. Transaction Concepts (Core to Many Systems)

Transactions provide a structured unit of work with rules about committing, aborting, and visibility of effects. Many concurrency control systems are built around transactional semantics.

3.1 Transactions and ACID properties

Transactions are designed to behave predictably:

  • Atomicity: either all effects of a transaction apply, or none do.
  • Consistency: transactions preserve database invariants according to application logic.
  • Isolation: concurrent transactions do not interfere beyond the system’s specified isolation guarantees.
  • Durability: once committed, results persist despite failures.

Isolation is directly related to concurrency control choices.

3.2 Isolation levels

Isolation levels define what interference patterns are acceptable and what observations are guaranteed. Lower isolation levels permit more parallelism but allow more anomalies. Higher isolation reduces anomalies by restricting how reads and writes can overlap or by requiring more coordination.

3.3 Serializability definitions

Serializability is a correctness criterion stating that the outcome of concurrent transactions is equivalent to some serial order of those transactions. Two major notions are:

  • Conflict serializability: based on conflicts between operations and the existence of an ordering without violating those conflicts.
  • View serializability: based on what values transactions read and what final values result, even if operation-by-operation conflicts are not sufficient to characterize it.

3.4 Conflict graphs and equivalence

A conflict graph models dependencies induced by conflicting operations. Nodes represent transactions; edges represent conflicts that force an order to preserve observed behavior. If the graph is acyclic, the schedule can be serialized according to that dependency structure. This concept supports practical reasoning and algorithmic checking.

4. Lock-Based Concurrency Control

Lock-based concurrency control uses explicit synchronization objects. A lock on a data item restricts other operations from accessing it in incompatible modes.

4.1 Locking primitives (shared/exclusive)

Most lock managers support two primary modes:

  • Shared (S) lock: permits other shared locks but blocks exclusive access.
  • Exclusive (X) lock: blocks both shared and exclusive access by others.

By mapping reads to shared locks and writes to exclusive locks, systems can prevent interference patterns that cause anomalies.

4.2 Two-phase locking (2PL)

Two-phase locking is a protocol that ensures locks are acquired before they are released:

  1. Growing phase: a transaction may acquire locks.
  2. Shrinking phase: a transaction may release locks, but it cannot acquire new ones.

2PL is designed to guarantee serializable behavior under common assumptions.

4.2.1 Strict 2PL and recovery implications

Strict 2PL holds all exclusive locks until the transaction commits or aborts. This reduces exposure to reading uncommitted changes and often simplifies recovery because other transactions cannot observe effects from transactions that may later roll back.

4.3 Deadlocks and detection

Deadlocks occur when transactions form a cycle of waiting: each transaction holds a lock needed by another. Without intervention, execution can stall. Detection-based approaches periodically search for cycles in the wait-for relationship, then abort one or more transactions to break the cycle.

4.4 Deadlock prevention strategies

Prevention aims to avoid deadlocks entirely. Common strategies include:

  • Lock ordering: transactions acquire locks in a predetermined global order.
  • Timeouts: abort transactions that wait too long.
  • Non-blocking designs: avoid waiting by failing and retrying when locks cannot be obtained.

Each strategy trades off overhead, latency, and throughput.

4.5 Lock granularity and overhead

Lock granularity refers to the size of the locked unit—ranging from entire databases to individual fields. Finer granularity can increase concurrency but adds lock-management overhead and complexity.

4.5.1 Coarse vs fine-grained locking

  • Coarse-grained: fewer locks, less overhead, but greater contention and reduced parallelism.
  • Fine-grained: more locks, potentially higher parallelism, but increased bookkeeping and increased risk of deadlocks if not carefully managed.

4.6 Intention locks and hierarchies

When data is organized hierarchically (e.g., database → table → row), intention locks indicate planned locking behavior on descendants. Intention locks help the lock manager determine compatibility quickly without forcing every access to traverse all levels.

4.7 Performance considerations (contention, fairness)

Lock-based systems must handle contention: as many transactions compete for the same items, waiting time rises. Fairness policies influence which waiting transactions make progress first. Some systems prevent starvation by using queueing or priority schemes, which can improve fairness at the cost of additional management.

5. Timestamp-Based Concurrency Control

Timestamp methods assign each transaction a logical time and use ordering rules to decide whether operations are allowed.

5.1 Logical timestamps and ordering

A transaction receives a start timestamp from a logical clock. The system then enforces that conflicts resolve according to these timestamps so that the final observed schedule aligns with timestamp order.

5.2 Optimistic timestamp validation

In many timestamp-based designs, transactions proceed speculatively and later validate that their observed reads are still consistent with writes that completed earlier. If validation fails, the transaction is aborted and restarted.

5.3 Multiversion timestamp strategies

Multiversion variants maintain multiple versions of data items, allowing transactions to read an earlier version consistent with their timestamp. This can reduce read/write blocking, especially when write conflicts are manageable.

5.4 Comparison with locking approaches

Timestamp methods can offer improved concurrency for workloads with many reads and fewer conflicts. However, they may increase abort rates under high contention and rely on careful version management and validation correctness.

6. Multiversion Concurrency Control (MVCC)

MVCC permits concurrent reads without blocking on writes by keeping multiple versions of each data item.

6.1 Versions and visibility rules

Each update creates a new version, typically tagged with commit information. Visibility rules determine which version a transaction is allowed to read based on its start time or snapshot boundaries. This structure prevents readers from seeing intermediate states.

6.2 Read stability and snapshot reads

Snapshot reads provide a stable view of the database at a chosen logical time. Within a transaction, repeated reads return values consistent with that snapshot, eliminating certain anomalies such as inconsistent reads across multiple items.

6.3 Write-write conflicts under MVCC

Even with multiversioning, write conflicts must be handled. Systems typically detect overlapping writes to the same item (or relevant indexes) and decide whether to allow the later writer to commit or to abort. Because updates change the version set, conflicts are usually enforced at commit time or via write locks on specific metadata.

6.4 Garbage collection of old versions

Old versions accumulate as new writes arrive. Garbage collection removes versions that are no longer visible to any active transaction according to retention rules.

6.4.1 Vacuuming and retention policies

Many systems use background processes to reclaim space. Retention policy choices balance storage costs, the need to support long-running transactions, and the overhead of version cleanup.

6.5 Tradeoffs: storage vs throughput

MVCC can improve throughput by reducing blocking between readers and writers. The tradeoff is extra storage and maintenance work for version creation and cleanup, which can affect cache behavior and system load.

7. Optimistic Concurrency Control

Optimistic concurrency control assumes conflicts are relatively rare and therefore performs work with minimal blocking, checking for conflicts near the end.

7.1 Validate-then-commit workflow

Transactions execute in two conceptual phases:

  1. Execution: read and compute changes without strict locking that blocks others.
  2. Validation: at commit time, verify that the read set has not been invalidated by concurrent writes.

If validation succeeds, the commit is applied; otherwise the transaction aborts.

7.2 Detecting conflicts at commit time

Conflict detection at commit time focuses on whether other transactions have modified data that the committing transaction depended upon. This can include changes to any items read during execution, depending on the model’s validation rules.

7.3 Read/Write sets and validation checks

A transaction records:

  • Read set: the items it accessed.
  • Write set: the items it intends to modify.

Validation checks compare these sets against the effects of transactions that committed concurrently, ensuring that the intended commit does not contradict the earlier reads.

7.4 Retrying policies and backoff

When a transaction aborts due to validation failure, the application may retry. Backoff strategies reduce synchronized retries that would otherwise create contention spikes. Proper retry limits help avoid endless loops under persistent contention.

7.5 When optimism performs well

Optimistic schemes are most effective when:

  • Transactions are short.
  • Read/write conflicts are infrequent.
  • The cost of validation is small relative to the cost of blocking.

Workloads dominated by reads and with low update overlap often benefit.

8. Deadlock Handling and System Recovery

Deadlocks and failures require mechanisms beyond normal scheduling rules. Recovery logic ensures correct outcomes after interruptions.

8.1 Aborts and rollbacks

When a transaction cannot proceed safely—due to deadlock resolution, validation failure, or explicit abort—it must undo partial effects. Rollbacks restore the system to a state consistent with completed transactions.

8.2 Wait-die and wound-wait policies

These are common schemes used with time-based reasoning to control who waits and who aborts. One approach chooses a rule so that older transactions either wait or preempt younger ones, depending on conflict direction, aiming to reduce deadlocks without excessive cycle detection.

8.3 Cascading aborts and mitigation

If a transaction reads uncommitted data from another transaction that later aborts, the reader may need to abort as well to maintain isolation properties. Cascading aborts can be costly; systems mitigate them using strictness, multiversioning, or careful dependency tracking.

8.4 Compensation logic in application design

Not all effects are easily reversible at the database level (e.g., external actions). Applications may implement compensation actions that “undo” side effects through additional operations, with concurrency control ensuring those compensations remain consistent with transaction outcomes.

9. Concurrency Control in Distributed Systems

Distributed systems introduce coordination across network boundaries, where delays and partial failures complicate concurrency control.

9.1 Replication and coordination challenges

Replication improves availability and read performance but requires consistent update propagation. Concurrent updates to replicas can diverge, so concurrency control must coordinate commit ordering and visibility across nodes.

9.2 Consensus-friendly approaches (high level)

Distributed transaction processing often aims to integrate with consensus mechanisms that agree on ordering or state transitions. Designs may use leader-based commit coordination or log-based replication so that conflicting writes are resolved by a deterministic ordering.

9.3 Partitioning and transaction boundaries

Partitioning data reduces cross-node contention by keeping related items together. Transaction boundaries define which operations touch which partitions; narrowing boundaries can significantly reduce coordination overhead and the number of locks or version checks required across nodes.

9.4 Network latency effects on locking

In distributed locking, acquiring and releasing locks involves remote messages. High latency increases waiting time and can amplify deadlock likelihood across nodes. These factors motivate designs that reduce blocking, such as multiversioning or optimistic validation.

9.5 Consistency vs availability tradeoffs (non-political)

Consistency requirements influence how operations proceed during delays or failures. Systems may prioritize safe correctness using coordination, or they may provide more availability by relaxing guarantees, typically within well-defined correctness limits. The tradeoff is often addressed through technical configuration rather than policy choices.

10. Concurrency Control for Multithreaded Programs

Database-style concurrency control concepts also appear in multithreaded programming, though the shared state model may differ.

10.1 Critical sections and mutual exclusion

Mutual exclusion ensures that only one thread at a time accesses a critical region that manipulates shared state. This prevents concurrent updates from producing inconsistent results, but it can limit parallelism if the critical section is large or frequently entered.

10.2 Condition variables and signaling

Condition variables allow threads to wait until a particular condition becomes true while releasing the associated lock. Signaling wakes waiting threads when state changes. Correct usage requires pairing waits with predicates and protecting those predicates with mutexes.

10.3 Reader-writer synchronization

Reader-writer locks distinguish between reading and writing access. Multiple readers can proceed concurrently when no writer holds the lock, while writers obtain exclusive access. This approach is beneficial when read operations dominate and write frequency is low.

10.4 Barriers and phased execution

Barriers synchronize threads at specific execution points so that all participants reach the same phase before continuing. Barriers are useful in algorithms with stepwise structure, such as parallel iteration methods or pipeline stages.

10.5 Atomic operations and memory ordering

Atomic operations allow indivisible updates to shared variables. Memory ordering rules determine how loads and stores become visible across cores. Correctness depends not only on atomicity but also on ordering constraints that prevent harmful reordering.

10.5.1 Compare-and-swap (CAS) patterns

Compare-and-swap compares the current value to an expected one and updates it only if they match. Many lock-free algorithms build on CAS to implement synchronization without blocking, though they require careful handling of contention and correctness proofs.

11. Isolation Level Selection and Tuning

Choosing an isolation level determines which anomalies are prevented and which performance costs are accepted.

11.1 Mapping requirements to isolation

Isolation selection starts from application semantics. If the application requires consistent multi-item reads, the isolation must prevent inconsistent snapshots or phantom effects. If a workload tolerates some anomalies, a weaker isolation can offer higher throughput.

11.2 Benchmarking contention and throughput

Because contention patterns vary by workload, benchmarking is essential. Metrics include transaction latency, abort rate (for optimistic schemes), queueing time (for lock-based schemes), and effective throughput under representative mixes.

11.3 Query and workload-driven tuning

Performance depends on access patterns: hot rows, range queries, and index usage affect how often transactions conflict. Tuning may involve schema changes, indexing strategies, or reworking query plans so that concurrency control overhead is reduced.

11.4 Correctness/performance evaluation metrics

Evaluation typically combines:

  • Correctness properties (e.g., serializability or weaker guarantees).
  • Observed anomalies in tests.
  • Operational metrics such as percentiles of latency and resource usage.

These measures help determine whether the chosen isolation level meets both functional and performance objectives.

12. Testing, Debugging, and Verification

Concurrency correctness is difficult to validate because failures can depend on timing and scheduling.

12.1 Reproducing concurrency bugs

Some concurrency bugs are rare and disappear under logging or debugging. Reproduction can require capturing schedules, adding instrumentation, or using workload replay. Without repeatability, diagnosing the precise interleaving that caused incorrect behavior is challenging.

12.2 Stress and randomized testing

Stress testing increases the likelihood of unusual interleavings by raising concurrency levels and varying timing. Randomized test strategies perturb operation order and scheduling, improving coverage of problematic cases.

12.3 Deterministic schedulers (overview)

Deterministic scheduling frameworks try to make thread interleavings reproducible by controlling the scheduling decisions. This can turn “heisenbugs” into repeatable failures, allowing systematic debugging.

12.4 Model checking concepts (high level)

Model checking explores possible states to verify that properties hold under all relevant interleavings, usually within bounded limits. For concurrency control algorithms, model checking can validate protocol invariants and detect deadlock conditions in simplified models.

12.5 Logging and tracing for contention

Instrumentation helps correlate contention events with performance anomalies. Tracing lock waits, validation failures, and retries provides evidence of which parts of a system contribute most to delays and aborts.

13. Performance Modeling and Complexity

Concurrency control affects both computational cost and system-level behavior under load.

13.1 Contention modeling

Contention models estimate how often transactions compete for the same resources. Factors include hot-spot distribution, transaction length, and the overlap of read/write sets. Accurate modeling helps predict when a technique will degrade.

13.2 Throughput and latency under load

As load increases, waiting time and abort probability typically rise. Systems must balance throughput (completed work per time) with latency requirements (time per transaction), which may respond differently to tuning.

13.3 Scalability bottlenecks

Scalability bottlenecks can arise from centralized lock managers, global timestamps, high-frequency version creation, or network-wide coordination. Bottlenecks often shift as system load patterns change, making end-to-end evaluation necessary.

13.4 Cost of locking vs validation

Locking introduces overhead for acquiring, holding, and releasing locks, plus possible queueing delays. Validation introduces overhead for tracking read/write sets and checking conflicts at commit time, plus potential abort and retry costs. The more frequently conflicts occur, the more validation overhead tends to become costly.

13.5 Starvation and fairness concerns

Starvation occurs when a transaction or thread repeatedly fails to make progress. Fairness policies, such as FIFO queueing in lock managers or backoff in optimistic retries, reduce starvation risk but may reduce peak throughput. Correctness is maintained either way, but user-visible performance differs.

Modern systems often combine multiple techniques to exploit their respective strengths.

14.1 Hybrid approaches (locking + MVCC/optimism)

Hybrid designs may use MVCC for reads while employing locks for specific write paths, or they may use optimistic validation with targeted locking on highly contended resources. The goal is to reduce blocking without losing control over write conflicts.

14.2 Escalation and adaptive control

Lock escalation changes the granularity of locking based on contention. Adaptive controls can shift between strategies—such as moving from optimistic to lock-based execution—depending on observed conflict rates and workload characteristics.

14.3 Transactional memory (overview)

Transactional memory is a programming paradigm that aims to provide atomic blocks of code without explicit locks. It can be implemented in software or hardware and is typically presented as a way to simplify concurrency by automatically handling conflicts and rollbacks at runtime.

14.4 Idempotency and retry-safe designs

When retries are common—particularly in optimistic systems—operations must be safe to repeat without causing incorrect outcomes. Idempotency ensures that repeated requests produce the same effect as a single successful request, which helps maintain correctness even when aborts and retries occur frequently.