2,940 views
2 votes
2 votes
Consider the following schedule for transaction T1,T2,T3

r1(x),r2(y),r3(y),w1(x),w3(x),r2(z),w1(x)

Also assume that the timestamp for the three transaction is{30,10,20} which of the following statement is true with respect to the above schedule?

ANS will be Thomas Write Time Stamp Protocol but not basic time stamp protocol HOW?

2 Answers

Best answer
7 votes
7 votes
  T2 T3 T1
Timestamps 10 20 30
      R(X)
  R(Y)    
    R(Y)  
      W(X)
    W(X)  
  R(Z)    
      W(X)

Basic Timestamp Protocol (BTSP) states that a schedule is allowed only if it is conflict serializable in the increasing order of the timestamp.Here, R1(X) clearly conflicts with W3(X), hence, given schedule does not comply with BTSP, and T3 must be rolled back.

Similarly, as Thomas Write Rule (TWR) saves us from aborting a transaction only in the case of an obsolete write in a WW conflict pair, the schedule again does not comply with TWR due to the presence of a R1(X)...W3(X) conflict. Note that Thomas Write rule could only save us a roll back in the case of T1(X)...T3(X) conflict, but not R1(X)...W3(X).

Hence, no matter the given answer, the given schedule does not follow both BTSP and TWR :)

selected by
1 votes
1 votes
Time stamp is value attached by sytsem to a transaction to indicate when that transaction was arrived in the system  

Or in other word you give a time to transaction when it was enterd in to system

note that here in transaction 1 (T1) has time stamp 30 , T2  has 10 and T3 has 20 Hence from the above given timestamp we can make out T2 is first one to come followed by T3 and T2

In a basic Time stamp protocol : A early arriving Timestamp(older ) must complete its all operation as compared to late arriving transaction (younger ). Here in this above T3 is older as comapred to T1 so all operation of T3 must happen before T1. but T1 is writing on a date item (X) before T3 write . SO the basic timestamp rule is violated

Hence this doesnt come under basic time stamp .

Now thomas  Write Timestamp : This can happen between WW pair . here it say all opertaion of older must happen before younger . except the write of older and write of younger . the reason why this pair is allowed beacuse anyways the final data item would be always of younger transaction . so older one write on a data item can be neglected .

Here if you see such WW pair happen between T1 and T3

Here T3 inspite of been older , T1 is writing before that . So the above come under thomas basic timestamp :)

Related questions

0 votes
0 votes
1 answer
1
Mrityudoot asked Jan 12
128 views
Isn’t F$^{+}$ minimal cover? If C $\rightarrow$ A is already there, then why does augmented CD $\rightarrow$ A needs to be?
0 votes
0 votes
1 answer
2
0 votes
0 votes
1 answer
3