1
Unit 4: Distributed Concurrency Control
1. Serializability Theory
2. Taxonomy of Concurrency Control Mechanisms
3. Lock Based Concurrency Control Algorithms
4. Time-Stamp Based Concurrency Control Algorithms
5. Optimistic Concurrency Control Algorithms
6. Deadlock management
11. Distributed Concurrency Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361
11.1 Serializability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362
11.2 Taxonomy of Concurrency Control Mechanisms. . . . . . . . . . . . . . . . . 367
11.3 Locking-Based Concurrency Control Algorithms . . . . . . . . . . . . . . . . 369
11.3.1 Centralized 2PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373
11.3.2 Distributed 2PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374
11.4 Timestamp-Based Concurrency Control Algorithms . . . . . . . . . . . . . . 377
11.4.1 Basic TO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
11.4.2 Conservative TO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 381
11.4.3 Multiversion TO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
11.5 Optimistic Concurrency Control Algorithms . . . . . . . . . . . . . . . . . . . . 384
11.6 Deadlock Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387
11.6.1 Deadlock Prevention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389
11.6.2 Deadlock Avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390
11.6.3 Deadlock Detection and Resolution . . . . . . . . . . . . . . . . . . . . . 391
1. Serializability Theory
• Serializability is the most widely accepted correctness criterion for concurrency
control algorithms.
• A history (or schedule) is serializable if its outcome is equivalent to some serial
execution of the same transactions.
Types of Serializability:
1. Conflict Serializability – Ensures that transactions do not interfere with each
other based on conflicting operations (read-write or write-write).
2. View Serializability – Ensures that the final outcome of transactions is the
same as in a serial execution.
Example:
Consider two transactions:
Er. Sital Prasad mandal
1|Page
2
T1: Read(X), X = X + 10, Write(X)
T2: Read(X), X = X * 2, Write(X)
If interleaved incorrectly, T1 and T2 could lead to inconsistencies. Serializability ensures
that the result is consistent with either T1 → T2 or T2 → T1 execution.
2. Taxonomy of Concurrency Control Mechanisms
Concurrency control mechanisms are broadly classified as:
1. Pessimistic Concurrency Control – Synchronizes transactions early to
avoid conflicts.
2. Optimistic Concurrency Control – Allows transactions to execute freely
and validates them at commit time.
3. Hybrid Approaches – Combine aspects of both pessimistic and optimistic
methods.
Further classification includes:
• Locking-based methods
• Timestamp-based methods
• Validation-based methods
• Multi-version concurrency control (MVCC).
3. Lock-Based Concurrency Control Algorithms
Locking mechanisms use read and write locks to prevent conflicts.
Types of Locking Protocols:
1. Two-Phase Locking (2PL)
o Phase 1 (Growing Phase): Transaction acquires all locks it needs.
o Phase 2 (Shrinking Phase): Transaction releases locks and cannot
acquire new ones.
o Ensures conflict serializability but can cause deadlocks.
2. Centralized 2PL – A single lock manager controls locks.
3. Distributed 2PL – Locking is managed across multiple sites.
Er. Sital Prasad mandal
2|Page
3
4. Timestamp-Based Concurrency Control Algorithms
Timestamp-based concurrency control assigns a unique timestamp to each
transaction at its start.
Types of Timestamp Ordering Algorithms:
1. Basic TO Algorithm – Transactions are executed in timestamp order.
Er. Sital Prasad mandal
3|Page
4
2. Conservative TO Algorithm – Delays transaction execution until it is safe
to proceed.
3. Multi-Version TO Algorithm (MVTO) – Maintains multiple versions of
data to avoid blocking reads.
Example:
• Transaction T1 gets timestamp 100, and T2 gets 200.
• If T2 tries to write a value before T1 completes, it is aborted and restarted.
5. Optimistic Concurrency Control Algorithms
Optimistic algorithms assume that conflicts are rare and allow transactions to execute
freely in three phases:
1. Read Phase – Transactions read data into local copies.
2. Validation Phase – Checks for conflicts before commit.
3. Write Phase – If no conflicts, changes are made permanent.
Example:
• If T1 and T2 read the same value but T2 writes first, then T1 is aborted if it
tries to write an outdated value.
6. Deadlock Management
Deadlocks occur when two transactions wait indefinitely for resources locked by each
other.
Deadlock Handling Techniques:
1. Deadlock Prevention – Enforces ordering rules to avoid deadlocks.
o Wait-Die: Older transactions wait; younger ones abort.
o Wound-Wait: Older transactions abort younger ones.
2. Deadlock Avoidance – Uses a wait-for graph to predict and prevent
cycles.
3. Deadlock Detection and Resolution – Detects deadlocks using a wait-
for graph and resolves them by aborting transactions.
Er. Sital Prasad mandal
4|Page
5
Example:
• T1 locks X → T2 locks Y → T1 waits for Y → T2 waits for X →
Deadlock.
Serializability Theory
• A history (or schedule) is defined as an interleaved order of execution of
transactions' operations.
• Conflicting operations are operations that access the same database entity, where
at least one is a write operation. Conflicts are categorized as read-write (or write-
read) and write-write.
• A history is serial if the operations of various transactions are not interleaved.
Serial execution maintains database consistency.
• A history H is serializable if it is conflict equivalent to a serial history.
• The primary function of a concurrency controller is to generate a serializable
history for the execution of pending transactions.
• Snapshot isolation is a weaker version of serializability that allows read
transactions to read stale data, which can provide better performance but may
result in non-serializable histories.
Taxonomy of Concurrency Control Mechanisms
• Concurrency control approaches can be classified based on the mode of database
distribution, network topology, or synchronization primitive.
• The most common classification criterion is the synchronization primitive,
which leads to algorithms based on mutually exclusive access to shared data
(locking) and those that order transaction execution (protocols).
• Concurrency control mechanisms are grouped into pessimistic and optimistic
methods. Pessimistic algorithms synchronize early, while optimistic algorithms
delay synchronization until termination.
Locking-Based Concurrency Control Algorithms
• Locking ensures that a data item shared by conflicting operations is accessed by
one operation at a time. A "lock" is associated with each lock unit.
• Two types of locks exist: read lock (rl) and write lock (wl). Read locks are
compatible, but read-write or write-write locks are not.
Er. Sital Prasad mandal
5|Page
6
• The two-phase locking (2PL) rule states that a transaction should not request a
lock after releasing one. 2PL algorithms have a growing phase (obtaining locks)
and a shrinking phase (releasing locks).
• Strict two-phase locking releases all locks together when the transaction
terminates (commits or aborts).
• Locking-based algorithms may cause deadlocks.
• Centralized 2PL delegates lock management to a single site.
• Distributed 2PL involves lock management at multiple sites.
Timestamp-Based Concurrency Control Algorithms
• Timestamp-based algorithms select a serialization order a priori and execute
transactions accordingly.
• Each transaction is assigned a unique timestamp at initiation.
• The timestamp ordering (TO) rule states that given two conflicting operations,
is executed before if and only if ts() < ts().
• The basic TO algorithm is a straightforward implementation of the TO rule.
• Conservative TO algorithms reduce transaction restarts by delaying each
operation until there is assurance that no operation with a smaller timestamp can
arrive.
• Multiversion TO attempts to eliminate the restart overhead cost of transactions.
Optimistic Concurrency Control Algorithms
• Optimistic algorithms delay the validation phase until just before the write phase.
• Transactions make updates on local copies of data items, and the validation phase
checks if these updates would maintain database consistency.
• Timestamps are associated with transactions at the beginning of their validation
step.
Deadlock Management
• Locking-based concurrency control algorithms may result in deadlocks.
• Deadlock prevention methods guarantee that deadlocks cannot occur.
• Deadlock avoidance involves checking for the possibility of deadlock before
granting a lock.
• Deadlock detection and resolution involves detecting deadlocks and then
resolving them, typically by aborting a transaction.
• Three methods of detecting distributed deadlocks are centralized, distributed, and
hierarchical deadlock detection.
Er. Sital Prasad mandal
6|Page
7
1. Serializability Theory
Serializability ensures that a set of concurrent transactions produces the same results as if
they were executed sequentially. It is the gold standard for correctness in transaction
processing.
Types of Serializability
1. Conflict Serializability: Ensures that transactions follow a correct execution order to
avoid conflicts.
2. View Serializability: Ensures that transactions produce the same output as an
equivalent serial schedule.
2. Taxonomy of Concurrency Control Mechanisms
Concurrency control ensures multiple transactions do not interfere with each other. The
main approaches are:
1. Pessimistic Concurrency Control: Prevents conflicts by using locks.
2. Optimistic Concurrency Control: Assumes conflicts are rare and checks for them at
commit time.
3. Lock-Based Concurrency Control
Locking is a widely used technique for concurrency control. Common types include:
1. Shared Lock (S): Allows multiple transactions to read but not write.
2. Exclusive Lock (X): Allows only one transaction to read and write.
The Two-Phase Locking (2PL) protocol is commonly used to prevent concurrency
conflicts.
4. Timestamp-Based Concurrency Control
Each transaction is assigned a unique timestamp to ensure a conflict-free schedule.
Timestamp ordering rules ensure transactions execute in the correct order.
5. Optimistic Concurrency Control (OCC)
OCC assumes conflicts are rare and follows a three-phase execution:
1. Read Phase: Transaction reads values and performs calculations.
2. Validation Phase: System checks for conflicts.
3. Write Phase: If no conflict, changes are committed.
Er. Sital Prasad mandal
7|Page
8
6. Deadlock Management
Deadlocks occur when two or more transactions wait for each other indefinitely. Methods
to handle deadlocks include:
Deadlock Detection
Deadlocks can be detected using a Wait-for Graph (WFG). The system detects cycles and
rolls back transactions to break the cycle.
Deadlock Prevention
1. Wait-Die: Older transactions wait, younger transactions abort.
2. Wound-Wait: Older transactions force younger ones to abort.
Deadlock Avoidance
Deadlocks can be avoided using timestamp ordering and timeouts to abort long-waiting
transactions.
Er. Sital Prasad mandal
8|Page