Basic Timestamp Protocol

We've examined the individual components of the Basic Timestamp Protocol: RTS and WTS timestamps, read rules, and write rules. Now it's time to see how these pieces combine into a complete, functioning concurrency control mechanism.

Protocol Execution encompasses everything that happens from when a transaction begins until it commits or aborts. This includes timestamp assignment, operation processing, conflict detection, abort handling, and commit processing. Understanding the complete protocol execution enables you to predict system behavior, diagnose concurrency issues, and make informed design decisions.

Every transaction under the Basic Timestamp Protocol goes through a defined lifecycle. Understanding this lifecycle is fundamental to understanding protocol execution.

Phase 1: Begin Transaction

When a transaction T begins:

1. A unique timestamp TS(T) is assigned from a monotonically increasing source
2. The transaction enters the ACTIVE state
3. No other initialization is required—no locks to acquire, no resources to reserve

Timestamp sources can be:

• System clock: Physical time with sub-millisecond resolution
• Logical counter: Atomic counter incremented on each new transaction
• Hybrid: Combination of physical time and logical sequence number

Phase 2: Execute Operations

During execution, each operation (read or write) is processed according to the rules we've studied:

• Read(X): Check WTS(X), return value or abort, update RTS(X)
• Write(X, v): Check RTS(X) and WTS(X), write or abort, update WTS(X)

If any operation fails the timestamp checks, the transaction immediately aborts. There's no waiting, no retry-within-transaction.

Phase 3: Abort or Commit

If all operations succeed:

• Transaction can commit
• Changes become durable
• Transaction's effects are permanent

If any operation fails:

• Transaction aborts
• All changes are rolled back
• Transaction may restart with a new (larger) timestamp

Let's formalize the complete Basic Timestamp Protocol, integrating all components:

Transaction Start:

BEGIN_TRANSACTION(T):
    TS(T) := GET_TIMESTAMP()     // Assign unique, increasing timestamp
    state(T) := ACTIVE

Read Operation:

READ(T, X):
    IF TS(T) < WTS(X) THEN
        ABORT(T)
        RETURN FAILURE
    END IF
    
    value := X
    IF TS(T) > RTS(X) THEN
        RTS(X) := TS(T)
    END IF
    RETURN value

Write Operation (with Thomas Write Rule):

WRITE(T, X, v):
    IF TS(T) < RTS(X) THEN
        ABORT(T)
        RETURN FAILURE
    END IF
    
    IF TS(T) < WTS(X) THEN
        // Thomas Write Rule: ignore obsolete write
        RETURN SUCCESS
    END IF
    
    X := v
    WTS(X) := TS(T)
    RTS(X) := TS(T)
    RETURN SUCCESS

Abort Handling:

ABORT(T):
    state(T) := ABORTED
    ROLLBACK_CHANGES(T)          // Undo all writes by T
    RESTART_TRANSACTION(T)       // Begin new transaction with new TS
    // Note: RTS updates by T may remain (can't be easily undone)

Commit Processing:

COMMIT(T):
    IF state(T) = ACTIVE THEN
        state(T) := COMMITTED
        MAKE_DURABLE(changes(T))  // Write to stable storage
    END IF

Let's trace a complete multi-transaction scenario to see the protocol in action.

Scenario Setup:

• Data items: X (initial value = 100), Y (initial value = 200)
• Initial timestamps: WTS(X) = 0, RTS(X) = 0, WTS(Y) = 0, RTS(Y) = 0
• Transactions:
  • T1 (TS=10): R(X), W(Y, X+50)
  • T2 (TS=20): R(Y), W(X, Y*2)
  • T3 (TS=15): R(X), R(Y)

Analysis of the Trace:

• t1-t3: All reads succeed because WTS = 0 for both items initially
• t4: T2's write to X succeeds because TS(T2)=20 ≥ RTS(X)=15 and ≥ WTS(X)=0
• t5: T1's write to Y fails because TS(T1)=10 < RTS(Y)=20 (T2 already read Y)

