Timestamp Ordering - Learning Module

Loading content...

0/241

Ordering Transactions

From Timestamps to Serial Order

We've established that each transaction receives a unique timestamp at its start. We've seen that data items track the timestamps of transactions that read and write them. Now we reach the central question: how do these timestamps actually create a transaction ordering, and how does the protocol enforce it?

The genius of timestamp ordering lies in a simple principle: timestamps define a serial schedule, and the protocol ensures that the actual concurrent execution is equivalent to that serial schedule. Any operation that would violate this equivalence is rejected.

In this page, we'll formalize this connection, present the complete protocol rules, prove their correctness, and work through detailed examples that illuminate how ordering is maintained even under complex concurrent access patterns.

What You Will Learn

By the end of this page, you will understand how timestamps define an equivalent serial schedule, the formal read and write rules of the timestamp ordering protocol, a proof sketch of why these rules guarantee serializability, detailed examples tracing protocol execution, edge cases and their handling, and the complete algorithm for timestamp ordering.

Timestamps Define Serial Order

The fundamental insight of timestamp ordering is that the timestamp assignment at transaction start defines the serial schedule we want to emulate.

The Target Serial Schedule:

If we have transactions T₁, T₂, T₃ with timestamps 100, 200, 300 respectively, then the "target" serial schedule is:

Serial Schedule S: T₁ → T₂ → T₃
(Execute T₁ completely, then T₂ completely, then T₃ completely)

This serial schedule is obviously serializable—it is serial. Our actual concurrent execution may interleave operations differently, but the final database state and transaction results must match this target.

Serialization Equivalence:

Two schedules are equivalent if:

They involve the same transactions and operations
They produce the same final database state
Each transaction reads the same values in both schedules

Timestamp ordering ensures: the actual schedule is equivalent to the serial schedule ordered by timestamps.

Why Timestamp Order Works:

Consider what "T₁ happens before T₂" means in a serial execution:

T₂ reads data items as written by T₁ (if T₁ wrote them)
T₂'s writes overwrite T₁'s writes on the same items
T₁ cannot see any of T₂'s changes (it "happened before")

The timestamp protocol enforces exactly these properties:

If TS(T₁) < TS(T₂):
- T₂ must see T₁'s writes (or later writes, never earlier)
- T₂'s writes must not violate T₁'s reads
- T₁ cannot read values "from the future" written by T₂

By rejecting any operation that violates these rules, the protocol guarantees equivalence to timestamp-ordered serial execution.

Think of Timestamps as 'Serialization Points'

Each transaction's timestamp marks its position on a timeline of serial execution. The protocol asks: 'Does this operation make sense for a transaction at this position?' If yes, proceed. If no, the transaction must restart at a new (later) position where its operations would make sense.

The Read Rule

When transaction T with timestamp TS(T) wants to read data item Q, the protocol must determine whether this read is consistent with the intended serial order.

The Read Rule:

READ(T, Q):
    If TS(T) < W-timestamp(Q):
        // A transaction with larger timestamp has already written Q
        // In serial order, that write happens AFTER T
        // But T would be reading that "future" value -> VIOLATION
        ABORT T and restart with new timestamp
    Else:
        // TS(T) >= W-timestamp(Q)
        // T's read is consistent with serial order
        Execute the read
        R-timestamp(Q) = max(R-timestamp(Q), TS(T))

Why This Works:

If TS(T) < W-timestamp(Q):

Some transaction T' with TS(T') = W-timestamp(Q) > TS(T) has written Q
In the target serial schedule, T comes before T'
Therefore, T should read the value of Q from before T' wrote
But T' has already written, and we only keep current values
T cannot see the "old" value → abort and restart

Example:

Initial: Q = 10, W-timestamp(Q) = 50, R-timestamp(Q) = 50

T₁ with TS = 100 reads Q:
  Check: TS(T₁) = 100 >= W-timestamp(Q) = 50 ✓
  Read succeeds, returns Q = 10
  R-timestamp(Q) = max(50, 100) = 100

T₂ with TS = 200 writes Q = 20:
  (Assuming write succeeds)
  W-timestamp(Q) = 200, R-timestamp(Q) = 200

T₃ with TS = 150 tries to read Q:
  Check: TS(T₃) = 150 < W-timestamp(Q) = 200 ✗
  T₃ would be reading T₂'s value, but T₃ "happens before" T₂
  → ABORT T₃, restart with new timestamp (e.g., 250)

After restart, T₃ has timestamp 250. Now:

