Concurrency Control

Two-Phase Locking (2PL) is a foundational concurrency control protocol that guarantees serializability by enforcing a strict lock acquisition and release discipline. A transaction has two distinct phases:

• Growing Phase: The transaction may acquire locks but cannot release any.
• Shrinking Phase: The transaction may release locks but cannot acquire new ones.

Variants include Strict 2PL, where all locks are held until transaction commit, which simplifies recovery but increases lock contention. While 2PL ensures correctness, it is susceptible to deadlock, requiring complementary detection or prevention schemes.

Timestamp Ordering (TO) is a non-locking, optimistic concurrency control protocol. Each transaction is assigned a unique, monotonically increasing timestamp upon start. The protocol serializes transactions in timestamp order by enforcing two rules:

• Read Rule: A read operation is allowed only if the timestamp of the transaction is greater than the timestamp of the last write to that data item.
• Write Rule: A write operation is allowed only if the timestamp of the transaction is greater than the timestamp of the last read and last write to that data item.

Violations cause the transaction to be aborted and restarted with a new timestamp. This method avoids deadlocks but can suffer from high abort rates under high contention.

Optimistic Concurrency Control (OCC) operates on the assumption that transactions rarely conflict. It proceeds in three phases, deferring all checks until the end:

1. Read Phase: The transaction executes, reading values into a private workspace and tracking writes locally.
2. Validation Phase: Before commit, the system checks if the transaction's reads conflict with writes from other committed transactions. A transaction is validated if it appears to have executed in a serial order relative to others.
3. Write Phase: If validation succeeds, the private writes are applied to the database; otherwise, the transaction is aborted.

OCC is highly efficient in low-conflict environments but requires rollback mechanisms and careful management of the validation phase to ensure correctness.

Multi-Version Concurrency Control (MVCC) maintains multiple physical versions of a data item. This allows read operations to access a snapshot of consistent past data without blocking concurrent write operations. Key mechanisms include:

• Version Storage: Each write creates a new version, linked to its predecessor.
• Visibility Rules: A transaction's read operations see all versions committed before its start time and no versions committed after.
• Garbage Collection: Old versions no longer visible to any active transaction are purged.

This provides non-blocking reads and improves throughput, but incurs storage overhead for version history. It is the standard mechanism in PostgreSQL, Oracle, and InnoDB (MySQL).

Serializable Snapshot Isolation (SSI) is an enhancement to Snapshot Isolation (SI) that detects and prevents serialization anomalies—specifically write skew—to guarantee full serializability. It works by:

• Tracking Dependencies: Monitoring read-write and write-write dependencies between concurrent transactions.
• Conflict Detection: Using commit-time checks to identify dangerous structures in the dependency graph that indicate a potential serialization anomaly.
• Aborting Transactions: Preemptively aborting one transaction in a dangerous pair to maintain correctness.

SSI retains the performance benefits of snapshot-based reads while providing the strongest isolation guarantee, making it a preferred choice in modern systems like PostgreSQL.

Two-Phase Locking (2PL) is a foundational concurrency control protocol that guarantees serializability by enforcing a strict discipline on lock acquisition and release. A transaction has two distinct phases:

• Growing Phase: The transaction may acquire locks but cannot release any.
• Shrinking Phase: The transaction may release locks but cannot acquire any new ones.

While 2PL ensures correctness, it is susceptible to deadlock, as transactions may hold locks while waiting for others. Variants like Strict 2PL, where all locks are held until transaction commit, are common in database systems to simplify recovery.

Timestamp Ordering (TO) is a non-locking, optimistic concurrency control method. Each transaction is assigned a unique, monotonically increasing timestamp upon start. The protocol ensures serializability by ordering transactions based on these timestamps.

Key rules:

• Read Rule: A read operation is allowed only if the timestamp of the transaction is greater than the timestamp of the last write to that data item.
• Write Rule: A write is allowed only if the transaction's timestamp is greater than the timestamp of the last read and last write for that item.

Violations cause the transaction to be aborted and restarted with a new timestamp. This method avoids deadlock but can suffer from high abort rates under high contention.

Optimistic Concurrency Control (OCC) operates on the assumption that conflicts are rare. Transactions proceed in three phases without acquiring locks:

1. Read Phase: The transaction reads data items, performing computations in a private workspace.
2. Validation Phase: Before commit, the system checks if the transaction's reads conflict with writes from other concurrently committed transactions.
3. Write Phase: If validation passes, the private writes are applied to the database; otherwise, the transaction is aborted.

Validation can be backward-looking (checking against committed transactions) or forward-looking (checking against active transactions). OCC is efficient in low-conflict scenarios but requires rollback mechanisms and careful management of the validation phase.

