Thomas write rule

Short description: Rule in timestamp-based concurrency control

In computer science, particularly the field of databases, the Thomas write rule is a rule in timestamp-based concurrency control. It can be summarized as ignore outdated writes.

It states that, if a more recent transaction has already written the value of an object, then a less recent transaction does not need to perform its write since the more recent one will eventually overwrite it.

The Thomas write rule is applied in situations where a predefined logical order is assigned to transactions when they start. For example, a transaction might be assigned a monotonically increasing timestamp when it is created. The rule prevents changes in the order in which the transactions are executed from creating different outputs: The outputs will always be consistent with the predefined logical order.

For example, consider a database with 3 variables (A, B, C), and two atomic operations C := A (T1), and C := B (T2). Each transaction involves a read (A or B), and a write (C). The only conflict between these transactions is the write on C. The following is one possible schedule for the operations of these transactions:

[math]\displaystyle{ \begin{bmatrix} T_1 & T_2 \\ & Read(A) \\ Read(B) & \\ &Write(C) \\ Write(C) & \\ Commit & \\ & Commit \end{bmatrix} \Longleftrightarrow \begin{bmatrix} T_1 & T_2 \\ & Read(A) \\ Read(B) & \\ & Write(C) \\ & \\ Commit & \\ & Commit\\ \end{bmatrix} }[/math]

If (when the transactions are created) T1 is assigned a timestamp that precedes T2 (i.e., according to the logical order, T1 comes first), then only T2's write should be visible. If, however, T1's write is executed after T2's write, then we need a way to detect this and discard the write.

One practical approach to this is to label each value with a write timestamp (WTS) that indicates the timestamp of the last transaction to modify the value. Enforcing the Thomas write rule only requires checking to see if the write timestamp of the object is greater than the time stamp of the transaction performing a write. If so, the write is discarded

In the example above, if we call TS(T) the timestamp of transaction T, and WTS(O) the write timestamp of object O, then T2's write sets WTS(C) to TS(T2). When T1 tries to write C, it sees that TS(T1) < WTS(C), and discards the write. If a third transaction T3 (with TS(T3) > TS(T2)) were to then write to C, it would get TS(T3) > WTS(C), and the write would be allowed.

References

• Robert H. Thomas (1979). "A majority consensus approach to concurrency control for multiple copy databases". ACM Transactions on Database Systems 4 (2): 180–209. doi:10.1145/320071.320076. 

©