T1 aborts because T2, which is "younger," has already read the value T1 wants to modify.

After T1 Restarts as T4 (TS=25):

The Basic Timestamp Protocol guarantees conflict serializability. Let's understand why and how to verify this.

The Serializability Theorem:

Any schedule produced by the Basic Timestamp Protocol (with or without Thomas Write Rule) is conflict-equivalent to the serial schedule that orders transactions by their timestamps.

Proof Intuition:

Conflicting operations are ordered by timestamp:

• If T1 reads X before T2 writes X, then TS(T1) < TS(T2) (enforced by write's RTS check)
• If T1 writes X before T2 reads X, then TS(T1) < TS(T2) (enforced by read's WTS check)
• If T1 writes X before T2 writes X, then TS(T1) < TS(T2) (enforced by write's WTS check)

Since all conflicts respect timestamp order, the schedule is equivalent to executing transactions in timestamp order.

Constructing the Precedence Graph:

To verify serializability, construct a precedence graph where:

• Nodes = committed transactions
• Edges = T1 → T2 if T1 and T2 conflict and T1's conflicting operation precedes T2's

For timestamp ordering, the graph always has edges only in the timestamp direction (smaller to larger). A graph with all edges going one direction cannot have cycles, so the schedule is always serializable.

While Basic Timestamp Ordering guarantees serializability, it does not guarantee recoverability. This is a critical limitation for practical systems.

The Dirty Read Problem:

Consider:

1. T1 (TS=10) writes X = 50
2. T2 (TS=20) reads X (gets 50, check passes: 20 ≥ WTS(10))
3. T2 uses value 50 in computation, commits
4. T1 aborts (for unrelated reasons)

T2 has committed with a value that was never durable—T1's write was rolled back. This is a dirty read leading to an unrecoverable schedule.

Solutions for Recoverability:

1. Strict Timestamp Ordering:

• Delay reads of uncommitted data
• When T wants to read X written by T', and T' hasn't committed:
  • Option A: T waits for T' to commit (introduces blocking)
  • Option B: T aborts and retries later

2. Commit Dependencies:

• Allow the read, but track that T depends on T'
• T cannot commit until T' commits
• If T' aborts, T must also abort (cascading abort)

3. Multi-Version Concurrency Control (MVCC):

• Keep multiple versions of each data item
• Readers access the most recent committed version
• Writers create new versions without affecting readers
• This is the approach used by most modern databases

Basic Timestamp Ordering and Two-Phase Locking (2PL) are two fundamentally different approaches to serializability. Understanding their differences helps in choosing the right protocol for specific workloads.

Implementing Basic Timestamp Ordering in a real system presents several challenges beyond the core algorithm.

Distributed Timestamp Ordering:

In distributed databases, timestamp ordering faces additional challenges:

1. Clock Skew: Physical clocks on different nodes differ; a transaction on node A might get TS=100 while a later transaction on node B gets TS=95.

2. Global Timestamp Source: Using a central timestamp server eliminates skew but creates a bottleneck and single point of failure.

3. Hybrid Logical Clocks (HLC): Combine physical time with logical counters; provide causality guarantees without tight synchronization.

4. TrueTime (Google Spanner): Uses GPS and atomic clocks to bound clock uncertainty; enables globally serializable transactions.

We've now covered the complete Basic Timestamp Protocol. Let's consolidate everything:

Where We Go From Here:

The Basic Timestamp Protocol establishes fundamental concepts that evolve into more practical protocols:

• Strict Timestamp Ordering: Adds recoverability by delaying reads of uncommitted data
• Multiversion Timestamp Ordering: Keeps old versions to avoid read aborts
• MVCC: Full multi-version approach used by PostgreSQL, Oracle, etc.
• Snapshot Isolation: MVCC-based isolation level with specific trade-offs

These topics are covered in subsequent modules of this chapter.