Distributed Concurrency Control: Locks, Protocols & Recovery

Core Concepts

What is Distributed Concurrency Control?

Distributed concurrency control ensures that transactions in a distributed database system execute correctly and consistently despite:

• Concurrent access from multiple sites.
• Network delays between nodes.
• Partial failures (e.g., a site crashing).

Without it, you’d face:

• Dirty reads (reading uncommitted data).
• Lost updates (overwriting changes).
• Inconsistent states (e.g., a bank account showing two different balances).

Key Mechanisms

1. Locking Protocols

Locks prevent conflicting operations on shared data. In distributed systems, locks must be global (across sites) or local (per site), with protocols to handle deadlocks and timeouts.

Types of Locks:

Two-Phase Locking (2PL) in Distributed Systems

• Growing Phase: Acquire all locks (no releases).
• Shrinking Phase: Release all locks (no new acquisitions).
• Problem: Deadlocks can occur if two transactions wait for each other’s locks.

stateDiagram-v2
    [*] --> Waiting
    Waiting --> AcquireLock: Request S/X lock
    AcquireLock --> HoldLock: Lock granted
    HoldLock --> ReleaseLock: Transaction commits
    ReleaseLock --> [*]
    HoldLock --> Deadlock: Circular wait detected
    Deadlock --> Timeout: Abort or rollback

Worked Example: Daraz Order Processing

• Scenario: Two users (A and B) try to update the stock of the same product simultaneously.
• Locking:
  • User A acquires an X-lock on the product’s stock.
  • User B requests the same lock but is blocked until User A releases it.
• Outcome: No lost updates; stock is updated atomically.

2. Timestamp-Based Protocols

Instead of locks, transactions are ordered by timestamps (logical clocks). Two main approaches:

a) Optimistic Concurrency Control (OCC)

• Assumption: Conflicts are rare.
• Steps:
  1. Execute transaction locally.
  2. Validate at commit time using timestamps.
  3. Roll back if conflict detected.
• Pros: No deadlocks; high concurrency.
• Cons: Overhead in validation and rollback.

b) Conservative vs. Pessimistic Timestamps

Worked Example: NEPSE Stock Trading

• Scenario: Two traders (A and B) try to buy the same share at the same price.
• Timestamp Order:
  • Trader A’s order gets timestamp TS=500.
  • Trader B’s order gets timestamp TS=501.
• Outcome: Trader B’s order executes first (higher timestamp), and Trader A’s order is rejected or rolled back.

3. Two-Phase Commit (2PC)

Ensures atomicity across distributed transactions. Used in systems like Khalti payments or Ncell billing.

Phases:

1. Prepare Phase:
   • Coordinator sends "prepare to commit" to all participants.
   • Participants vote yes (can commit) or no (cannot commit).
2. Commit Phase:
   • If all yes: Coordinator sends "commit".
   • If any no: Coordinator sends "abort".

flowchart TD
    A["Start"] --> B["Coordinator sends Prepare"]
    B --> C{"All Participants Respond"}
    C -->|"All Yes"| D["Coordinator sends Commit"]
    C -->|"Any No"| E["Coordinator sends Abort"]
    D --> F["All Commit"]
    E --> G["All Rollback"]

Worked Example: Khalti Payment Transfer

• Scenario: User A transfers ₹1000 to User B via Khalti.
• 2PC Steps:
  1. Khalti’s coordinator asks both users’ banks: "Can you deduct ₹1000 and credit ₹1000?"
  2. Both banks reply yes.
  3. Coordinator commits the transaction; both banks update balances.

Failure Case:

• If Bank B crashes during prepare, the coordinator aborts the transaction to avoid inconsistent states.

4. Recovery Techniques

Distributed systems must recover from failures without violating ACID properties.

a) Checkpointing

• Periodically save the state of all sites.
• Problem: High overhead; may lose recent transactions.

b) Write-Ahead Logging (WAL)

• Log all changes before applying them to the database.
• Example: Ncell’s billing system logs every top-up before updating the user’s balance.

c) Distributed Deadlock Detection

• Centralized: A deadlock detector monitors all sites (single point of failure).
• Distributed: Each site detects deadlocks locally (e.g., using wait-for graphs).

Worked Example: Kathmandu Traffic Management

• Scenario: Three traffic lights (A, B, C) must coordinate to avoid deadlocks.
• Solution:
  • Each light uses timestamp ordering to decide which vehicle gets priority.
  • If a deadlock is detected (e.g., A waits for B, B waits for C, C waits for A), the system aborts one transaction and retries.

Comparison of Concurrency Control Methods

In the Real World

1. Khalti Payments

   • Idea Used: Two-Phase Commit (2PC) ensures that money is deducted from one account and credited to another atomically, even if a bank server fails.
   • How: The Khalti coordinator acts as the 2PC coordinator, polling all participating banks for "prepare" votes before committing.

2. NEPSE Stock Exchange

   • Idea Used: Timestamp-based concurrency control to order trades and prevent duplicate executions.
   • How: Each trade is assigned a timestamp, and only the highest-priority (latest timestamp) trade executes if conflicts arise.

3. Pathao Ride Allocation

   • Idea Used: Distributed locking to prevent two drivers from accepting the same ride request.
   • How: When a user requests a ride, Pathao’s system acquires an exclusive lock on the ride request until a driver accepts or the request times out.

Exam Tip

This unit is heavily tested on:

1. Definitions: Know the difference between 2PL, OCC, and timestamp ordering.
2. Worked Examples: Be ready to trace a 2PC protocol or a deadlock scenario step-by-step.
3. Real-World Applications: Link concepts to Khalti, NEPSE, or Daraz in explanations.
4. Diagrams: Draw wait-for graphs, 2PC flowcharts, and locking hierarchies clearly.
5. Shortcomings: For each method, list at least one disadvantage (e.g., "2PC is blocking").

Common Pitfalls:

• Confusing pessimistic vs. optimistic concurrency.
• Forgetting that distributed deadlocks require global detection.
• Not accounting for network partitions in recovery.

Summary Checklist

Before the exam, ensure you can: ✅ Explain why locks alone fail in distributed systems. ✅ Draw a wait-for graph and identify deadlocks. ✅ Trace a 2PC protocol with success/failure cases. ✅ Compare timestamp ordering vs. locking in terms of concurrency and overhead. ✅ Describe how Khalti or NEPSE uses these concepts in practice.