Timestamp Ordering Protocol

In the physical world, time flows in one direction—events happen in sequence, and this sequence determines cause and effect. When you deposit money before making a purchase, the order matters: the deposit must complete before funds become available. Database systems face this exact challenge: how do we establish a definitive, unambiguous order for concurrent transactions?

Locking protocols solve this problem by preventing simultaneous access—but they introduce complexity: deadlocks, lock management overhead, and waiting. What if there were a fundamentally different approach? What if, instead of preventing conflicts through locks, we could detect conflicts by assigning each transaction a unique position in a timeline?

This is the essence of timestamp-based concurrency control—a paradigm that uses temporal ordering rather than mutual exclusion to ensure serializability.

In database concurrency control, a timestamp is a unique identifier assigned to each transaction at the moment it begins. Unlike wall-clock time in everyday usage, database timestamps have specific mathematical properties that make them suitable for ordering operations.

Formal Definition:

A timestamp is a value from a totally ordered domain, typically the natural numbers or real numbers, assigned to each transaction T such that:

1. Uniqueness: No two distinct transactions receive the same timestamp
2. Monotonicity: If transaction T₁ starts before T₂, then TS(T₁) < TS(T₂)
3. Immutability: Once assigned, a transaction's timestamp never changes

These properties ensure that timestamps establish a total ordering over all transactions—every pair of transactions can be unambiguously compared to determine which "logically" comes first.

The Temporal Metaphor:

Think of timestamps as VIP entry numbers at an exclusive event. Each guest receives a unique number upon arrival. Even if guests arrive seconds apart, their entry numbers establish an unambiguous precedence. Later, if two guests want the same seat, we check their entry numbers—the lower number has priority. The guest with the higher number must either wait or find another seat.

In database terms:

• Guests = Transactions
• Entry numbers = Timestamps
• Wanting the same seat = Accessing the same data item
• Priority rules = Timestamp ordering protocols

Understanding timestamps requires contrasting them with the lock-based approach we've studied earlier. These aren't just different techniques—they represent fundamentally different philosophies for achieving serializability.

Lock-Based Approach:

• Conflict Prevention: Blocks transactions to prevent conflicts from occurring
• Dynamic Decisions: Order determined at runtime based on who acquired locks first
• Pessimistic: Assumes conflicts will happen, so prevent them preemptively
• Blocking: Transactions wait when they encounter locked resources
• Deadlock Risk: Circular waits can occur, requiring detection/resolution

Timestamp-Based Approach:

• Conflict Detection: Allows transactions to proceed, detects violations afterward
• Pre-determined Order: Order fixed when transaction starts (by timestamp assignment)
• Optimistic Tendency: Lets operations proceed, validates correctness via timestamps
• Non-Blocking with Rollbacks: No waiting for locks, but may need to restart
• No Deadlocks: Circular waits are impossible (we'll see why shortly)

A crucial insight is that database timestamps represent logical time, not physical time. While they may correlate with wall-clock time, their purpose is defining an equivalence class of serial executions.

The Serializability Connection:

Recall that a schedule is serializable if it is equivalent to some serial schedule. The timestamp assigned to each transaction defines which serial schedule we're targeting: the one that executes transactions in timestamp order.

If transaction T₁ has timestamp 100 and T₂ has timestamp 200, then:

• Any correct execution must produce results as if T₁ ran completely before T₂
• The actual interleaving can differ, but the effect must match T₁ → T₂

This is a profound shift in thinking. We're not asking "did T₁ physically complete before T₂ started?" We're asking "does the outcome match a world where T₁ ran first?"

Logical Clocks and Lamport's Insight:

The concept of logical time in computer science was formalized by Leslie Lamport in his seminal 1978 paper "Time, Clocks, and the Ordering of Events in a Distributed System." Lamport showed that:

1. Physical clocks are unreliable for ordering events across multiple processors
2. What matters is establishing a happened-before relationship
3. Logical clocks can capture causality without physical synchronization

Database timestamps borrow this fundamental insight: we don't need perfect physical time—we need a consistent ordering that all participants agree upon. A simple incrementing counter can serve this purpose in a centralized database, while more sophisticated protocols (like vector clocks or hybrid logical clocks) extend the idea to distributed systems.

For timestamps to serve as the foundation of concurrency control, they must satisfy specific mathematical properties. Understanding these properties clarifies what makes a timestamp assignment "valid" and why certain implementation choices work while others fail.

Why These Properties Matter:

Uniqueness prevents the protocol from getting stuck when two transactions want the same resource—one timestamp is always strictly greater.

Monotonicity ensures that the logical ordering respects physical causality. If you start a transaction after observing another's results, your timestamp will be higher, modeling the dependency correctly.

Immutability prevents complications where a transaction's "position" could shift mid-execution, potentially violating orders already established with other transactions.

Violating any of these properties introduces correctness holes. For example, if timestamps could change, a transaction might pass a read check at time 100, have its timestamp bumped to 50, and then violate the write rule for another transaction at timestamp 75.

Given the essential properties, how do real database systems assign timestamps? Two primary approaches dominate, each with distinct trade-offs.

Hybrid Approaches:

Modern distributed databases often combine both approaches. For example:

• Hybrid Logical Clocks (HLC): Combine physical timestamps with logical components. The physical part provides rough ordering aligned with real time, while the logical component resolves ties and handles clock skew.

• TrueTime (Google Spanner): Uses GPS and atomic clocks to bound uncertainty in physical time, then waits out the uncertainty before committing. This gives the benefits of real-time ordering with formal correctness guarantees.

For learning purposes, we'll focus on the conceptually cleaner logical counter approach, understanding that production systems may add sophistication for distributed scenarios.

Transaction timestamps define when transactions logically occur. But for the protocol to work, we must also track which transactions have accessed each data item. This requires maintaining timestamps at the data level.

Two Critical Timestamps Per Data Item:

For each data item Q in the database, we maintain:

1. W-timestamp(Q) — The largest timestamp of any transaction that has successfully written Q
2. R-timestamp(Q) — The largest timestamp of any transaction that has successfully read Q

These data item timestamps are essential for conflict detection. When a transaction wants to read or write Q, we compare the transaction's timestamp against Q's timestamps to determine if the operation would violate the intended serial order.

Example:

Suppose data item Q has:

• W-timestamp(Q) = 100 (written by transaction with TS = 100)
• R-timestamp(Q) = 150 (read by transaction with TS = 150)

Now transaction T with TS(T) = 120 wants to write Q.

Question: Should this write be permitted?

The timestamp ordering protocol would reject this write. Why? Because a transaction with timestamp 150 has already read Q's value. If we allowed T (timestamp 120) to write, we'd be saying "T occurred before the TS=150 transaction"—but then the TS=150 transaction should have seen T's value, not the TS=100 value it actually read.

This is the essence of timestamp ordering: enforcing that the timestamps tell a consistent story about what happened when.

One of the most elegant properties of timestamp ordering is the impossibility of deadlocks. This isn't a happy accident—it's a direct consequence of how timestamps define ordering.

The Deadlock Problem in Locking:

Recall that deadlocks occur when there's a cycle in the wait-for graph:

• Transaction T₁ waits for T₂ to release lock on A
• Transaction T₂ waits for T₁ to release lock on B

Neither can proceed—they're stuck in a circular dependency.

Why This Cannot Happen with Timestamps:

In timestamp ordering, transactions don't wait for each other. When a conflict is detected:

• The transaction whose operation would violate timestamp order is aborted and restarted
• The other transaction proceeds without any blocking

There is no "waiting"—hence no wait-for graph, hence no cycles, hence no deadlocks.

Formal Argument:

Let's prove this more rigorously. Suppose, for contradiction, that deadlock occurs in timestamp ordering.

1. Deadlock requires a cycle: T₁ waits for T₂, T₂ waits for T₃, ..., Tₙ waits for T₁
2. In timestamp ordering, Tᵢ "waits" for Tⱼ only if Tⱼ has a higher timestamp and has accessed a data item that Tᵢ wants
3. This means TS(T₁) < TS(T₂) < TS(T₃) < ... < TS(Tₙ) < TS(T₁)
4. But TS(T₁) < TS(T₁) is a contradiction—no value is less than itself

Therefore, deadlock cannot occur. ∎

The Trade-off:

The absence of deadlocks comes at a cost: transactions may be aborted and restarted multiple times. In high-contention scenarios, the same transaction might repeatedly conflict with newer transactions, leading to starvation. Various enhancements (which we'll explore later) address this trade-off.

We've established the conceptual foundation for timestamp-based concurrency control. Let's consolidate the key insights:

What's Next:

Now that we understand what timestamps represent and why they form a valid basis for ordering, we'll explore the two primary methods for generating timestamps: system clock timestamps and logical counters. Each approach has its place depending on system architecture and requirements.