Concurrency Control and Distributed Deadlocks

Introduction

A distributed database permits multiple transactions to execute concurrently while data is stored at several networked sites. Concurrency improves throughput, resource utilization, and response time, but it also creates correctness risks. Two transactions may read and write the same logical item at different replicas, sites may observe events in different orders, and communication delays may cause a transaction to wait for a lock that is already involved in a remote dependency cycle.

Concurrency control is the collection of protocols that regulate conflicting operations so that concurrent execution has an acceptable correctness property, usually serializability or a deliberately weaker isolation level. In a distributed database, the protocol must also address message delays, site failures, replicated data, clock limitations, coordinator failures, and the distinction between local and global knowledge.

This chapter examines locking, timestamp ordering, optimistic and multiversion methods, serializability, snapshot isolation, distributed deadlocks, and scheduling anomalies. The central design problem is to balance correctness, availability, latency, and implementation cost.

Learning Objectives

After studying this chapter, students should be able to:

1. Explain conflict and view serializability in centralized and distributed settings.
2. Compare two-phase locking, timestamp ordering, optimistic control, and multiversion concurrency control.
3. Analyze snapshot isolation and identify its anomalies.
4. Construct and interpret distributed wait-for graphs.
5. Distinguish deadlock prevention, detection, avoidance, and recovery.
6. Evaluate concurrency-control choices for replicated and geographically distributed systems.
7. Apply these concepts to a realistic distributed transaction scenario.

1. Transactions, Schedules, and Correctness

A transaction is a finite sequence of database operations that normally satisfies atomicity, consistency, isolation, and durability (ACID). An operation is commonly written as r_i(X) for a read of item X by transaction Tᵢ, or w_i(X) for a write. A schedule is an ordering of operations from several transactions that preserves the internal order of each transaction.

Two operations conflict when they belong to different transactions, access the same logical item, and at least one is a write. Thus, read–read operations do not conflict, whereas read–write, write–read, and write–write operations do.

A schedule is conflict-serializable if its precedence graph is acyclic. The graph has one node per transaction and an edge Tᵢ → Tⱼ when a conflicting operation of Tᵢ precedes the corresponding operation of Tⱼ in the schedule. A topological ordering of the graph gives an equivalent serial order.

For example, if T₁ reads X before T₂ writes X, and T₂ writes Y before T₁ reads Y, the graph contains T₁ → T₂ and T₂ → T₁. The cycle proves that the schedule is not conflict-serializable.

View serializability is more general. Two schedules are view equivalent if they preserve which transaction reads the initial value, which transaction supplies each read value, and which transaction performs the final write on every item. Every conflict-serializable schedule is view-serializable, but the converse is not necessarily true. Conflict serializability is preferred in most practical protocols because it is easier to test and enforce.

In a distributed database, the logical item may be replicated. A protocol must ensure that operations on replicas represent a coherent global object. Local serializability at every site does not by itself guarantee global serializability. A global schedule may combine locally harmless orders into an inconsistent cycle.

Serializability and recoverability

Serializability concerns isolation, while recoverability concerns safe commitment after reads from other transactions. A schedule is recoverable if a transaction that reads a value written by Tⱼ does not commit before Tⱼ commits. Cascadeless schedules avoid reading uncommitted values; strict schedules delay both reads and writes of an item until the transaction that last wrote it commits or aborts. Strictness simplifies recovery and is a common goal of locking systems.

2. Distributed Scheduling Anomalies

Concurrency anomalies arise when conflicting operations are improperly ordered. Important examples include:

• Lost update: two transactions read the same old value and one overwrites the other’s update.
• Dirty read: a transaction reads data written by an uncommitted transaction that later aborts.
• Non-repeatable read: a transaction reads an item twice and obtains different committed values.
• Phantom: repeated execution of a predicate query returns a different set of rows because another transaction inserted, deleted, or modified a qualifying row.
• Write skew: two transactions read overlapping data, update different items, and together violate a constraint.
• Inconsistent analysis: an aggregate reads some values before and some after another transaction’s update.

