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

Satisfying basic 2PL will also satisfy basic timestamp protocol?

---

Yes u r right..I have edited..It should be timestamp instead of 2PL..:)

---

Can you please expalin what do u mean by one to one correspondence?

---

This means that given a conflict serialisable schedule , we have a basic timestamp protocol satisfying schedule..
And for view serialisable we have Thomas Write schedule

---

Yes but reverse is not true for both the cases right?

---

No it is a strong statement so true both ways..Thats why I have said one to one correspondence..

---

Basic timestamp protocol doesnt have one-one correspondence with conflict serializable schedules. See Korth for this. They have clearly stated there are schedules which are possible under 2PL but not under timestamp protocol. And there are schedules which are conflict serializable but not possible under 2PL.

@Habib. Could you give reference for this?

---

I mean to say that u can get a timestamp ordering which is the same as topological sort of given schedule..U r talking about the case in which transactions are already assigned some time stamp values ..But here no transaction is assigned any timestamp value..So we can take according to topological sort..No issue in that..

---

got it. You backtracked. But had there been more than 1 conflict serializable schedule, then it would become impossible.

---

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!