Loading learning content...
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.
By the end of this page, you will understand the formal write rules of the Basic Timestamp Protocol, including the dual checks against RTS and WTS. You'll be able to determine whether any write operation should succeed or fail, understand the Thomas Write Rule optimization, and see how writes and reads combine to form the complete protocol.
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.
T(TS=10) wants to write X. But T'(TS=20) has already read X (RTS(X) = 20). In any valid serial schedule where T comes before T', T would write first, then T' would read T's value. But T' has already read the old value. Contradiction! T must abort.
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.
| Conflict Type | Condition | Meaning | Violation |
|---|---|---|---|
| Write-After-Read | TS(T) < RTS(X) | Younger transaction read X | That read saw wrong value |
| Write-After-Write | TS(T) < WTS(X) | Younger transaction wrote X | Replacing newer with older value |
Why Reads Only Have One Check:
In contrast, reads can only conflict in one way:
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
The order of RTS and WTS checks doesn't affect correctness—if either fails, T aborts. However, implementations may order them based on which is more likely to fail in their workload, for minor efficiency gains.
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:
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.
If TS(T) < WTS(X), T's write would be overwritten by the younger transaction that already wrote X. In the equivalent serial schedule, T writes first, then T' writes, leaving T''s value. Since T's value is never observed, we can simply ignore T's write rather than aborting T!
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.
| Step | Transaction | Operation | WTS(X) | Action | Result |
|---|---|---|---|---|---|
| 1 | T40 | Write(X, 'new') | 0→40 | WTS updated | Success |
| 2 | T20 | Write(X, 'old') | 40 | 20 < 40, skip write | Success (ignored) |
| 3 | — | Final value | 40 | Value = 'new' | 'old' never visible |
Correctness Argument:
The Thomas Write Rule maintains serializability because:
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
| State | Check | Result |
|---|---|---|
| Initial: WTS(X)=10, RTS(X)=15 | — | — |
| T(TS=25) wants Write(X) | — | — |
| Check 1: 25 ≥ RTS(15)? | 25 ≥ 15 | ✓ Pass |
| Check 2: 25 ≥ WTS(10)? | 25 ≥ 10 | ✓ Pass |
| Execute write | X = new value | WTS(X)=25, RTS(X)=25 |
Example 2: RTS Conflict (Abort)
| State | Check | Result |
|---|---|---|
| Initial: WTS(X)=10, RTS(X)=30 | — | — |
| T(TS=20) wants Write(X) | — | — |
| Check 1: 20 ≥ RTS(30)? | 20 ≥ 30 | ✗ FAIL |
| Result | — | ABORT T |
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)
| State | Check | Result |
|---|---|---|
| Initial: WTS(X)=40, RTS(X)=40 | — | — |
| T(TS=25) wants Write(X) | — | — |
| Check 1: 25 ≥ RTS(40)? | 25 ≥ 40 | ✗ FAIL |
| Result | — | ABORT T |
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)
| State | Check | Result |
|---|---|---|
| Initial: WTS(X)=40, RTS(X)=20 | — | RTS set by earlier read |
| T(TS=25) wants Write(X) | — | — |
| Check 1: 25 ≥ RTS(20)? | 25 ≥ 20 | ✓ Pass |
| Check 2: 25 ≥ WTS(40)? | 25 ≥ 40 | ✗ Fail → Thomas Rule |
| Result | — | Ignore write, T continues |
The Thomas Write Rule only applies when RTS(X) < WTS(X)—meaning the most recent write was to a value that wasn't subsequently read by a younger transaction. This scenario arises when writes are frequent but reads are from older transactions.
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:
Initial state: WTS(X)=0, RTS(X)=0, WTS(Y)=0, RTS(Y)=0
| Time | Operation | Check | X State | Y State | Result |
|---|---|---|---|---|---|
| t1 | T1: Read(X) | 10 ≥ WTS(0)? | RTS=10 | — | Success |
| t2 | T2: Write(X) | 20 ≥ RTS(10)? 20 ≥ WTS(0)? | WTS=20, RTS=20 | — | Success |
| t3 | T2: Read(Y) | 20 ≥ WTS(0)? | — | RTS=20 | Success |
| t4 | T1: Write(Y) | 10 ≥ RTS(20)? | — | — | FAIL: 10 < 20 |
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):
| Time | Operation | Check | X State | Y State | Result |
|---|---|---|---|---|---|
| t5 | T3: Read(X) | 25 ≥ WTS(20)? | RTS=25 | — | Success |
| t6 | T3: Write(Y) | 25 ≥ RTS(20)? 25 ≥ WTS(0)? | — | WTS=25, RTS=25 | Success |
When T1 aborted, its read of X (which set RTS(X)=10) remained. T2's write at t2 proceeded because 20 > 10. But now T3 reads X and sees T2's value, not the original value T1 saw. The serialization order is effectively T2 → T3, even though T3 is the 'reincarnation' of T1.
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:
Conflict serializability requires that conflicting operations occur in a consistent order across all data items. Timestamp ordering achieves this by:
| Conflict Type | Required Order | Enforced By | Violation Action |
|---|---|---|---|
| R-W (same item) | Reader TS < Writer TS | Write's RTS check | Abort writer |
| W-R (same item) | Writer TS < Reader TS | Read's WTS check | Abort reader |
| W-W (same item) | Earlier TS < Later TS | Write's WTS check | Abort/ignore older |
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.
Basic timestamp ordering doesn't prevent reading uncommitted data. If T writes X and then T' reads X (with TS(T') > TS(T)), the read succeeds even if T hasn't committed. If T then aborts, T' has read dirty data. This is a recoverability issue addressed by Strict Timestamp Ordering.
Write rules have significant performance implications that affect system design decisions.
The Hot Item Problem:
Consider a popular data item like a global counter:
This creates a starvation-like effect where certain writes become nearly impossible. Workload patterns matter significantly:
We've now formalized the complete write rules of the Basic Timestamp Protocol. Let's consolidate the key concepts:
What's Next:
With both read and write rules understood, the final page brings everything together: Protocol Execution. We'll trace complete transaction schedules through the protocol, see how serializability is achieved, discuss the implications for recovery, and compare the protocol's behavior to locking approaches.
You now understand the formal write rules of the Basic Timestamp Protocol, including both checks and the Thomas Write Rule optimization. Combined with the read rules, you have a complete picture of how timestamp ordering handles individual operations. Next, we'll see how these rules combine to execute entire transactions.