Thomas write rule

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 perform its own write since it will eventually be overwritten by the more recent one.

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:

{\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}}

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.

This article is issued from Wikipedia - version of the 7/30/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.