Distributed execution adds further anomalies. A transaction may read an old replica while another transaction has already committed at a different site. Network partitions can produce divergent histories. Clock skew can make physical timestamps disagree with causal order. A coordinator may decide to commit while a participant is unreachable, creating uncertainty about the transaction’s final outcome.

Predicate and phantom anomalies require protection of ranges or predicates, not merely individual records. Key-range locks, predicate locks, serializable snapshot isolation, or validation of predicate reads are possible solutions.

3. Lock-Based Concurrency Control

A lock is a logical permission that controls access to a data item. The standard modes are:

A transaction must obtain an S lock before reading and an X lock before writing. Lock conversion from S to X may be permitted, but conversion can itself create deadlock. A lock manager maintains granted locks and a queue of waiting requests.

Two-phase locking

Under two-phase locking (2PL), a transaction has a growing phase, during which it obtains locks but releases none, followed by a shrinking phase, during which it releases locks but obtains none. The protocol guarantees conflict serializability if all conflicting accesses are protected by the required locks.

Strict 2PL holds all exclusive locks until commit or abort. Strong strict 2PL holds both shared and exclusive locks until completion. Strictness prevents dirty reads and cascading aborts and makes recovery easier, although it can reduce concurrency.

A distributed transaction may require a lock at several sites. Distributed 2PL preserves serializability if lock acquisition and release collectively obey 2PL and all replicas representing one logical item are coordinated consistently. Centralized lock management is simple but creates a bottleneck; primary-copy locking assigns one authoritative replica to manage locks; fully distributed locking spreads management but increases communication and deadlock complexity.

Intention locks and hierarchical locking

Databases often lock at several granularities, such as database, table, page, and row. Intention locks advertise lower-level locks. IS means that shared locks will be acquired below the current object; IX means that exclusive locks will be acquired below it; SIX combines shared access to the object with intention-exclusive access below it. A multigranularity protocol requires a transaction to follow a compatible top-down acquisition order and a bottom-up release order.

Distributed lock protocol

A practical distributed lock request typically follows these steps:

1. Map the logical item to its lock authority or replica group.
2. Send a request containing transaction identity, item identity, mode, and an ordering identifier.
3. Grant the lock if compatible; otherwise place the request in a wait queue.
4. Record remote dependencies for deadlock detection.
5. Release locks after commit or abort and notify waiting transactions.

Failures complicate this process. Leases or failure detectors may reclaim locks, but premature reclamation can allow conflicting work while a transaction is still active. Therefore lock expiration must be integrated with fencing tokens, epochs, or an authoritative membership service.

4. Timestamp-Ordering Protocols

Timestamp ordering assigns each transaction a unique timestamp TS(T). Timestamps may be generated by a centralized service, by a site using logical counters, or by a causally ordered mechanism. Physical time alone is unsafe when clocks can move backward or differ across sites.

For each data item X, maintain read_TS(X), the largest timestamp of a transaction that successfully read X, and write_TS(X), the largest timestamp of a transaction that successfully wrote X. In the basic timestamp-ordering protocol:

• A read rᵢ(X) is rejected if TS(Tᵢ) < write_TS(X); otherwise read_TS(X) is updated.
• A write wᵢ(X) is rejected if TS(Tᵢ) < read_TS(X) or TS(Tᵢ) < write_TS(X); otherwise write_TS(X) is updated.

A rejected operation causes rollback or restart of the transaction. The protocol ensures that conflicting operations appear in timestamp order and does not create lock waits, so traditional deadlock does not occur. Its disadvantages include repeated aborts under contention and sensitivity to timestamp-service availability. Thomas’s write rule can ignore certain obsolete writes when TS(Tᵢ) < write_TS(X), improving concurrency, but it must be used only under the rule’s stated conditions and may not provide the same guarantees for every application.

Distributed timestamp systems must ensure uniqueness and a meaningful order. A pair such as (logical counter, site identifier) guarantees uniqueness, but not necessarily causality unless counters are updated on message send and receipt. Hybrid logical clocks combine physical-clock intuition with logical corrections, but they do not eliminate the need for a clearly defined consistency protocol.

