Page 7: Timestamp-Based Protocols

First-Come-First-Served Approach

Instead of locks, use timestamps to decide order. Like taking a number at a deli counter.

Each Data Item Has:

• R-timestamp(Q): Latest transaction that read Q

• W-timestamp(Q): Latest transaction that wrote Q

Basic Timestamp Rules

For Read(Q) by Ti:

• If TS(Ti) < W-timestamp(Q): Too late! Someone already overwrote it → ROLLBACK

• Else: Allow read, update R-timestamp(Q)

For Write(Q) by Ti:

• If TS(Ti) < R-timestamp(Q): Too late! Someone needed old value → ROLLBACK

• If TS(Ti) < W-timestamp(Q): Too late! Someone already wrote newer value → ROLLBACK

• Else: Allow write, update W-timestamp(Q)

Example:

CopyT27 (TS=10), T28 (TS=15)
1. T27: Read(Q) → OK, R-timestamp(Q) = 10
2. T28: Write(Q) → OK, W-timestamp(Q) = 15  
3. T27: Write(Q) → REJECT! TS(27)=10 < W-timestamp(Q)=15

Thomas' Write Rule

Smart optimization: Instead of rollback, ignore obsolete writes.

If TS(Ti) < W-timestamp(Q) but TS(Ti) ≥ R-timestamp(Q): → Just ignore the write (don't rollback)

Benefits:

• ✅ No deadlocks (no waiting)

• ❌ Possible starvation of long transactions