Timestamp Ordering in Distributed System

In this tutorial you are going to learn about Timestamp Ordering in Distributed System.

Introduction

Timestamp ordering is a unique identifier created by a database management system that indicates the relative starting line of a transaction.

Timestamp is nothing but a tag that can be attached to any transaction or to any data item, which denotes a specific time on which the transaction or the data item had been activated in any way.

It is denoted by TS(Ti)

For two transaction Ti and Tj,

Ts(Ti)< Ts(Tj) -> Ti started before Tj

Ts->time of state.

Timestamp Allocation

Each transaction T1 is assigned a unique fixed timestamp that is monotonically increasing. Let Ts(T1) be the timestamp allocated to transaction T1. Different schemes assign timestamps at different times during the transaction.

Strategies or methods to implement the scheme:

1. System clock as a timestamp.
2. Logical counter that is incremented after a new timestamp has been assigned.
3. Hybrid.

Transaction read and write objects without locks: Every object X is tagged with the timestamp of the last transaction that is successfully did read and write:

W-Ts(x) – Write timestamp on X

R-Ts(X) -Read timestamp on X

Check timestamp for every operation: If transaction to access an object “ from the future”, it aborts and restarts.

With each shared data item associated with 2 timestamps

1. W-time stamp(X) -> Largest Ts value {write(X)}
2. R-time stamp(X)->Largest Ts value{Read (X)}

Optimistic Concurrency Control

It is applied to transactional systems such as relational DBMS and software transactional memory.

1. Read phase : Read and perform write on local buffer.
2. Validation: Synchronisation checking.
3. Write phase: Local writes are made global.

It assigns each transaction a unique timestamp at the end of its read phase A transaction validate

1. Ti complete write phase before Tj begin read phase
2. Tj does not read any item written by Ti and Ti finishes its write phase before Tj begins its write phase.

Timestamp Ordering Protocol

It ensures that any conflicting Read and write operations are executed in a timestamp order.

• The unique value assigned to every transaction tells the order when they enter into the systems.
• Read_TS(RTS)=latest lost transaction number which performed read successfully.
• Write_TS(WTS)= Latest lost transaction number which performed write successfully.

Rules:

1. Transaction T1 issues a Read(A) operation
   • If WTS(A)>TS(T1) It rolls back T1. Ti is an older transaction than the last transaction that wrote the value of A (request will fail).
   • Otherwise execute R(A) operation. Set RTS(A)=Max{RTS(A), TS(T1)}. Ti is allowed to read updated value of A.
2. Transaction T1 issues write(A) operation
   • If RTS(A)>TS(T1) then RollBack T1. Ti is allowed to modify or write value of Q Ts(Ti) will become current value of W(A).
   • If WTS(A)> Ts(T1) then Rollback T1. Younger transaction is already using value of A. (Updation is not allowed).
   • Otherwise execute write(A) operation. Set WTS(A)=TS(T1). Younger transaction has updated value of Q.

---

This article on Timestamp Ordering in Distributed System is contributed by Hemalatha P. If you like TheCode11 and would like to contribute, you can also write your article and mail to thecode11info@gmail.com