Thomas Write Rule

In the basic timestamp ordering protocol, a transaction is aborted whenever it attempts to write a value that is "too late"—when another transaction with a larger timestamp has already read the data item. This strict approach ensures serializability, but it can lead to unnecessary transaction aborts that waste computational resources and reduce system throughput.

Consider this scenario: Transaction T₁ (timestamp 10) wants to write to data item X, but transaction T₂ (timestamp 20) has already written to X. Under basic timestamp ordering, T₁ must be aborted and restarted. But think about this carefully: if T₂'s write has already overwritten X, does T₁'s write even matter anymore?

This is precisely the insight that led to one of the most elegant optimizations in database concurrency control—the Thomas Write Rule.

The Thomas Write Rule was introduced by Robert H. Thomas in the late 1970s as part of his work on distributed database systems. Thomas observed that the basic timestamp ordering protocol was overly conservative in its handling of write operations, leading to transaction aborts that were unnecessary from the perspective of data correctness.

The Problem with Basic Timestamp Ordering:

In the basic timestamp ordering protocol, every write operation must adhere to a strict rule: a transaction T can write to data item X only if no transaction with a larger timestamp has already read or written X. The rationale is straightforward—if a later transaction has already accessed X, then allowing T to write would violate the timestamp order, potentially breaking serializability.

However, Thomas recognized a subtle but crucial distinction: reads and writes are fundamentally different operations with different implications for serializability.

Why Reads Must Be Protected, But Some Writes Can Be Ignored:

Consider the difference:

1. Read-Write Conflict: If T₂ (timestamp 20) has already read X, and T₁ (timestamp 10) wants to write X, we have a real problem. T₂ has made decisions based on the old value of X. If T₁'s write were allowed, it would change history—T₂ should have seen T₁'s value, not the old one. This violates serializability.

2. Write-Write Conflict: If T₂ (timestamp 20) has already written to X, and T₁ (timestamp 10) wants to write X, the situation is different. T₁'s write would simply be overwritten by T₂'s write anyway. In any serial schedule where T₁ comes before T₂, T₁'s write would be superseded. T₁'s write is obsolete before it even happens.

This distinction is the foundation of the Thomas Write Rule.

The Thomas Write Rule modifies the write rule of the basic timestamp ordering protocol. Let's first recall the basic protocol, then see how Thomas's modification improves it.

Basic Timestamp Ordering Protocol (Write Rule):

When transaction T wants to execute write(X):

1. If TS(T) < R-TS(X): A transaction with a larger timestamp has already read the old value of X. T's write would change history. Abort T and restart with a new timestamp.

2. If TS(T) < W-TS(X): A transaction with a larger timestamp has already written to X. T's write would be overwritten. Abort T and restart with a new timestamp.

3. Otherwise: Execute the write and set W-TS(X) = TS(T).

The Thomas Write Rule Modification:

The Thomas Write Rule changes only case 2. Instead of aborting T, we simply ignore the write operation and let T continue:

When transaction T wants to execute write(X):

1. If TS(T) < R-TS(X): A transaction with a larger timestamp has already read X. Abort T and restart.

2. If TS(T) < W-TS(X): A transaction with a larger timestamp has already written to X. T's write is obsolete. Ignore the write but do NOT abort T. Let T continue with its other operations.

3. Otherwise: Execute the write and set W-TS(X) = TS(T).

The Elegance of the Rule:

Notice that the Thomas Write Rule doesn't add complexity—it actually simplifies the protocol's response to one scenario. Instead of the expensive operation of aborting and restarting a transaction, we simply skip the obsolete write and continue. The transaction loses nothing (its write was going to be invisible anyway), and the system gains the benefit of avoiding unnecessary work.

Let's walk through a concrete example to see the Thomas Write Rule in action. Consider two transactions, T₁ and T₂, with timestamps 10 and 20 respectively, both operating on data item X.

Initial State:

• X = 100 (initial value)
• W-TS(X) = 0, R-TS(X) = 0

Schedule of Operations:

1. T₂ writes X = 200
2. T₁ attempts to write X = 150
3. T₁ reads Y and performs other operations
4. T₁ commits
5. T₂ reads Z and performs other operations
6. T₂ commits

Analyzing the Outcome:

In the Thomas Write Rule scenario, the final value of X is 200 (written by T₂). This is exactly what we want! In any serial schedule where T₁ (timestamp 10) executes before T₂ (timestamp 20), T₁'s write to X would be followed by T₂'s write—meaning T₂'s value would be the final one.

The Thomas Write Rule produces the same final database state as the serial schedule T₁ → T₂, but without the overhead of aborting and restarting T₁. The ignored write is called an obsolete write or a blind write that would have been immediately overwritten.

The Intuition:

Think of it this way: T₁'s write to X is like writing a message on a whiteboard, only to have T₂ immediately erase it and write a different message. Why bother writing the first message at all? The Thomas Write Rule captures this intuition formally.

The Thomas Write Rule's correctness isn't immediately obvious. How can we simply ignore a write operation and still maintain correctness? Let's examine the reasoning carefully.

The Serialization Order Argument:

The timestamp ordering protocol produces schedules that are equivalent to a serial schedule where transactions execute in timestamp order. If T₁ has timestamp 10 and T₂ has timestamp 20, the equivalent serial schedule is T₁ → T₂.

Now consider what happens to data item X in the serial schedule T₁ → T₂:

1. T₁ executes first, writing its value to X
2. T₂ executes second, overwriting X with its value
3. Final value of X = T₂'s written value

T₁'s write exists in the serial schedule, but its effect is invisible in the final state. Any transaction that reads X after both T₁ and T₂ will see T₂'s value, not T₁'s.