5. Optimistic Concurrency Control

Optimistic concurrency control (OCC) assumes that conflicts are infrequent. A transaction executes without locking data for most of its lifetime, records its read set R(T) and write set W(T), validates at commit, and then installs its updates if validation succeeds.

The three conceptual phases are:

1. Read phase: read committed versions and calculate tentative results.
2. Validation phase: test whether the transaction can be serialized with transactions that overlap it.
3. Write phase: publish buffered writes atomically if validation succeeds.

A validation test must account for the chosen serialization order. For example, if Tᵢ validates after Tⱼ, then allowing Tᵢ to commit is unsafe when Tⱼ’s write set intersects Tᵢ’s read set, because Tᵢ may have read a value that Tⱼ changed. Exact tests vary by implementation, and an OCC design must specify whether transactions validate against active, validated, or committed transactions.

OCC is attractive for read-heavy, low-conflict workloads and avoids lock blocking. It performs poorly when long transactions frequently conflict, because work is discarded at validation. In distributed systems, validation also requires reliable and sufficiently current knowledge of remote read and write sets.

6. Multiversion Concurrency Control

Multiversion concurrency control (MVCC) stores multiple committed versions of an item. A reader chooses a version visible in its read snapshot, while a writer creates a new version rather than overwriting the old version immediately. MVCC can allow readers and writers to proceed concurrently.

A version can be represented conceptually as Xᵥ = (value, begin, end), where begin and end identify the visibility interval. A transaction with snapshot timestamp s can read the newest committed version satisfying begin ≤ s < end. The exact representation differs among systems; some use transaction identifiers, commit sequence numbers, or epochs rather than literal timestamps.

MVCC reduces read blocking and supports consistent snapshots. It does not automatically guarantee serializability. A system that allows concurrent transactions to read an old snapshot and update different records may exhibit write skew. Version cleanup, or garbage collection, must retain every version still needed by active snapshots. Long-running snapshots can therefore create storage pressure.

In replicated databases, a snapshot must have a defined scope. A local snapshot at one site may not include causally related writes from another site. Globally consistent snapshots require coordination, such as a common commit sequence, a consistent-cut protocol, or a replicated log with appropriate visibility rules.

7. Snapshot Isolation and Its Limits

Under snapshot isolation (SI), each transaction reads from a snapshot established at its start, and a transaction that writes an item conflicts with another concurrent transaction that writes the same item. A common first-committer-wins rule aborts one of two concurrent writers to the same item.

SI prevents many dirty, non-repeatable, and lost-update anomalies. However, it is weaker than serializability because read–write dependencies can form cycles without a direct write–write conflict. The classic write-skew example is an on-call rule: two doctors are on duty, and the constraint requires at least one to remain. T₁ reads that both doctors are on duty and changes doctor A to off duty. T₂ reads the same snapshot and changes doctor B to off duty. Since they write different rows, SI may allow both to commit, violating the constraint.

Serializable snapshot isolation (SSI) augments snapshot execution with dependency tracking. It detects dangerous structures, commonly involving overlapping read–write dependencies, and aborts a transaction when the system determines that a serializable cycle could form. SSI improves concurrency relative to strict locking in some workloads, but it requires memory and tracking overhead and can produce aborts.

The choice among read committed, repeatable read, SI, and serializable isolation should be based on business invariants, not merely benchmark throughput. If an invariant spans multiple rows or partitions, test whether the selected isolation level actually protects it.

8. Deadlocks in Distributed Databases

A deadlock is a cycle of transactions, each waiting for a resource held by another transaction in the cycle. In a centralized setting, a wait-for graph (WFG) contains an edge Tᵢ → Tⱼ when Tᵢ waits for Tⱼ. A cycle indicates deadlock.

In a distributed database, no single site may see the complete graph. A local graph can be acyclic even though the union of local graphs contains a cycle. For example, site S₁ may record T₁ → T₂, while site S₂ records T₂ → T₁. Neither site can detect the global cycle alone.

Figure: A distributed wait-for cycle whose edges are observed at different sites.

Deadlock handling strategies