T₃' with TS = 250 reads Q:
  Check: TS(T₃') = 250 >= W-timestamp(Q) = 200 ✓
  Read succeeds, returns Q = 20
  R-timestamp(Q) = max(200, 250) = 250

Reading 'Stale' Values Is Fine

The read rule doesn't require reading the 'latest' value—it requires reading a value consistent with the transaction's timestamp position. If TS(T) = 100 and the only write was at TS = 50, T reads the TS = 50 value. This is correct: in the serial schedule, T (at position 100) would see the value written by the transaction at position 50.

The Write Rule

When transaction T with timestamp TS(T) wants to write data item Q, the protocol checks two conditions to ensure serial order consistency.

The Write Rule:

WRITE(T, Q, value):
    If TS(T) < R-timestamp(Q):
        // A transaction with larger timestamp has already read Q
        // That transaction saw the "old" value
        // T's write would change the value they should have seen -> VIOLATION
        ABORT T and restart with new timestamp
    
    Else If TS(T) < W-timestamp(Q):
        // A transaction with larger timestamp has already written Q
        // T's write is "obsolete" - its effects are overwritten anyway
        // Two options: abort, or use Thomas Write Rule (ignore)
        ABORT T and restart with new timestamp
        // OR with Thomas Write Rule: simply ignore this write (don't abort)
    
    Else:
        // TS(T) >= R-timestamp(Q) AND TS(T) >= W-timestamp(Q)
        // Write is consistent with serial order
        Execute the write: Q = value
        W-timestamp(Q) = TS(T)

Why Two Checks Are Needed:

Check 1: TS(T) < R-timestamp(Q)

If a transaction T' with larger timestamp read Q, it saw some value V. In the serial schedule, T (coming before T') should have written first, and T' should have seen T's value. But T' already read V ≠ T's write. The read is now inconsistent → abort T.

Check 2: TS(T) < W-timestamp(Q)

If a transaction T'' with larger timestamp already wrote Q, then in the serial schedule, T's write comes first, then T'' overwrites it. The final value should be T'''s value. But if we let T write now, T's value becomes current—wrong final state → abort T (or use Thomas Write Rule to skip the obsolete write).

Example:

Initial: Q = 10, W-timestamp(Q) = 50, R-timestamp(Q) = 50

T₁ with TS = 100 reads Q:
  R-timestamp(Q) = 100

T₂ with TS = 80 tries to write Q = 20:
  Check 1: TS(T₂) = 80 < R-timestamp(Q) = 100 ✗
  T₁ (TS=100) already read Q. T₂ (TS=80) "comes before" T₁.
  In serial order, T₁ should read T₂'s write, but T₁ read the old value.
  → ABORT T₂

T₃ with TS = 150 writes Q = 30:
  Check 1: TS(T₃) = 150 >= R-timestamp(Q) = 100 ✓
  Check 2: TS(T₃) = 150 >= W-timestamp(Q) = 50 ✓
  Write succeeds: Q = 30, W-timestamp(Q) = 150

T₄ with TS = 120 tries to write Q = 40:
  Check 1: TS(T₄) = 120 >= R-timestamp(Q) = 100 ✓
  Check 2: TS(T₄) = 120 < W-timestamp(Q) = 150 ✗
  T₃ already wrote with larger timestamp. T₄'s write is obsolete.
  → ABORT T₄ (or skip write with Thomas Write Rule)

Order of Checks Matters

Always check R-timestamp before W-timestamp. If both conditions fail, the R-timestamp violation is the 'real' conflict—a reader already consumed a value inconsistent with this write. The W-timestamp check is about obsolescence, which might be handled differently (Thomas Write Rule). Correct ordering ensures proper handling.

Complete Protocol Algorithm

Let's consolidate everything into a complete, implementable algorithm for the timestamp ordering protocol.

Data Structures:

// Global timestamp counter
global_timestamp = 0

// Per-transaction context
Transaction {
    id: integer
    timestamp: integer
    status: ACTIVE | COMMITTED | ABORTED
}

// Per-data-item metadata
DataItem {
    value: any
    w_timestamp: integer  // Timestamp of last writer
    r_timestamp: integer  // Largest timestamp of any reader
}

