Wednesday, 18 April 2012

Thomas' Write Rule Correctness of Timestamp Protocol

We know timestamp based schedules are not recoverable and also there is a possibility of starvation. If this problem is recoverable by maintaining some rules but Thomas' Write Rule is the best solution for Timestamp based protocol. This part of the tutorial I described Thomas' Write Rule. In this rule read operation remain unchanged but write operations are different from the timestamp-ordering protocol. 
Suppose that transaction Ti issues write(Q) and the Thomas' rule is:
A. If TS(Ti) < R-timestamp(Q) then the system reject the write operation and Ti is rolled back. Because at any transaction the first operation must be read operation.
B. If TS(Ti) < W-timestamp(Q) then the operation rejected and Ti is rolled back. Because this write operation attempting to produce obsolete value.
C. Otherwise the system executes the write operation.

Now consider the following schedule. In this schedule T1 starts before T2 and we assume that TS(Ti)<TS(T2).
The read(Q) operation of T1 is succeeded and when T1 wants to write(Q) operation we find that TS(T1) < W-timestamp(Q) where Q-timestamp(Q) = TS(T2). So this operation rejected and T1 must be rolled back because T2 has already written Q.




No comments:

Post a Comment