retagged by
633 views
0 votes
0 votes

Consider the following schedule:

$\begin{array}{|c|c|} \hline T1&  T2 \\ \hline R(A) &{} \\ \hline R(B) & {} \\ \hline R(C) & {} \\ \hline {} & R(A) \\ \hline {} & R(B) \\ \hline {} & F: \text{_____} \\ H: \text{______} & {} \\ \hline {} & R(C) \\ \hline \end{array}$

What are the possible values of F & H for which the above schedule is allowed under Thomas Write Rule but NOT under Basic Timestamp Ordering Protocol if $\text{timestamp(T2)} > \text{timestamp(T1)}$?

  1. $W(B), W(C)$
  2. $W(A), W(A)$
  3. $W(A) ,W(B)$
  4. $W(C), W(A)$
retagged by

1 Answer

Best answer
2 votes
2 votes

The answer looks bigger(I noticed after writing) it is because I copied the above table twice, otherwise there are just a few lines. 

 T1         T2
 R(A)  
 R(B)  
 R(C)  
    R(A)
    R(B)
   F:___W(B)______

 H:____W(C)____

 
   R(C)

Option A allows both in basic timestamp ordering and Thomas write rule,
W(C) of T1 checks the Read_TS(C)>TS(T1) || Write_TS(C)>TS(T1)
which will be false
i.e. no new transaction has read C before T1,  so T1 can write successfully.
 After that T2 will check for Write_TS(C)>TS(T2) which will be false i.e now newer transaction has written before T2 want to read it, so allowed to read C.

 T1         T2
 R(A)  
 R(B)  
 R(C)  
    R(A)
    R(B)
   F:__W(A)_______
 H:__W(A)______  
   R(C)

    Option B:

Let T1, T2 have timestamps as 100,200 i.e T1 is older and T2 is newer.

Then when T2 want to write(A) it will check
Read_TS(A)>TS(T2) || Write_TS(A)>TS(T2) which will be false as lastly T2 itself read the value and now newer transaction has written or read A. So T2 will be allowed to Write A and update Write_TS(A)=200. 

when T1 want to write(A) it will check
Read_TS(A)>TS(T1) || Write_TS(A)>TS(T1) which will be true, hence it will be not allowed in to do this operation and will be rolled back.
But in timestamp ordering this will allowed as just this Write(A) of T1 will be just ignored, T2 has already written the new value of A.
 

To get the last line, it means if T1 has to write the value of A as 10 and T2 as 20 when they executed in timestamp order(T1->T2 as TS(T1)<TS(T2)) last value of A will be written by T2 i.e 20. But Thomas is a smart guy, he thought when T2 has already updated A's value as 20 why to bother about T1 which is updating it to an obsolete value, so he just ignored the T1's Write(A).

selected by
Answer:

Related questions

1 votes
1 votes
1 answer
1
2 votes
2 votes
1 answer
2
Bikram asked Aug 26, 2017
318 views
Consider the following transaction involving two bank accounts $A$ and $B$.$\begin{array}{|l|} \hline \text{read(A);} \\ \hline A:=A-250; \\ \hline \text{write(A);} \\ \...
1 votes
1 votes
1 answer
3
Bikram asked Aug 26, 2017
294 views
A schedule with two transactions T1 and T2 is as mentioned below:$\begin{array}{|c|c|} \hline T1 & T2 \\ \hline \text{read(A)} & {} \\ \hline \text{write(A)} & {} \\ \hl...
3 votes
3 votes
2 answers
4