Multi-Version Concurrency Control (MVCC) maintains multiple physical versions of a data item. Read operations access a snapshot of the database from a past timestamp, while writes create new versions. This decouples readers from writers.

Key mechanisms:

• Version Storage: A version chain per data item, often with creation and deletion timestamps.
• Garbage Collection: A process to reclaim old versions no longer needed by any active snapshot.
• Visibility Rules: Determine which version is visible to a transaction based on its start timestamp and the version timestamps.

MVCC provides high performance for read-heavy workloads and is the backbone of systems like PostgreSQL and modern distributed databases. It can prevent read-write deadlocks but introduces storage overhead.

Conflict Serializability is the practical criterion for determining if a concurrent schedule of transactions is equivalent to a serial one. Two operations conflict if they are from different transactions, operate on the same data item, and at least one is a write.

Analysis is performed using a Precedence Graph (or Serializability Graph):

• Nodes: Represent transactions.
• Directed Edge (T_i → T_j): Exists if an operation in T_i precedes and conflicts with an operation in T_j.

A schedule is conflict-serializable if and only if its precedence graph is acyclic. Concurrency control protocols like 2PL are designed to produce schedules that result in an acyclic graph, thereby guaranteeing serializability. Cycle detection in this graph is analogous to deadlock detection in wait-for graphs.

Extending concurrency control across multiple nodes introduces significant complexity due to network latency, partial failures, and lack of a global clock. Primary approaches include:

• Distributed Two-Phase Locking (Distributed 2PL): Locks are managed locally, but a coordinator (often the transaction's originating node) manages the global commit protocol, typically Two-Phase Commit (2PC).
• Distributed Timestamp Ordering: A global timestamp must be generated, often using logical clocks (e.g., Lamport timestamps) or hybrid logical-physical clocks.
• Pessimistic vs. Optimistic Trade-offs: Network delays make lock-holding times longer, favoring optimistic or multi-version schemes.

Distributed deadlock detection becomes essential, employing algorithms like edge-chasing (Chandy-Misra-Haas) where probe messages traverse the distributed wait-for graph to detect cycles.

Two-Phase Locking (2PL) is a foundational concurrency control protocol that ensures serializable execution of database transactions. It mandates two distinct phases:

• Growing Phase: A transaction may acquire locks but cannot release any.
• Shrinking Phase: A transaction may release locks but cannot acquire new ones. While it guarantees correctness, strict 2PL (where all locks are held until commit) is often used to prevent cascading rollbacks. A major drawback is its potential to create deadlocks, as transactions may hold locks while waiting for others.

A safe state is a system configuration in deadlock avoidance where there exists at least one theoretical sequence (a safe sequence) in which all currently active processes can be granted their maximum possible resources and still complete without causing a deadlock. The Banker's Algorithm uses this concept to evaluate resource requests dynamically. If granting a request would leave the system in an unsafe state (where deadlock is possible), the request is denied. Maintaining a safe state is a proactive guarantee of deadlock freedom.

A Wait-For Graph (WFG) is a directed graph used for deadlock detection in systems with multiple processes or agents. Nodes represent processes, and a directed edge from process P_i to P_j indicates that P_i is waiting for a resource currently held by P_j. The core detection mechanism is cycle detection: the existence of a cycle in the WFG signifies a deadlock. This model abstracts specific resources, focusing purely on dependencies, making it efficient for centralized detection algorithms. In distributed systems, algorithms like edge-chasing propagate probes along these graphs.

Priority inversion is a scheduling anomaly and a common cause of unbounded blocking in real-time systems, often leading to deadlock-like scenarios. It occurs when a high-priority task is forced to wait for a resource held by a low-priority task, which is in turn preempted by a medium-priority task. This chain of events inverts the intended priority scheme. The Priority Inheritance Protocol is a standard mitigation, where the low-priority task temporarily inherits the priority of the high-priority task waiting on it, allowing it to run and release the resource promptly.

A livelock is a concurrency failure state akin to a deadlock, where processes are not blocked but make no progress. Processes continuously change state in response to each other in a non-productive cycle. A classic example is two agents in a narrow corridor, each repeatedly stepping aside to let the other pass, resulting in endless side-stepping. Unlike starvation (where one process is perpetually denied), livelock involves mutual interference. Resolution often requires introducing randomness or coordinated back-off protocols to break the symmetrical, oscillating behavior.

Model checking is a formal verification technique used to exhaustively analyze the state space of a concurrent system for properties like deadlock freedom, liveness, and safety. Engineers create a formal model (e.g., using Petri Nets or process calculi) and a specification of desired properties. The model checker then explores all possible states and transitions to verify the properties or provide a counter-example trace leading to a violation. This is a powerful method for proving the correctness of concurrency control protocols and orchestration logic before deployment.