Basic Time Stamp Protocol

Question

Which of the following schedule is allowed under basic time stamp protocol?

S1: R1(X) R3(X) W1(X) R2(X) W3(X)

S2: R1(X) R3(X) W3(X) W1(X) R2(X)

S3: R3(X) R2(X) W3(X) R1(X) W1(X)

S4: R1(X) R3(X) R2(X) W1(X) W3(X)

A. S1

B. S2

C. S3

D. S4

Comments

@Habibkhan sir, In s3 How w1(x) will be executed in B-Time stamp ordering protocol. Do You not think it will be rollback? 

Answer 1

As we know there exists one to one correspondence between :

a) Basic timestamp schedule and conflict serialisable.

b) Thomas Write timestamp schedule and view serialisable

So basically we have to check which one is conflict serialisable..

A) is not conflict serialisable as we have conflict pairs R₁(X) - W₃(X) and R₃(X) - W₁(X) .Making the precedence graph cyclic hence and hence not conflict serialisable..

B) is not conflict serialisable as we have conflict pairs R₁(X) - W₃(X) and W₃(X) - W₁(X) .Making the precedence graph cyclic hence and hence not conflict serialisable..

D) is not conflict serialisable as we have conflict pairs R₁(X) - W₃(X) and R₃(X) - W₁(X) .Making the precedence graph cyclic hence and hence not conflict serialisable..

But C) does not any such conflict pairs which are resulting to cycle in precedence graph..Hence it is conflict serialisable and hence alowed under basic 2PL protocol..

Hence C) option should be correct..

Comments

Habib
If you don't even consider any timestamp value associated with the transactions, then what is the point of this question?
We must use value of the system clock to assign the timestamp values.

---

@gaurab

i too have the same doubt.. here we should take time stamps of the transactions according to their order of arrival.

otherwise they would have asked .. which one of schedules is conflict serializable schedule?

here the question is about timestamp ordering protocol not 2PL protocol.

am I missing something.

---

The given option is correct but the explanation is wrong!