Prevention ensures that at least one necessary condition for deadlock cannot hold. Timestamp schemes such as wait-die and wound-wait impose an age order. In wait-die, an older transaction may wait for a younger one, whereas a younger transaction requesting a resource held by an older one aborts. In wound-wait, an older requester may abort a younger holder, while a younger requester waits. The precise policy must be applied consistently and must address transaction restarts.

Avoidance grants a request only when the resulting state is known to remain safe. This requires knowledge of possible future resource demands and is less common for general database locking.

Detection and recovery allow waits, periodically construct a global or partially combined WFG, detect cycles, and abort a victim. Distributed detection methods include a centralized detector, edge-chasing algorithms, and hierarchical detectors. Edge chasing sends probes along dependency edges; a probe that returns to its origin indicates a cycle under the algorithm’s assumptions. Delayed or duplicated messages can create false suspicions, so implementations require transaction epochs, idempotent messages, and careful failure handling.

Victim selection may consider transaction age, amount of work completed, number of locks held, restart cost, priority, and the effect on service-level objectives. Aborting a transaction is not sufficient if its locks are not released or if its retry immediately reproduces the same cycle. Backoff, priority aging, and deterministic lock ordering reduce repeated deadlocks.

9. Distributed Commit and Concurrency Control

Concurrency control and atomic commit are distinct but interdependent. Two-phase commit (2PC) coordinates the decision to commit or abort, but it does not itself guarantee serializability and can block participants while the coordinator is unavailable. A transaction may hold locks during the prepared state, increasing deadlock and resource pressure.

A robust design specifies when locks are acquired, when versions become visible, how validation interacts with the commit timestamp, and what happens if a participant fails after preparing. Consensus-based replication can provide a fault-tolerant log, but consensus does not automatically solve application-level conflicts. Conversely, a serializable transaction protocol still needs an atomic commit mechanism when updates span independent resource managers.

10. Applied Case: Distributed Seat Reservation

Background. Consider a fictional airline platform with regional database partitions. Flight inventory is replicated between two regions. A reservation transaction must ensure that the number of confirmed seats never exceeds capacity and that a seat cannot be assigned twice.

Problem. During a network delay, customer transaction T₁ reads the last available seat at region A, while T₂ reads the same apparent availability at region B. If both regions accept updates independently, local serializability can coexist with a global overbooking anomaly. A separate example occurs when T₁ locks the passenger record at A and waits for the flight record at B, while T₂ holds the flight record at B and waits for the passenger record at A.

Analysis. Row-level SI with first-committer-wins prevents two transactions from updating the same seat row, but it may not protect a capacity constraint represented by an aggregate counter and several seat records. A distributed lock on the flight’s inventory key, or a serializable reservation service using a single ordered log, can serialize allocations. A deterministic order—passenger identifier before flight identifier—reduces deadlocks when multiple objects must be locked.

Approach. The platform assigns each flight inventory item a primary concurrency authority. Reservation requests are routed to that authority, which validates the current version, reserves the seat, and publishes the committed result through replication. Transactions that span passenger and payment records use strict 2PL or a carefully designed saga when a single atomic transaction is impossible. A global deadlock detector combines dependency edges from regional lock managers. Leases are protected by fencing epochs so an old regional leader cannot continue writing after failover.

Outcome. The primary authority prevents conflicting seat allocations, version checks reject stale requests, and the global detector aborts one transaction when a cross-region cycle appears. The design sacrifices some availability during loss of the inventory authority, but it preserves the stronger business invariant.

Learning points. First, identify the invariant rather than selecting isolation by habit. Second, local correctness is not global correctness. Third, replication, commit, and concurrency control must be designed together. Finally, predictable lock ordering and bounded transaction scope often improve performance more safely than simply weakening isolation.

11. Performance, Governance, and Contemporary Practice

Concurrency control has measurable costs: lock memory, network round trips, validation work, version storage, aborts, and waiting time. Useful operational metrics include commit latency, conflict-abort rate, deadlock frequency, average lock-wait duration, oldest active snapshot age, and replication visibility lag. Metrics should be segmented by transaction type and partition; aggregate averages can hide hotspots.