timestamp_ordering_protocol.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class TimestampOrderingProtocol:
    """
    Complete implementation of the basic Timestamp Ordering Protocol.
    Guarantees conflict-serializable schedules.
    """
    
    def __init__(self):
        self.global_ts = 0
        self.data_items = {}  # item_id -> DataItem
        self.transactions = {}  # txn_id -> Transaction
    
    def begin_transaction(self) -> int:
        """
        Start a new transaction, assign timestamp.
        Returns: transaction ID
        """
        self.global_ts += 1
        txn = Transaction(
            id=self.global_ts,
            timestamp=self.global_ts,
            status="ACTIVE"
        )
        self.transactions[txn.id] = txn
        return txn.id
    
    def read(self, txn_id: int, item_id: str) -> tuple[bool, any]:
        """
        Execute read operation under timestamp ordering.
        Returns: (success: bool, value: any or None)
        """
        txn = self.transactions[txn_id]
        item = self._get_or_create_item(item_id)
        
        # THE READ RULE
        if txn.timestamp < item.w_timestamp:
            # Violation: trying to read "future" value
            self._abort(txn)
            return (False, None)
        
        # Read allowed
        item.r_timestamp = max(item.r_timestamp, txn.timestamp)
        return (True, item.value)
    
    def write(self, txn_id: int, item_id: str, value: any) -> bool:
        """
        Execute write operation under timestamp ordering.
        Returns: success (bool)
        """
        txn = self.transactions[txn_id]
        item = self._get_or_create_item(item_id)
        
        # THE WRITE RULE - Check 1: Read timestamp
        if txn.timestamp < item.r_timestamp:
            # Violation: a later transaction already read
            self._abort(txn)
            return False
        
        # THE WRITE RULE - Check 2: Write timestamp
        if txn.timestamp < item.w_timestamp:
            # This write is obsolete - later txn already wrote
            # Option A: Abort
            self._abort(txn)
            return False
            # Option B: Thomas Write Rule - skip write, return success
            # return True  # Uncomment for Thomas Write Rule
        
        # Write allowed
        item.value = value
        item.w_timestamp = txn.timestamp
        return True
    
    def commit(self, txn_id: int) -> bool:
        """
        Commit the transaction.
        In basic TO, commit always succeeds if we reach here.
        """
        txn = self.transactions[txn_id]
        if txn.status != "ACTIVE":
            return False
        txn.status = "COMMITTED"
        return True
    
    def _abort(self, txn):
        """Mark transaction as aborted."""
        txn.status = "ABORTED"
    
    def restart_transaction(self, old_txn_id: int) -> int:
        """
        Restart an aborted transaction with new, higher timestamp.
        Application must re-execute all operations.
        """
        old_txn = self.transactions[old_txn_id]
        if old_txn.status != "ABORTED":
            raise ValueError("Can only restart aborted transactions")
        
        # Get fresh timestamp
        return self.begin_transaction()
    
    def _get_or_create_item(self, item_id: str):
        """Get item or create with default timestamps."""
        if item_id not in self.data_items:
            self.data_items[item_id] = DataItem(
                value=None,
                w_timestamp=0,
                r_timestamp=0
            )
        return self.data_items[item_id]

This Is Simplified

Production implementations add: durability (WAL logging), buffering, locking for internal concurrency, recovery logic, and performance optimizations. But the core algorithm—the read and write rules—remains exactly as shown. Understanding this foundation enables understanding the more complex production versions.

Correctness Proof Sketch

We claim the timestamp ordering protocol produces conflict-serializable schedules equivalent to the serial schedule ordered by timestamps. Let's sketch a proof.

Theorem: Any schedule S produced by the timestamp ordering protocol is conflict-equivalent to the serial schedule S' where transactions appear in timestamp order.

Proof Sketch:

We show that every pair of conflicting operations in S has the same relative order as in S'.

Case 1: Read-Write Conflict (T₁ reads, T₂ writes same item)

Subcase 1a: TS(T₁) < TS(T₂)

In S': T₁ reads before T₂ writes (correct order for serial execution)
In S: If T₂'s write completed first, W-timestamp(Q) = TS(T₂)
When T₁ reads: TS(T₁) < W-timestamp(Q), so T₁ is aborted
T₁'s read cannot appear after T₂'s write in S (would be aborted)
Therefore, T₁'s read appears before T₂'s write in S → same order as S'

Subcase 1b: TS(T₂) < TS(T₁)

In S': T₂ writes before T₁ reads
In S: If T₁ reads first (before T₂ writes), R-timestamp(Q) = TS(T₁)
When T₂ writes: TS(T₂) < R-timestamp(Q), so T₂ is aborted
T₂'s write cannot appear after T₁'s read in S → same order as S'

Case 2: Write-Read Conflict (T₁ writes, T₂ reads same item)

Symmetric to Case 1. The protocol ensures the read sees a value from a writer with smaller-or-equal timestamp, matching serial order.

Case 3: Write-Write Conflict (T₁ writes, T₂ writes same item)

Subcase 3a: TS(T₁) < TS(T₂)

In S': T₁ writes before T₂ writes; final value is T₂'s
In S: If T₁ writes last, the write rule aborts T₁ (its TS < W-timestamp)
Only T₂'s write can be the "last" write → same final value as S'

Subcase 3b: TS(T₂) < TS(T₁)

Symmetric: T₂'s later-in-time write would be aborted
T₁'s write is the final value → same as S'

Conclusion:

In every case, conflicting operations maintain the same relative order as the timestamp-ordered serial schedule. By the definition of conflict equivalence, S is conflict-serializable. ∎

