Write Timestamp (WTS)

In the previous page, we explored Read Timestamps (RTS)—metadata that tracks which transactions have read a data item. RTS detects write-after-read conflicts. But what about the complementary scenario: a transaction trying to read a value that was written by a transaction that should come after it in the serial order?

This is a read-after-write conflict, and detecting it requires knowing when data was last written. Enter the Write Timestamp (WTS)—the second half of our timestamp-based conflict detection mechanism. Together with RTS, WTS completes the picture that allows the Basic Timestamp Protocol to guarantee serializability.

Every data item in a timestamp-based system maintains a Write Timestamp (WTS), denoted WTS(X), which stores the timestamp of the transaction that wrote the current value of X.

Unlike RTS, which tracks the maximum timestamp across all readers, WTS records the timestamp of a single transaction—specifically, the one that produced the current value. When a new transaction writes X, the WTS is updated to that transaction's timestamp, effectively "tagging" the value with its creator's identity.

Formal Definition:

For any data item X in the database:

WTS(X) = TS(Ti) where Ti is the transaction that last wrote the current value of X.

This is simpler than RTS because there's always exactly one writer of the current value. When transaction T writes X:

• WTS(X) is set to TS(T)
• The previous value (and its WTS) is replaced
• RTS(X) is typically reset to TS(T) as well (since readers of the old value are now irrelevant)

The write timestamp establishes the "birth time" of the current value. Any transaction trying to read this value must have a timestamp at least as large as WTS(X) to maintain serialization order.

Write timestamps serve two critical purposes in the Basic Timestamp Protocol:

Purpose 1: Detecting Read-After-Write Conflicts

Consider this scenario:

1. Transaction T2 (timestamp 20) writes data item X
2. Later, transaction T1 (timestamp 10) tries to read X

In a serial schedule respecting timestamp order, T1 would execute completely before T2 starts. T1 would read the value of X that existed before T2's write. But in our actual execution, T2 has already written X—T1 would be reading T2's value, which shouldn't exist yet from T1's perspective.

Purpose 2: Detecting Write-After-Write Conflicts

WTS also detects when an older transaction tries to overwrite a value written by a younger transaction:

1. Transaction T2 (timestamp 20) writes data item X
2. Later, transaction T1 (timestamp 10) tries to write X

If we allowed T1's write, we'd be replacing T2's value with T1's—but T2 is supposed to come after T1 in any equivalent serial schedule. The final value should be T2's, not T1's.

The WTS check for writes:

If TS(T) < WTS(X), then T is trying to overwrite a value written by a younger transaction.

This scenario has two possible resolutions:

• Basic protocol: Abort T and restart with a new timestamp
• Thomas Write Rule: Ignore T's write (since it's obsolete anyway)—covered in a later module

Understanding the precise mechanics of WTS updates is essential for implementing and reasoning about timestamp protocols. Unlike RTS which accumulates information across reads, WTS is simply replaced on each write.

The WTS Update Rule:

When transaction T successfully writes data item X with value v:

X := v
WTS(X) := TS(T)
RTS(X) := TS(T)  // Reset read timestamp

The write operation completely replaces the old value and its metadata. The new value is "born" with:

• WTS(X) = TS(T): Identifying its creator
• RTS(X) = TS(T): Indicating the creator was also the first reader (logical initialization)

Why Reset RTS on Write?

When transaction T writes X, any previous reads of X were reads of the old value. Those read timestamps are associated with the old value, not the new one. Resetting RTS to TS(T) effectively starts fresh—the new value has only been "seen" by its creator.

This is conceptually different from RTS's behavior during reads. Reads accumulate information (capturing the youngest reader), while writes discard old information (since the old value no longer exists).

Practical Consideration: Write Visibility

In many implementations, the WTS update isn't immediately visible to other transactions. The new value might be buffered until transaction commit. This introduces complexity around when exactly WTS(X) reflects the pending write vs. the committed value—a topic we'll revisit when discussing strict timestamp protocols.

With both timestamps defined, we can now see the complete conflict detection mechanism. For each data item X, we maintain:

• RTS(X): Largest timestamp of any transaction that read X (constrains writes)
• WTS(X): Timestamp of the transaction that wrote X (constrains reads and writes)

These two timestamps work in concert to enforce timestamp-ordered execution without locks.

Understanding the Checks:

For Reads:

• Check WTS(X): Has anyone "younger" than me written X?
• If yes (TS(T) < WTS(X)): I'd be reading a future value—abort
• If no (TS(T) ≥ WTS(X)): Safe to read—update RTS if I'm younger than all previous readers

For Writes:

• Check RTS(X): Has anyone "younger" than me read X?
• If yes (TS(T) < RTS(X)): They read a value I'm about to change—abort
• Check WTS(X): Has anyone "younger" than me written X?
• If yes (TS(T) < WTS(X)): I'm overwriting a newer value—abort (or skip via Thomas Write Rule)
• If both pass: Write the value, update WTS(X) and reset RTS(X)

Let's work through several examples to solidify understanding of WTS behavior and its interaction with RTS.

Example 1: Sequential Writes by Increasingly Younger Transactions

In this ideal scenario, writes occur in timestamp order. Each write succeeds, and both WTS and RTS are updated to the writer's timestamp.

Example 2: Read-After-Write Conflict

T10 cannot read the value written by T30 because T10 is "older" and shouldn't see T30's work. After restart with timestamp 40, T40 > T30, so the read is allowed.

Example 3: Write-After-Write Conflict

Example 4: Complex Interleaving

Let's trace a more complex scenario with multiple data items:

This example shows:

• Step 4: T10's write to X fails because T20 (younger) has already read X
• Step 5: T40 successfully reads Y (40 ≥ 30) and updates RTS to 40
• Step 6: T25 also reads Y successfully (25 ≥ 30), but doesn't update RTS since 25 < 40

Notice how the timestamps create a consistent ordering despite the interleaved execution.

Understanding how WTS behaves across a data item's entire lifecycle—from creation through multiple updates—provides deeper insight into timestamp-based concurrency control.

Initial Creation:

When a data item X is first created (e.g., inserting a new row):

• WTS(X) = TS(T) where T is the creating transaction
• RTS(X) = TS(T) (the creator is treated as having read the item)

The item is "born" with both timestamps set to its creator's timestamp.

Successive Updates:

Each write operation completely replaces the old value and its metadata:

[Value: old_v, WTS: old_ts, RTS: old_rts] 
    → [Value: new_v, WTS: TS(T), RTS: TS(T)]

The old value and its entire access history are discarded. This is a fundamental difference from MVCC, where old versions are retained.

Deletion:

Deleting a data item in basic timestamp ordering is treated as a write with a special "tombstone" value:

• WTS(X) = TS(T) where T is the deleting transaction
• The item is marked deleted but may need to retain timestamps for conflict detection
• Actual removal may be deferred until no active transactions could reference it

Version History (Preview of MVCC):

In basic timestamp ordering, writes destroy previous values. This creates a problem: if a transaction is aborted, its writes must be undone, but the old value is gone. Solutions include:

1. Logging the old value before overwriting (for rollback)
2. Deferred writing until commit (buffer changes)
3. Multi-version storage (keep old versions—this leads to MVCC)

The inefficiency of options 1 and 2, combined with the elegance of option 3, is why MVCC has largely superseded pure timestamp ordering in modern systems.

Having explored both timestamps in depth, let's directly compare their characteristics and roles in the protocol.