Formal Correctness Argument:

Let T_i be a transaction with timestamp TS(T_i), attempting to write data item X, where W-TS(X) = TS(T_j) and TS(T_i) < TS(T_j).

Claim: Ignoring T_i's write preserves serializability.

Proof Sketch:

1. The equivalent serial schedule orders transactions by timestamp: T_i before T_j.

2. In this serial schedule:

   • T_i writes to X first
   • T_j writes to X second, overwriting T_i's value
   • Final value of X = T_j's written value

3. By ignoring T_i's write and keeping T_j's write:

   • Final value of X = T_j's written value (same as serial schedule)
   • No transaction can observe T_i's write (it would be overwritten anyway)

4. The resulting schedule is view-equivalent to the serial schedule T_i → T_j.

Important Caveat: This argument works only because W-TS(X) = TS(T_j) > TS(T_i). If a third transaction T_k with TS(T_i) < TS(T_k) < TS(T_j) reads X, T_k would see T_j's value in both cases (with or without the Thomas Write Rule), maintaining consistency.

To deeply understand the Thomas Write Rule, we must appreciate the different roles of read and write timestamps and why they're handled differently.

R-TS(X): The Read Timestamp

The read timestamp R-TS(X) records the largest timestamp of any transaction that has read data item X. This is critical because:

1. Reads establish dependencies: When a transaction reads X, it makes decisions based on that value. Future transactions' writes cannot change what a past transaction "saw."

2. Reads cannot be undone: Once a transaction has read a value and potentially used it in computations or decisions, that read has consequences that persist even if the transaction later aborts.

3. Read-write conflicts break serializability: If T₁ (timestamp 10) tries to write X after T₂ (timestamp 20) has read X, we cannot allow it. T₂ has already seen the old value; allowing T₁'s write would mean T₂ should have seen T₁'s value instead.

W-TS(X): The Write Timestamp

The write timestamp W-TS(X) records the largest timestamp of any transaction that has written to data item X. This is simpler because:

1. Writes are overwritable: Unlike reads, a write's effect can be "erased" by a subsequent write.

2. Write-write conflicts can sometimes be resolved: If T₁ (timestamp 10) tries to write X after T₂ (timestamp 20) has written X, T₁'s value would be immediately superseded. No transaction can observe T₁'s write.

3. The Thomas Write Rule exploits this: We can safely ignore T₁'s write, treating it as if it happened but was immediately overwritten.

The Thomas Write Rule produces schedules that are view serializable but not necessarily conflict serializable. Understanding this distinction is crucial for appreciating what the Thomas Write Rule achieves.

Conflict Serializability Review:

A schedule S is conflict serializable if we can transform it into a serial schedule by swapping the order of non-conflicting operations. Two operations conflict if:

1. They belong to different transactions
2. They access the same data item
3. At least one of them is a write

View Serializability Review:

A schedule S is view serializable if:

1. For each data item, the same transaction performs the initial read in S as in some serial schedule S'
2. For each read operation, the same transaction wrote the value being read in S as in S'
3. For each data item, the same transaction performs the final write in S as in S'

The Thomas Write Rule and View Serializability:

When we ignore an obsolete write using the Thomas Write Rule, we may create a schedule that is not conflict serializable but is view serializable.

Example:

Consider transactions T₁ (timestamp 10) and T₂ (timestamp 20):

Schedule S:
T₂: write(X) 
T₁: write(X) [IGNORED by Thomas Write Rule]
T₂: commit
T₁: commit

Conflict Analysis:

• T₂'s write(X) and T₁'s write(X) conflict
• In schedule S, T₂'s write appears before T₁'s write
• But T₁ has a smaller timestamp, so in the equivalent serial schedule, T₁ should come first
• The schedule is NOT conflict serializable!

View Analysis:

• The serial schedule T₁ → T₂ would have T₂ as the final writer to X
• In schedule S (with T₁'s write ignored), T₂ is also the final writer to X
• No transaction reads X in this schedule
• The schedule IS view serializable!

The Key Insight:

The Thomas Write Rule sacrifices conflict serializability for better performance, but maintains the stronger guarantee of view serializability. This is acceptable because view serializability is the true correctness criterion—it ensures the schedule produces the same results as some serial schedule.

The Thomas Write Rule represents one of several strategies for handling write-write conflicts in concurrent database systems. Let's compare it with alternative approaches.

When to Use the Thomas Write Rule:

The Thomas Write Rule is most beneficial in systems where:

1. Write-write conflicts are common: Applications with many concurrent writes to shared data items benefit most.

2. Transactions are long-running: Aborting and restarting long transactions is expensive; ignoring obsolete writes saves significant work.

3. View serializability is acceptable: Applications that don't require strict conflict serializability can leverage this optimization.

4. Read-write conflicts are rare: The rule doesn't help with read-write conflicts, so systems with many reads may see less benefit.

When NOT to Use the Thomas Write Rule:

1. Strict conflict serializability required: Some applications need the stronger guarantee; auditing systems, for example.

2. Write operations have side effects: If writing triggers external actions (logging, notifications), ignoring writes could cause inconsistencies.

3. Recovery considerations: Ignoring writes complicates some recovery scenarios (discussed in later sections).

We've covered the foundational concepts of the Thomas Write Rule. Let's consolidate the key takeaways:

What's Next:

In the following pages, we'll explore the concept of outdated writes in greater depth, understanding exactly when and why writes become obsolete. We'll then examine how the Thomas Write Rule handles these cases and analyze the performance improvements it provides. Finally, we'll rigorously examine the correctness guarantees to ensure you have complete confidence in applying this optimization.