The Key Insight

The protocol doesn't 'choose' an order—timestamps pre-determine the order at transaction start. The protocol merely enforces that predetermined order by rejecting operations that would violate it. This is fundamentally different from lock-based protocols, where the order emerges dynamically from lock acquisition sequences.

Detailed Execution Example

Let's trace through a complete example showing how the protocol handles multiple concurrent transactions.

Setup:

Data items: A (value=100), B (value=200)
Initial timestamps: W-TS(A)=0, R-TS(A)=0, W-TS(B)=0, R-TS(B)=0

Transactions:

T₁ (TS=10): Read A, Write B = A + 50
T₂ (TS=20): Read B, Write A = B - 30
T₃ (TS=15): Read A, Read B, Write A = A + B

Execution Trace with Timestamp Ordering
Step	Operation	Check	Result	State After
1	T₁ reads A	TS(T₁)=10 ≥ W-TS(A)=0	✓ Success, returns 100	R-TS(A)=10
2	T₂ reads B	TS(T₂)=20 ≥ W-TS(B)=0	✓ Success, returns 200	R-TS(B)=20
3	T₃ reads A	TS(T₃)=15 ≥ W-TS(A)=0	✓ Success, returns 100	R-TS(A)=max(10,15)=15
4	T₁ writes B=150	TS(T₁)=10 ≥ R-TS(B)=20?	✗ FAIL: 10 < 20	T₁ ABORTED
5	T₃ reads B	TS(T₃)=15 ≥ W-TS(B)=0	✓ Success, returns 200	R-TS(B)=max(20,15)=20
6	T₃ writes A=300	TS(T₃)=15 ≥ R-TS(A)=15?	✓ (equal), W-TS(A)=0 ✓	A=300, W-TS(A)=15
7	T₂ writes A=170	TS(T₂)=20 ≥ R-TS(A)=15?	✓, W-TS(A)=15 < 20 ✓	A=170, W-TS(A)=20
8	T₃ commits		✓ Success	T₃ committed
9	T₂ commits		✓ Success	T₂ committed

Analysis:

Step 4: T₁ tried to write B, but T₂ (with larger timestamp 20) already read B. In the serial order T₁ → T₂, T₂ should have read T₁'s value. But T₂ read the old value (200). Conflict detected → T₁ aborted.

Step 6: T₃ writes A. Its read of A earlier (step 3) updated R-TS(A) to 15. Now TS(T₃)=15 equals R-TS(A)=15, which satisfies the ≥ condition. This is allowed—T₃ is the highest reader so far, and it's now writing.

Step 7: T₂ writes A. Even though T₃ just wrote (W-TS=15), T₂ has larger timestamp (20), so its write is valid and overwrites T₃'s value.

Final Result:

A = 170 (written by T₂)
B = 200 (unchanged; T₁ was aborted before writing)

Equivalent Serial Schedule: T₃ → T₂ (T₁ never completed)

If we had executed T₃ then T₂ serially:

T₃: A = 100 + 200 = 300
T₂: A = 200 - 30 = 170 (overwrites T₃)
Final A = 170 ✓

T₁ Must Restart

After abort, T₁ gets a new timestamp (e.g., 25) and restarts from the beginning. With TS=25, its operations would now succeed (assuming no new conflicts). The restart ensures T₁ eventually completes, though possibly much later in the serialization order.

Edge Cases and Special Scenarios

Real-world execution encounters various edge cases. Understanding how the protocol handles them is essential for correct implementation.

Edge Case 1: Transaction Reads Its Own Writes

T₁ (TS=100):
  Write A = 50
  Read A      // Should return 50, not abort!

After T₁ writes A, W-TS(A) = 100. When T₁ reads, TS(T₁) = 100 = W-TS(A). The check TS(T₁) ≥ W-TS(A) passes. T₁ reads its own write. ✓

Edge Case 2: Transaction Writes Same Item Twice

T₁ (TS=100):
  Write A = 50
  Write A = 75    // Second write

After first write: W-TS(A) = 100. Second write check: TS(T₁) = 100 ≥ W-TS(A) = 100. Passes. The second write overwrites with 75. Both are T₁'s writes, so order within transaction is preserved. ✓

Edge Case 3: Read After Another Transaction's Read

T₁ (TS=100) reads A      // R-TS(A) = 100
T₂ (TS=150) reads A      // R-TS(A) = 150
T₃ (TS=80) reads A       // TS=80 ≥ W-TS(A)=0, succeeds
                         // R-TS(A) = max(150, 80) = 150

Reads don't conflict with each other—only with writes. Multiple concurrent reads always succeed (if they satisfy the read rule against W-TS). R-TS tracks the maximum reader, not all readers.

