Timestamp-Based Protocol

Overview

The Timestamp Ordering Protocol is a concurrency control mechanism that uses transaction timestamps — rather than locks — to determine the serialization order of conflicting operations. Each transaction receives a unique timestamp when it begins, and the protocol ensures that conflicting read/write operations execute in timestamp order.

The most significant advantage: No locks means no deadlocks. This eliminates the need for deadlock detection, prevention, or timeout mechanisms entirely.

Per-Data-Item Bookkeeping

For each data item X in the database, the system maintains two timestamp values:

These fields record "who was the most recent reader/writer" and are updated after each successful operation.

Protocol Rules

Read Rule — Transaction Ti wants to read(X)

Write Rule — Transaction Ti wants to write(X)

Worked Example

Thomas Write Rule (Optimization)

The basic protocol aborts Ti when TS(Ti) < W-timestamp(X) for a write. But the Thomas Write Rule observes that if a newer transaction has already written X, then Ti's write is obsolete — it would be immediately overwritten anyway. So instead of aborting, we simply skip the write:

Timestamp Protocol Guarantees

Preventing Cascading Rollbacks

The basic timestamp protocol allows dirty reads (reading uncommitted data). To prevent cascading rollbacks:

1. Strict Timestamp Ordering: Delay reads until the writing transaction commits
2. Buffered Writes: Hold writes in a buffer until commit, then apply all at once
3. Commit Dependencies: Track which transactions read from uncommitted writers

Comparison: Timestamp vs. Lock-Based Protocols

Advantages and Disadvantages

Advantages:

• No deadlocks (eliminates a major complexity in database systems)
• Serialization order is predictable (based on start time)
• No waiting for locks — transactions proceed immediately or abort
• Good for distributed systems (timestamps are easy to coordinate)

Disadvantages:

• High abort rate under heavy write contention (many restarts)
• Starvation: a long transaction may be repeatedly aborted by newer ones
• Cascading rollback possible without strict variant
• Maintaining timestamps for every data item adds storage overhead

Summary

The timestamp protocol provides deadlock-free concurrency control by ordering all operations according to transaction start times. It works well for read-dominated workloads with low conflict but suffers from excessive aborts under heavy write contention. The Thomas Write Rule optimization reduces unnecessary aborts by skipping obsolete writes rather than aborting their transactions.