Timestamp Based Protocol

Timestamp Based Protocol                             

• The time stamp ordering protocol is a scheme in which the order of transaction' is decided in advance based on their timestamps. Thus the schedules are serialized according to their timestamps.

• The timestamp-ordering protocol ensures that any conflicting read and write operations are executed in timestamp order.

• A larger timestamp indicates a more recent transaction or it is also called as younger transaction while lesser timestamp indicates older transaction.

• Assume a collection of data items that are accessed, with read and write operations, by transactions.

• For each data item X the DBMS maintains the following values:

      • RTS(X): The Timestamp on which object X was last read (by some transaction T1, i.e., RTS(X):=TS(T;)) [Note that: RTS stands for Read Time Stamp]

      • WTS(X): The Timestamp on which object X was last written (by some transaction T,, i.e., WTS(X):=TS(T)) [Note that: WTS stands for Write Time Stamp]     

• For the following algorithms we use the following assumptions: - A data item X in the database has a RTS(X) and WTS(X). These are actually the timestamps of read and write operations performed on data item X at latest time.

• A transaction T attempts to perform some action (read or write) on data item X on some timestamp and we call that timestamp as TS(T).

• By timestamp ordering algorithm we need to decide whether transaction T has to be aborted or T can continue execution.

Basic Timestamp Ordering Algorithm

Case 1 (Read): Transaction T issues a read(X) operation

i) If TS(T) < WTS(X), then read(X) is rejected. T has to abort and be rejected.

ii) If WTS(X) ≤ TS(T), then execute read(X) of T and update RTS(X).

Case 2 (Write): Transaction T issues a write(X) operation

i) If TS(T) < RTS(X) or if TS(T) < WTS(X), then write is rejected

ii) If RTS(X)≤ TS(T) or WTS(X) ≤ TS(T), then execute write(X) of T and update WTS(X).

Example for Case 1 (Read operation)

(i) Suppose we have two transactions T1 and T2 with timestamps 10 sec and 20 sec respectively.

RTS(X) and WTS(X) is initially = 0

Then RTS(X)=10, when transaction T₁ executes

After that WTS(X) =20 when transaction T₂ executes

Now if Read operation R(X) occurs on transaction T₁ at TS(T₁) = 10 then

TS(T₁) i.e. 10 <WTS(X) i.e. 20, hence we have to reject second read operation on T₁ i.e.

(ii) Suppose we have two transactions T1 and T2 with timestamps 10 sec and 20 sec respectively.

RTS(X) and WTS(X) is initially = 0

Then WTS(X) =10 as transaction T₁ executes.

Now if Read operation R(X) occurs on transaction T₂ at TS(T₂) = 20 then

TS(T₂) i.e. 20 >WTS(X) which is 10, hence we accept read operation on T₂. The transaction T₂ will perform read operation and now RTS will be updated as

RTS(X)=20

Example for Case 2 (Write Operation)

(i) Suppose we have two transactions T₁ and T₂ with timestamps 10 sec and 20 sec respectively.

RTS(X) and WTS(X) is initially = 0

Then RTS(X)=10, when transaction T₁ executes

After that WTS(X) =20 when transaction T₂ executes

Now if Write operation W(X) occurs on transaction T₁ at TS(T₁) = 10 then TS(T₁) i.e. 10 <WTS(X), hence we have to reject second write operation on T₁ i.e.

(ii) Suppose we have two transactions T₁ and T₂ with timestamps 10 sec and 20 sec respectively.

RTS(X) and WTS(X) is initially = 0

Then WTS(X) =10 as transaction T₁ executes.

Now if write operation W(X) occurs on transaction T₂ at TS(T₂) = 20 then

TS(T₂) i.e. 20 >WTS(X) which is 10, hence we accept write operation on T₂. The transaction T₂ will perform write operation and now WTS will be updated as

WTS(X) = 20

Advantages and disadvantages of time stamp ordering

Advantages

(1)Schedules are serializable

(2) No waiting for transaction and hence there is no deadlock situation.

Disadvantages

(1) Schedules are not recoverable once transactions occur.

(2) Same transaction may be continuously aborted or restarted.