Write Rules

Write operations in timestamp ordering face a more complex challenge than reads. While reads only conflict with "future" writes (detected via WTS), writes can conflict with both younger reads and younger writes. This dual conflict potential means write operations must pass two checks before proceeding.

The Write Rules of the Basic Timestamp Protocol embody a fundamental principle: a transaction should only write values that could have existed at its logical position in the serialization order. If a younger transaction has already read the data item, the read saw the "pre-write" value, and writing now would invalidate that read. If a younger transaction has already written the data item, overwriting would replace a "newer" value with an "older" one.

Before formalizing the write rules, let's understand why writes are more constrained than reads. A write by transaction T can create two types of temporal violations:

Conflict Type 1: Write-After-Read (W-A-R)

If a younger transaction T' has already read X, T' saw the pre-write value. If T now writes X, T' has seen a value that, in the equivalent serial schedule (where T executes before T'), would have been overwritten by T before T' read it. T' has read a "stale" value that shouldn't exist.

Detection: If TS(T) < RTS(X), a younger transaction has read X. T's write would violate serializability.

Conflict Type 2: Write-After-Write (W-A-W)

If a younger transaction T' has already written X, allowing T to now write X would replace T''s value with T's older value. In the equivalent serial schedule, T' would execute after T, so T''s value should be the final value. Overwriting it with T's value violates this order.

Detection: If TS(T) < WTS(X), a younger transaction has written X. T's write would overwrite a "newer" value with an "older" one.

Why Reads Only Have One Check:

In contrast, reads can only conflict in one way:

• Read-After-Write: T reading a value written by younger T' (TS(T) < WTS(X))

There's no "Read-After-Read" conflict because multiple transactions can read the same value without affecting serializability. Reads don't change data, so they don't invalidate each other.

We now present the complete, formal write rules for the Basic Timestamp Protocol. When transaction T requests to write value v to data item X:

Algorithm: Write(X, v) by Transaction T

1. IF TS(T) < RTS(X) THEN
       // A younger transaction has read X
       // T's write would invalidate that read
       Abort T and restart with new, larger timestamp
       RETURN FAILURE
   END IF

2. IF TS(T) < WTS(X) THEN
       // A younger transaction has written X
       // T would be overwriting a newer value (Basic: abort)
       Abort T and restart with new, larger timestamp
       RETURN FAILURE
   END IF

3. // Both checks passed - write is allowed
   X := v                // Set new value
   WTS(X) := TS(T)       // Update write timestamp
   RTS(X) := TS(T)       // Reset read timestamp
   
4. RETURN SUCCESS

Why Reset RTS?

When T writes X, the old value and its read history become irrelevant. The new value has never been read by any transaction except (logically) its creator. Setting RTS(X) := TS(T) reflects this:

• Previous reads were of the old value
• The new value's read history starts fresh
• Only transactions younger than T might read this new value
• Setting RTS = TS(T) is a conservative starting point

The Basic Timestamp Protocol aborts T when TS(T) < WTS(X)—when T tries to overwrite a newer value. But consider: does this write actually affect correctness?

If T's write would be immediately overwritten by the younger transaction's value anyway (in the equivalent serial schedule), T's write is obsolete. It produces a value no one will ever see. The Thomas Write Rule exploits this observation.

Modified Write Rules (with Thomas Write Rule):

1. IF TS(T) < RTS(X) THEN
       // Still must abort: a read has been invalidated
       Abort T and restart
       RETURN FAILURE
   END IF

2. IF TS(T) < WTS(X) THEN
       // Thomas Write Rule: ignore obsolete write
       // The write is skipped, but T continues
       RETURN SUCCESS (no abort, no write)
   END IF

3. // Both checks passed - write proceeds normally
   X := v
   WTS(X) := TS(T)
   RTS(X) := TS(T)
   
4. RETURN SUCCESS

The only change is in Step 2: instead of aborting, we simply skip the write and return success. T continues executing as if the write happened, but no state change occurs.

Correctness Argument:

The Thomas Write Rule maintains serializability because:

1. T's write would produce an obsolete value (overwritten by T' in serial order)
2. No transaction ever reads T's value (T' already wrote a newer value)
3. The effect is as if T's write executed and was immediately overwritten
4. Skipping the write is semantically equivalent to this sequence

Limitations:

The Thomas Write Rule only applies when TS(T) < WTS(X) but TS(T) ≥ RTS(X). If TS(T) < RTS(X), a read conflict exists and abort is mandatory—ignoring the write doesn't help because the problem is with the read, not the write.

Let's trace the write rules through several scenarios.

Example 1: Successful Write

Example 2: RTS Conflict (Abort)

T cannot write X because a transaction with timestamp 30 has already read X. T's write would invalidate that read.

Example 3: WTS Conflict (Basic Protocol: Abort)

Note: In this case, T actually fails the RTS check first (25 < 40). Since a transaction with TS=40 wrote X, it also "read" it (WTS write resets RTS). Both checks would fail.

Example 4: WTS Conflict (Thomas Write Rule: Ignore)

Real workloads involve sequences of reads and writes across multiple data items. Let's trace a complex scenario.

Scenario: Two Transactions, Two Data Items

Transactions:

• T1 (TS=10): Read X, Write Y
• T2 (TS=20): Write X, Read Y

Initial state: WTS(X)=0, RTS(X)=0, WTS(Y)=0, RTS(Y)=0

Analysis:

T1 starts successfully (t1), but by t4, when T1 tries to write Y, T2 has already read Y. Since T1's timestamp (10) is less than RTS(Y) = 20, T1 must abort.

This demonstrates a critical property: late failures are possible. A transaction may execute many operations successfully before encountering a conflict with a younger transaction. All prior work must be undone.

After T1 Aborts and Restarts as T3 (TS=25):

The write rules, combined with read rules, enforce a strict isolation guarantee: conflict serializability. Let's understand how.

Conflict Serializability via Timestamp Order:

Two operations conflict if they:

1. Are from different transactions
2. Access the same data item
3. At least one is a write

Conflict serializability requires that conflicting operations occur in a consistent order across all data items. Timestamp ordering achieves this by:

• Read-Write conflicts: Read before write (by different transactions) is allowed iff reader's TS < writer's TS. Enforced by RTS check on write.
• Write-Read conflicts: Write before read (by different transactions) is allowed iff writer's TS < reader's TS. Enforced by WTS check on read.
• Write-Write conflicts: First write before second write requires first writer's TS < second writer's TS. Enforced by WTS check on write.

The Serialization Order:

The resulting schedule is equivalent to executing all committed transactions in timestamp order. If T commits with TS=10 and T' commits with TS=20, the schedule is equivalent to:

T completes all operations, then T' begins.

This is true across all data items, regardless of actual execution interleaving.

Write rules have significant performance implications that affect system design decisions.

The Hot Item Problem:

Consider a popular data item like a global counter:

1. Many transactions read it, driving RTS to very high values
2. Any write attempt must satisfy TS(T) ≥ RTS
3. Only the very newest transactions can successfully write
4. Older transactions abort repeatedly

This creates a starvation-like effect where certain writes become nearly impossible. Workload patterns matter significantly:

• Read-heavy workloads: Generally perform well (RTS updates are the main overhead)
• Write-heavy workloads: Can suffer high abort rates
• Mixed with hot spots: Worst case—hot items cause cascading aborts