Governance requires clear isolation-level documentation, auditability of abort and retry decisions, access controls for lock and transaction metadata, and careful treatment of personally identifiable information in diagnostic logs. A deadlock graph may reveal sensitive identifiers or business relationships. Automated retry logic must be bounded and idempotent; otherwise a system can amplify load during an incident.

Modern distributed SQL systems commonly combine MVCC, a replicated ordering or consensus layer, timestamp or hybrid-clock services, and serializable or SI-based execution. Cloud architectures also use partition-aware scheduling, deterministic transaction ordering, and workload-adaptive techniques. AI can assist with anomaly detection, hotspot prediction, or tuning, but it should not silently change isolation guarantees. Any learned policy must be observable, tested against adversarial workloads, and constrained by explicit correctness rules.

Best-practice checklist

• Define the required invariant and isolation guarantee explicitly.
• Use strict 2PL, serializable OCC, or serializable MVCC when business correctness requires serializability.
• Use deterministic lock ordering and keep transactions short.
• Treat replicas of one logical item as one concurrency domain.
• Use logical or causally informed ordering rather than unsynchronized wall-clock time.
• Monitor global as well as local waits, conflicts, versions, and commit latency.
• Make retries safe through idempotency keys and bounded exponential backoff.
• Test partitions, delayed messages, coordinator failure, clock anomalies, and long snapshots.
• Document the trade-off between availability, latency, and consistency.

Chapter Summary

Concurrency control converts an interleaving of distributed operations into a controlled execution with defined correctness properties. Conflict serializability is conveniently represented by an acyclic precedence graph, while view serializability is more general but harder to enforce. Two-phase locking provides serializability through disciplined lock acquisition; strict variants improve recovery. Timestamp ordering eliminates lock waits but may cause aborts. Optimistic control delays conflict detection until validation and is effective when conflicts are rare. MVCC and snapshot isolation improve read concurrency, yet snapshot isolation can permit write skew and is not equivalent to serializability. Distributed deadlocks arise because dependencies are scattered across sites; they require prevention, avoidance, or global detection and recovery. Correct system design must integrate concurrency control with replication, failure handling, atomic commit, monitoring, and business invariants.

Key Terms

Transaction: A logical unit of work that satisfies defined atomicity and isolation rules.

Schedule: An ordering of operations from one or more transactions.

Conflict: A pair of operations from different transactions on the same item where at least one is a write.

Conflict serializability: Equivalence to a serial schedule based on conflicting-operation order.

View serializability: Equivalence preserving reads-from relationships and final writes.

Precedence graph: A directed graph used to test conflict serializability.

Shared lock: A lock permitting compatible reads but not conflicting writes.

Exclusive lock: A lock required for writing and incompatible with other access locks.

Two-phase locking: A protocol with separate lock acquisition and lock-release phases.

Strict 2PL: 2PL that holds exclusive locks until commit or abort.

Timestamp ordering: A protocol that orders conflicting operations by transaction timestamps.

Optimistic concurrency control: Validation-based control that assumes conflicts are uncommon.

MVCC: A method that maintains multiple committed versions for concurrent access.

Snapshot isolation: Execution in which reads use a consistent snapshot and concurrent writes conflict.

Write skew: A constraint violation caused by concurrent updates to different items after overlapping reads.

Wait-for graph: A graph whose edges represent transactions waiting for other transactions.

Distributed deadlock: A wait cycle whose dependencies span multiple sites.

Deadlock victim: The transaction selected for rollback to break a deadlock.

Fencing token: A monotonically changing authority identifier that prevents stale actors from writing.

Review Questions

Short Answer Questions

1. What conditions make two database operations conflict?
2. Why does an acyclic precedence graph imply conflict serializability?
3. Distinguish strict 2PL from basic 2PL.
4. What is the principal assumption behind optimistic concurrency control?
5. Why can local deadlock graphs fail to reveal a distributed deadlock?

Long Answer Questions