Edge Case 4: Timestamp Ties (Shouldn't Happen)

T₁ (TS=100) and T₂ (TS=100)  // Same timestamp - BUG!

Timestamp assignment must guarantee uniqueness. If two transactions have the same timestamp, the protocol cannot determine their relative order. This is a system invariant violation—prevent it through proper timestamp generation. If somehow encountered, one approach is to compare transaction IDs as a tiebreaker.

Edge Case 5: All Writes, No Reads

If transactions only write (never read), R-timestamp never increases. Write-write conflicts are still detected via W-timestamp comparison. The protocol degrades to last-writer-wins based on timestamp order.

Cascading Aborts Are Possible

Basic timestamp ordering doesn't prevent cascading aborts. If T₁ writes A, T₂ reads A (sees T₁'s value), and then T₁ aborts (due to conflict with another item), T₂ has read 'dirty' data and may also need to abort. Strict timestamp ordering variants address this by not allowing reads of uncommitted data.

Summary: Ordering Transactions

We've completed our deep dive into how timestamps create and enforce transaction ordering. Let's consolidate the essential insights:

Key Takeaways

•Timestamps define the target serial schedule — The serial execution ordered by timestamps is what the protocol aims to emulate.
•The Read Rule prevents reading 'future' values — If W-TS(Q) > TS(T), T would see a value written by a logically-later transaction—abort and restart.
•The Write Rule has two checks — First, ensure no later transaction has read (would invalidate their read). Second, ensure no later transaction has written (this write is obsolete).
•The protocol guarantees conflict-serializability — Conflicting operations maintain the same order as the timestamp-ordered serial schedule.
•Aborts are the enforcement mechanism — Violations are detected eagerly, and offending transactions restart with fresh timestamps.
•Edge cases resolve consistently — Self-reads, self-writes, concurrent reads, and other scenarios all follow from the basic rules.

Module Complete:

You've now mastered the foundations of timestamp ordering—from the concept of timestamps through generation methods, assignment policies, and the complete ordering protocol. This knowledge forms the basis for understanding more advanced topics like the Thomas Write Rule (an optimization), Strict Timestamp Ordering (for recoverability), and MVCC (which extends timestamp ideas to support multiple versions).

Page Complete

You now fully understand how timestamp ordering works—from the theoretical foundation of timestamps defining serial equivalence, through the precise read and write rules, to practical implementation and edge case handling. You can analyze concurrent executions, predict outcomes, and implement timestamp ordering protocols. This completes Module 1: Timestamp Ordering.

Ordering Transactions

From Timestamps to Serial Order

What You Will Learn

Timestamps Define Serial Order

The fundamental insight of timestamp ordering is that the timestamp assignment at transaction start defines the serial schedule we want to emulate.

The Target Serial Schedule:

If we have transactions T₁, T₂, T₃ with timestamps 100, 200, 300 respectively, then the "target" serial schedule is:

Serial Schedule S: T₁ → T₂ → T₃
(Execute T₁ completely, then T₂ completely, then T₃ completely)

Serialization Equivalence:

Two schedules are equivalent if:

They involve the same transactions and operations
They produce the same final database state
Each transaction reads the same values in both schedules

Timestamp ordering ensures: the actual schedule is equivalent to the serial schedule ordered by timestamps.

Why Timestamp Order Works:

Consider what "T₁ happens before T₂" means in a serial execution:

T₂ reads data items as written by T₁ (if T₁ wrote them)
T₂'s writes overwrite T₁'s writes on the same items
T₁ cannot see any of T₂'s changes (it "happened before")

The timestamp protocol enforces exactly these properties:

If TS(T₁) < TS(T₂):
- T₂ must see T₁'s writes (or later writes, never earlier)
- T₂'s writes must not violate T₁'s reads
- T₁ cannot read values "from the future" written by T₂

By rejecting any operation that violates these rules, the protocol guarantees equivalence to timestamp-ordered serial execution.

Think of Timestamps as 'Serialization Points'

The Read Rule

When transaction T with timestamp TS(T) wants to read data item Q, the protocol must determine whether this read is consistent with the intended serial order.

The Read Rule:

READ(T, Q):
    If TS(T) < W-timestamp(Q):
        // A transaction with larger timestamp has already written Q
        // In serial order, that write happens AFTER T
        // But T would be reading that "future" value -> VIOLATION
        ABORT T and restart with new timestamp
    Else:
        // TS(T) >= W-timestamp(Q)
        // T's read is consistent with serial order
        Execute the read
        R-timestamp(Q) = max(R-timestamp(Q), TS(T))

Why This Works:

If TS(T) < W-timestamp(Q):

Some transaction T' with TS(T') = W-timestamp(Q) > TS(T) has written Q
In the target serial schedule, T comes before T'
Therefore, T should read the value of Q from before T' wrote
But T' has already written, and we only keep current values
T cannot see the "old" value → abort and restart

Example:

Initial: Q = 10, W-timestamp(Q) = 50, R-timestamp(Q) = 50

T₁ with TS = 100 reads Q:
  Check: TS(T₁) = 100 >= W-timestamp(Q) = 50 ✓
  Read succeeds, returns Q = 10
  R-timestamp(Q) = max(50, 100) = 100

T₂ with TS = 200 writes Q = 20:
  (Assuming write succeeds)
  W-timestamp(Q) = 200, R-timestamp(Q) = 200

T₃ with TS = 150 tries to read Q:
  Check: TS(T₃) = 150 < W-timestamp(Q) = 200 ✗
  T₃ would be reading T₂'s value, but T₃ "happens before" T₂
  → ABORT T₃, restart with new timestamp (e.g., 250)

After restart, T₃ has timestamp 250. Now:

T₃' with TS = 250 reads Q:
  Check: TS(T₃') = 250 >= W-timestamp(Q) = 200 ✓
  Read succeeds, returns Q = 20
  R-timestamp(Q) = max(200, 250) = 250

Reading 'Stale' Values Is Fine

The Write Rule

When transaction T with timestamp TS(T) wants to write data item Q, the protocol checks two conditions to ensure serial order consistency.

The Write Rule:

WRITE(T, Q, value):
    If TS(T) < R-timestamp(Q):
        // A transaction with larger timestamp has already read Q
        // That transaction saw the "old" value
        // T's write would change the value they should have seen -> VIOLATION
        ABORT T and restart with new timestamp
    
    Else If TS(T) < W-timestamp(Q):
        // A transaction with larger timestamp has already written Q
        // T's write is "obsolete" - its effects are overwritten anyway
        // Two options: abort, or use Thomas Write Rule (ignore)
        ABORT T and restart with new timestamp
        // OR with Thomas Write Rule: simply ignore this write (don't abort)
    
    Else:
        // TS(T) >= R-timestamp(Q) AND TS(T) >= W-timestamp(Q)
        // Write is consistent with serial order
        Execute the write: Q = value
        W-timestamp(Q) = TS(T)

Why Two Checks Are Needed:

Check 1: TS(T) < R-timestamp(Q)

Check 2: TS(T) < W-timestamp(Q)

Example:

Initial: Q = 10, W-timestamp(Q) = 50, R-timestamp(Q) = 50

T₁ with TS = 100 reads Q:
  R-timestamp(Q) = 100

T₂ with TS = 80 tries to write Q = 20:
  Check 1: TS(T₂) = 80 < R-timestamp(Q) = 100 ✗
  T₁ (TS=100) already read Q. T₂ (TS=80) "comes before" T₁.
  In serial order, T₁ should read T₂'s write, but T₁ read the old value.
  → ABORT T₂

T₃ with TS = 150 writes Q = 30:
  Check 1: TS(T₃) = 150 >= R-timestamp(Q) = 100 ✓
  Check 2: TS(T₃) = 150 >= W-timestamp(Q) = 50 ✓
  Write succeeds: Q = 30, W-timestamp(Q) = 150

T₄ with TS = 120 tries to write Q = 40:
  Check 1: TS(T₄) = 120 >= R-timestamp(Q) = 100 ✓
  Check 2: TS(T₄) = 120 < W-timestamp(Q) = 150 ✗
  T₃ already wrote with larger timestamp. T₄'s write is obsolete.
  → ABORT T₄ (or skip write with Thomas Write Rule)

Order of Checks Matters

Complete Protocol Algorithm

Let's consolidate everything into a complete, implementable algorithm for the timestamp ordering protocol.

Data Structures:

// Global timestamp counter
global_timestamp = 0

// Per-transaction context
Transaction {
    id: integer
    timestamp: integer
    status: ACTIVE | COMMITTED | ABORTED
}

// Per-data-item metadata
DataItem {
    value: any
    w_timestamp: integer  // Timestamp of last writer
    r_timestamp: integer  // Largest timestamp of any reader
}

timestamp_ordering_protocol.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class TimestampOrderingProtocol:
    """
    Complete implementation of the basic Timestamp Ordering Protocol.
    Guarantees conflict-serializable schedules.
    """
    
    def __init__(self):
        self.global_ts = 0
        self.data_items = {}  # item_id -> DataItem
        self.transactions = {}  # txn_id -> Transaction
    
    def begin_transaction(self) -> int:
        """
        Start a new transaction, assign timestamp.
        Returns: transaction ID
        """
        self.global_ts += 1
        txn = Transaction(
            id=self.global_ts,
            timestamp=self.global_ts,
            status="ACTIVE"
        )
        self.transactions[txn.id] = txn
        return txn.id
    
    def read(self, txn_id: int, item_id: str) -> tuple[bool, any]:
        """
        Execute read operation under timestamp ordering.
        Returns: (success: bool, value: any or None)
        """
        txn = self.transactions[txn_id]
        item = self._get_or_create_item(item_id)
        
        # THE READ RULE
        if txn.timestamp < item.w_timestamp:
            # Violation: trying to read "future" value
            self._abort(txn)
            return (False, None)
        
        # Read allowed
        item.r_timestamp = max(item.r_timestamp, txn.timestamp)
        return (True, item.value)
    
    def write(self, txn_id: int, item_id: str, value: any) -> bool:
        """
        Execute write operation under timestamp ordering.
        Returns: success (bool)
        """
        txn = self.transactions[txn_id]
        item = self._get_or_create_item(item_id)
        
        # THE WRITE RULE - Check 1: Read timestamp
        if txn.timestamp < item.r_timestamp:
            # Violation: a later transaction already read
            self._abort(txn)
            return False
        
        # THE WRITE RULE - Check 2: Write timestamp
        if txn.timestamp < item.w_timestamp:
            # This write is obsolete - later txn already wrote
            # Option A: Abort
            self._abort(txn)
            return False
            # Option B: Thomas Write Rule - skip write, return success
            # return True  # Uncomment for Thomas Write Rule
        
        # Write allowed
        item.value = value
        item.w_timestamp = txn.timestamp
        return True
    
    def commit(self, txn_id: int) -> bool:
        """
        Commit the transaction.
        In basic TO, commit always succeeds if we reach here.
        """
        txn = self.transactions[txn_id]
        if txn.status != "ACTIVE":
            return False
        txn.status = "COMMITTED"
        return True
    
    def _abort(self, txn):
        """Mark transaction as aborted."""
        txn.status = "ABORTED"
    
    def restart_transaction(self, old_txn_id: int) -> int:
        """
        Restart an aborted transaction with new, higher timestamp.
        Application must re-execute all operations.
        """
        old_txn = self.transactions[old_txn_id]
        if old_txn.status != "ABORTED":
            raise ValueError("Can only restart aborted transactions")
        
        # Get fresh timestamp
        return self.begin_transaction()
    
    def _get_or_create_item(self, item_id: str):
        """Get item or create with default timestamps."""
        if item_id not in self.data_items:
            self.data_items[item_id] = DataItem(
                value=None,
                w_timestamp=0,
                r_timestamp=0
            )
        return self.data_items[item_id]

This Is Simplified

Correctness Proof Sketch

We claim the timestamp ordering protocol produces conflict-serializable schedules equivalent to the serial schedule ordered by timestamps. Let's sketch a proof.

Theorem: Any schedule S produced by the timestamp ordering protocol is conflict-equivalent to the serial schedule S' where transactions appear in timestamp order.

Proof Sketch:

We show that every pair of conflicting operations in S has the same relative order as in S'.

Case 1: Read-Write Conflict (T₁ reads, T₂ writes same item)

Subcase 1a: TS(T₁) < TS(T₂)

In S': T₁ reads before T₂ writes (correct order for serial execution)
In S: If T₂'s write completed first, W-timestamp(Q) = TS(T₂)
When T₁ reads: TS(T₁) < W-timestamp(Q), so T₁ is aborted
T₁'s read cannot appear after T₂'s write in S (would be aborted)
Therefore, T₁'s read appears before T₂'s write in S → same order as S'

Subcase 1b: TS(T₂) < TS(T₁)

In S': T₂ writes before T₁ reads
In S: If T₁ reads first (before T₂ writes), R-timestamp(Q) = TS(T₁)
When T₂ writes: TS(T₂) < R-timestamp(Q), so T₂ is aborted
T₂'s write cannot appear after T₁'s read in S → same order as S'

Case 2: Write-Read Conflict (T₁ writes, T₂ reads same item)

Symmetric to Case 1. The protocol ensures the read sees a value from a writer with smaller-or-equal timestamp, matching serial order.

Case 3: Write-Write Conflict (T₁ writes, T₂ writes same item)

Subcase 3a: TS(T₁) < TS(T₂)

In S': T₁ writes before T₂ writes; final value is T₂'s
In S: If T₁ writes last, the write rule aborts T₁ (its TS < W-timestamp)
Only T₂'s write can be the "last" write → same final value as S'

Subcase 3b: TS(T₂) < TS(T₁)

Symmetric: T₂'s later-in-time write would be aborted
T₁'s write is the final value → same as S'

Conclusion:

In every case, conflicting operations maintain the same relative order as the timestamp-ordered serial schedule. By the definition of conflict equivalence, S is conflict-serializable. ∎

The Key Insight

Detailed Execution Example

Let's trace through a complete example showing how the protocol handles multiple concurrent transactions.

Setup:

Data items: A (value=100), B (value=200)
Initial timestamps: W-TS(A)=0, R-TS(A)=0, W-TS(B)=0, R-TS(B)=0

Transactions:

T₁ (TS=10): Read A, Write B = A + 50
T₂ (TS=20): Read B, Write A = B - 30
T₃ (TS=15): Read A, Read B, Write A = A + B

Execution Trace with Timestamp Ordering
Step	Operation	Check	Result	State After
1	T₁ reads A	TS(T₁)=10 ≥ W-TS(A)=0	✓ Success, returns 100	R-TS(A)=10
2	T₂ reads B	TS(T₂)=20 ≥ W-TS(B)=0	✓ Success, returns 200	R-TS(B)=20
3	T₃ reads A	TS(T₃)=15 ≥ W-TS(A)=0	✓ Success, returns 100	R-TS(A)=max(10,15)=15
4	T₁ writes B=150	TS(T₁)=10 ≥ R-TS(B)=20?	✗ FAIL: 10 < 20	T₁ ABORTED
5	T₃ reads B	TS(T₃)=15 ≥ W-TS(B)=0	✓ Success, returns 200	R-TS(B)=max(20,15)=20
6	T₃ writes A=300	TS(T₃)=15 ≥ R-TS(A)=15?	✓ (equal), W-TS(A)=0 ✓	A=300, W-TS(A)=15
7	T₂ writes A=170	TS(T₂)=20 ≥ R-TS(A)=15?	✓, W-TS(A)=15 < 20 ✓	A=170, W-TS(A)=20
8	T₃ commits		✓ Success	T₃ committed
9	T₂ commits		✓ Success	T₂ committed

Analysis:

Step 7: T₂ writes A. Even though T₃ just wrote (W-TS=15), T₂ has larger timestamp (20), so its write is valid and overwrites T₃'s value.

Final Result:

A = 170 (written by T₂)
B = 200 (unchanged; T₁ was aborted before writing)

Equivalent Serial Schedule: T₃ → T₂ (T₁ never completed)

If we had executed T₃ then T₂ serially:

T₃: A = 100 + 200 = 300
T₂: A = 200 - 30 = 170 (overwrites T₃)
Final A = 170 ✓

T₁ Must Restart

Edge Cases and Special Scenarios

Real-world execution encounters various edge cases. Understanding how the protocol handles them is essential for correct implementation.

Edge Case 1: Transaction Reads Its Own Writes

T₁ (TS=100):
  Write A = 50
  Read A      // Should return 50, not abort!

After T₁ writes A, W-TS(A) = 100. When T₁ reads, TS(T₁) = 100 = W-TS(A). The check TS(T₁) ≥ W-TS(A) passes. T₁ reads its own write. ✓

Edge Case 2: Transaction Writes Same Item Twice

T₁ (TS=100):
  Write A = 50
  Write A = 75    // Second write

Edge Case 3: Read After Another Transaction's Read

T₁ (TS=100) reads A      // R-TS(A) = 100
T₂ (TS=150) reads A      // R-TS(A) = 150
T₃ (TS=80) reads A       // TS=80 ≥ W-TS(A)=0, succeeds
                         // R-TS(A) = max(150, 80) = 150

Reads don't conflict with each other—only with writes. Multiple concurrent reads always succeed (if they satisfy the read rule against W-TS). R-TS tracks the maximum reader, not all readers.

Edge Case 4: Timestamp Ties (Shouldn't Happen)

T₁ (TS=100) and T₂ (TS=100)  // Same timestamp - BUG!

Edge Case 5: All Writes, No Reads

Cascading Aborts Are Possible

Summary: Ordering Transactions

We've completed our deep dive into how timestamps create and enforce transaction ordering. Let's consolidate the essential insights:

Key Takeaways

•Timestamps define the target serial schedule — The serial execution ordered by timestamps is what the protocol aims to emulate.
•The Read Rule prevents reading 'future' values — If W-TS(Q) > TS(T), T would see a value written by a logically-later transaction—abort and restart.
•The Write Rule has two checks — First, ensure no later transaction has read (would invalidate their read). Second, ensure no later transaction has written (this write is obsolete).
•The protocol guarantees conflict-serializability — Conflicting operations maintain the same order as the timestamp-ordered serial schedule.
•Aborts are the enforcement mechanism — Violations are detected eagerly, and offending transactions restart with fresh timestamps.
•Edge cases resolve consistently — Self-reads, self-writes, concurrent reads, and other scenarios all follow from the basic rules.

Module Complete:

Page Complete