1. Compare locking, timestamp ordering, OCC, and MVCC in terms of blocking, aborts, workload suitability, and distributed implementation challenges.
2. Explain snapshot isolation and construct a write-skew example showing why it is weaker than serializability.
3. Discuss how replicated data changes the meaning of serializability and describe two ways to coordinate replicas.
4. Explain distributed deadlock prevention, detection, and recovery, including the trade-offs of each.
5. Analyze the relationship between concurrency control and two-phase commit in a distributed transaction system.

Analytical / Application Questions

1. T₁ holds a lock at site A and waits for a lock held by T₂ at site B; T₂ waits for a lock held by T₁ at site A. Identify the global condition, propose two prevention methods, and recommend a victim-selection criterion.
2. A workload is 95% short reads, has occasional long analytical queries, and experiences frequent write skew under snapshot isolation. Recommend a concurrency-control design and justify how it protects cross-row invariants.
3. Design a reservation protocol for a replicated inventory item across two regions. State the consistency guarantee, lock or version strategy, failure behavior, and metrics needed to evaluate it.

Multiple Choice Questions with Answers

Question 1

Which condition indicates that a schedule is not conflict-serializable?

A. Its precedence graph contains a directed cycle.

B. It contains two read operations on different items.

C. Every transaction has at least one write.

D. All transactions commit successfully.

Correct Answer: A. Its precedence graph contains a directed cycle.

Question 2

What is the defining property of two-phase locking?

A. Transactions use only exclusive locks.

B. A transaction has a growing phase followed by a shrinking phase.

C. Locks are acquired only after validation.

D. All timestamps are generated by physical clocks.

Correct Answer: B. A transaction has a growing phase followed by a shrinking phase.

Question 3

Under basic timestamp ordering, a read of X by Tᵢ is rejected when:

A. TS(Tᵢ) is greater than read_TS(X).

B. TS(Tᵢ) equals the transaction count.

C. TS(Tᵢ) is less than write_TS(X).

D. X has more than one version.

Correct Answer: C. TS(Tᵢ) is less than write_TS(X).

Question 4

Which workload is generally most suitable for optimistic concurrency control?

A. A workload with frequent conflicts on a single hot row.

B. A workload with long transactions and nearly universal overlap.

C. A workload in which every transaction writes all records.

D. A read-heavy workload with relatively infrequent conflicts.

Correct Answer: D. A read-heavy workload with relatively infrequent conflicts.

Question 5

Which anomaly can occur under ordinary snapshot isolation?

A. Write skew.

B. A read of an uncommitted value by definition.

C. A lost update on the same item under first-committer-wins.

D. A violation of atomic commit caused solely by MVCC.

Correct Answer: A. Write skew.

Question 6

What does a directed cycle in a complete wait-for graph represent?

A. A successful serial order.

B. A distributed deadlock.

C. A completed validation phase.

D. A replica with no active transactions.

Correct Answer: B. A distributed deadlock.

Question 7

Why is local deadlock detection insufficient in a distributed database?

A. Local sites cannot hold locks.

B. Only read operations create waits.

C. A cycle may be formed by edges observed at different sites.

D. Transactions never communicate across sites.

Correct Answer: C. A cycle may be formed by edges observed at different sites.

Question 8

Which technique prevents a stale former leader from writing after failover?

A. A shared lock alone.

B. A longer analytical query.

C. A dirty read.

D. A fencing token or epoch.

Correct Answer: D. A fencing token or epoch.

Question 9

What is the main purpose of strictness in strict 2PL?

A. To prevent dirty reads and simplify recovery by retaining exclusive locks until completion.

B. To eliminate all network messages.

C. To permit every transaction to write without waiting.

D. To guarantee that no transaction ever aborts.

Correct Answer: A. To prevent dirty reads and simplify recovery by retaining exclusive locks until completion.

Question 10

Two transactions read the same snapshot, update different rows, and together violate a multi-row constraint. Which explanation is most accurate?

A. This is impossible under any MVCC system.

B. It is a write-skew anomaly that snapshot isolation may permit.

C. It is necessarily a distributed deadlock.

D. It proves that timestamp ordering was used.

Correct Answer: B. It is a write-skew anomaly that snapshot isolation may permit.