Chapter 32 of 41

Timestamp Ordering Protocol

In the previous chapter, Lock-Based Concurrency Control (2PL), the order of transactions was decided while they ran: whoever reached its lock point first came first in the equivalent serial schedule. That approach needs waiting, and waiting can lead to deadlocks.

The Timestamp Ordering Protocol takes a different view. It decides the serial order in advance, the moment each transaction starts, and then simply makes sure that every conflicting operation respects that order.

In simple words:

An older transaction must appear to run before a younger one. If an operation would break this order, the transaction that is "too late" is rolled back and restarted.

There are no locks, so no transaction ever waits for another, and therefore no deadlocks can occur.


What Is a Timestamp?

When a transaction Ti enters the system, the DBMS gives it a unique number called its timestamp, written TS(Ti).

  • It can come from the system clock or from a simple counter that increases by 1 for every new transaction.

  • If Ti started before Tj, then TS(Ti) < TS(Tj). A smaller timestamp means an older transaction.

The protocol guarantees that the schedule is equivalent to the serial schedule in which transactions run in increasing timestamp order.

TS(T1) = 10   (oldest)
TS(T2) = 20
TS(T3) = 30   (youngest)

Required equivalent serial order:  T1 → T2 → T3

Read and Write Timestamps of a Data Item

To check the order, the DBMS stores two values for every data item Q:

Value

Meaning

W-timestamp(Q) or WTS(Q)

The largest timestamp of any transaction that successfully wrote Q

R-timestamp(Q) or RTS(Q)

The largest timestamp of any transaction that successfully read Q

Think of them as "the youngest transaction that has already written Q" and "the youngest transaction that has already read Q". If an older transaction now arrives wanting to do something that conflicts with what a younger one already did, it has arrived too late.


Basic Timestamp Ordering Rules

Rule 1: Ti wants to read(Q)

if TS(Ti) < W-timestamp(Q):
    # a younger transaction has already overwritten Q;
    # the value Ti should have seen is gone
    REJECT read, ROLL BACK Ti
else:
    execute read(Q)
    R-timestamp(Q) = max(R-timestamp(Q), TS(Ti))

Rule 2: Ti wants to write(Q)

if TS(Ti) < R-timestamp(Q):
    # a younger transaction already read the old value of Q,
    # assuming Ti's write would never come
    REJECT write, ROLL BACK Ti
else if TS(Ti) < W-timestamp(Q):
    # a younger transaction already wrote Q; Ti's value is obsolete
    REJECT write, ROLL BACK Ti
else:
    execute write(Q)
    W-timestamp(Q) = TS(Ti)

A rolled-back transaction is restarted with a new, larger timestamp. Why new? If it kept its old (small) timestamp, it would be "too old" again and keep getting rejected.

Quick Way to Remember

Operation by Ti

Rejected if a younger transaction has already…

Check

read(Q)

written Q

TS(Ti) < WTS(Q)

write(Q)

read Q or written Q

TS(Ti) < RTS(Q) or TS(Ti) < WTS(Q)

Notice that read after read is never a problem — two reads do not conflict, just as S is compatible with S in locking.


Worked Example: Step-by-Step Trace

Let TS(T1) = 10, TS(T2) = 20, TS(T3) = 30. Initially all RTS and WTS values are 0. Schedule:

R1(A), R2(A), W2(A), R3(B), W3(B), R1(B)

Step

Operation

Check

Result

RTS / WTS after

1

R1(A)

10 < WTS(A)=0? No

OK

RTS(A)=10

2

R2(A)

20 < WTS(A)=0? No

OK

RTS(A)=20

3

W2(A)

20 < RTS(A)=20? No. 20 < WTS(A)=0? No

OK

WTS(A)=20

4

R3(B)

30 < WTS(B)=0? No

OK

RTS(B)=30

5

W3(B)

30 < RTS(B)=30? No. 30 < WTS(B)=0? No

OK

WTS(B)=30

6

R1(B)

10 < WTS(B)=30? Yes

T1 rolled back

unchanged

Why is step 6 rejected? In the required order T1 → T2 → T3, T1 should have read B before T3 wrote it. But T3 has already written B, so the value T1 needs no longer exists. T1 arrived too late and must restart with a new timestamp (say 40), after which it will be treated as the youngest transaction.

(We checked this trace with a small Python simulator of the rules above; the RTS/WTS values match.)


Thomas' Write Rule

Look at this schedule, again with TS(T1) = 10 and TS(T2) = 20:

R1(A), W2(A), W1(A)

Under basic timestamp ordering:

  • R1(A): OK, RTS(A) = 10

  • W2(A): 20 < RTS(A)=10? No. OK, WTS(A) = 20

  • W1(A): 10 < RTS(A)=10? No. 10 < WTS(A)=20? Yes → T1 rolled back

But think about it. In the serial order T1 → T2, T1's write of A would be immediately overwritten by T2's write anyway. Nobody (with a timestamp between 10 and 20) has read T1's value. So T1's write is simply obsolete — we can just skip it instead of rolling T1 back.

Thomas' Write Rule: if TS(Ti) < W-timestamp(Q) (and TS(Ti) ≥ R-timestamp(Q)), the write is obsolete and is ignored; Ti continues normally.

The modified write rule is:

if TS(Ti) < R-timestamp(Q):
    ROLL BACK Ti                 # still needed: a younger txn read the old value
else if TS(Ti) < W-timestamp(Q):
    IGNORE this write            # obsolete write (Thomas' rule)
else:
    execute write(Q); W-timestamp(Q) = TS(Ti)

Note that the first check is unchanged. If a younger transaction has read Q, an older write can never be ignored, because that reader should have seen it.

Thomas' Rule and View Serializability

The schedule R1(A), W2(A), W1(A) is not conflict serializable: R1(A) before W2(A) gives T1 → T2, and W2(A) before W1(A) gives T2 → T1, a cycle. Yet with Thomas' rule it is accepted. Is that safe?

Yes, because T1's write is thrown away. What actually reaches the database is R1(A), W2(A), which is equivalent to the serial schedule T1, T2: T1 reads the initial A in both, and the final value of A is T2's in both. Be careful here: the schedule as written, with W1(A) really performed last, would not be serializable in any sense, because then T1 would be the final writer. Thomas' rule is safe precisely because it deletes that write.

A cleaner example shows the link to view serializability. Add T3 with TS(T3) = 30:

R1(A), W2(A), W1(A), W3(A)

R1(A)  OK        RTS(A) = 10
W2(A)  OK        WTS(A) = 20
W1(A)  10 < RTS(A)=10? No.  10 < WTS(A)=20? Yes → IGNORED (Thomas)
W3(A)  OK        WTS(A) = 30

This schedule is not conflict serializable (it still has the T1 → T2 → T1 cycle), but it is view serializable, equivalent to T1, T2, T3: T1 reads the initial A, and T3 makes the final write in both. It works because of the blind writes W2(A) and W3(A) (writes without a preceding read), exactly the situation from the Conflict & View Serializability chapter where view serializability is larger than conflict serializability. Basic TO would have rolled T1 back here; Thomas' rule accepts it.

Protocol

Schedules it produces are

Basic timestamp ordering

Conflict serializable

Timestamp ordering + Thomas' write rule

View serializable (may be non-conflict-serializable)


Properties of Timestamp Ordering

Advantages

  • Conflict serializable: every conflicting pair is executed in timestamp order, so all edges in the precedence graph go from older to younger. There can be no cycle.

  • Deadlock-free: no transaction ever waits; it either proceeds or is rolled back.

Disadvantages

  • Starvation is possible: a long transaction may keep getting rolled back by a stream of short, younger ones.

  • Not recoverable by default: basic timestamp ordering checks only the order, not commits. Example: T1 writes A, T2 (younger) reads A — allowed — and commits; then T1 aborts. T2 read a value that never existed. The schedule is non-recoverable.

  • Overhead: every read updates RTS(Q), so even a read becomes a write to metadata. Rollbacks also waste work.

Making It Recoverable

  • Strict timestamp ordering: if Ti wants to read or write Q and a transaction Tj with TS(Tj) < TS(Ti) has written Q but not yet committed, Ti waits until Tj commits or aborts. This gives cascadeless (and recoverable) schedules. It is still deadlock-free, because a transaction only ever waits for an older one, so a cycle of waits is impossible.

  • Alternatively, perform all writes together at the end of the transaction, or track commit dependencies so that a reader cannot commit before the writer it read from.


Timestamp Ordering vs Two-Phase Locking

Feature

2PL

Timestamp Ordering

Serial order decided

Dynamically (lock points)

In advance (start timestamps)

On conflict

Transaction waits

Transaction is rolled back

Deadlock possible?

Yes (except conservative 2PL)

No

Starvation possible?

Yes

Yes

Serializability

Conflict serializable

Conflict serializable (view with Thomas' rule)

Recoverable by default?

No (Strict 2PL is)

No (Strict TO is)

Good for

High-conflict workloads

Low-conflict workloads

An important exam fact: some schedules are allowed by 2PL but not by timestamp ordering, and vice versa. Neither protocol's set of schedules contains the other. For example, under 2PL a younger transaction may finish its conflicting operations before an older one — something TO would never allow because TO fixes the order by start time.


Validation-Based (Optimistic) Concurrency Control

If conflicts are rare, checking every single operation is wasted effort. Optimistic concurrency control lets a transaction run without any checks and validates it only at the end. Each transaction goes through three phases:

  1. Read phase: read data and write only into private local copies.

  2. Validation phase: check whether its reads conflict with the writes of transactions that committed while it was running.

  3. Write phase: if validation passes, copy local changes into the database; otherwise roll back and restart.

The timestamp used for ordering is given at the start of the validation phase. Because writes happen only after validation, there are no cascading rollbacks.

Multiversion Timestamp Ordering

In basic TO, an old transaction's read is rejected because the value it needs was overwritten. What if the database simply kept the old version? In multiversion schemes each write creates a new version of Q tagged with the writer's timestamp, and a read by Ti returns the newest version whose write timestamp is ≤ TS(Ti). Reads are never rejected and never wait.

This idea, generally called MVCC (Multiversion Concurrency Control), is used by almost every modern database. PostgreSQL, Oracle, and MySQL InnoDB all keep older row versions so that ordinary SELECT statements can read a consistent snapshot without blocking writers. InnoDB stores those old versions in its undo logs, which we will meet in the Recovery & Logging chapter.


Common Mistakes

  • Restarting with the same timestamp. A rolled-back transaction gets a new timestamp; otherwise it would fail again.

  • Applying Thomas' rule when TS(Ti) < RTS(Q). The write must still be rejected then; Thomas' rule only relaxes the WTS check.

  • Saying TO gives recoverable schedules. Basic TO can produce non-recoverable schedules.

  • Updating RTS(Q) to TS(Ti) blindly. It is the maximum of the old RTS and TS(Ti). An older reader must not lower it.

  • Mixing up "older" and "smaller". Older transaction = smaller timestamp = should come first.


Interview Questions

Why is timestamp ordering deadlock-free?

Because in basic TO no transaction ever waits for another. A conflicting operation is either executed or causes a rollback. Without waiting, there is no circular wait.

What is Thomas' write rule?

If an older transaction tries to write Q after a younger transaction has already written Q (and no younger transaction has read Q), the older write is obsolete and is ignored instead of rolling the transaction back.

Is a schedule produced by TO with Thomas' write rule always conflict serializable?

No. It is always view serializable (once the ignored writes are removed), but it can be non-conflict-serializable, e.g. R1(A), W2(A), W1(A), W3(A) with TS(T1) < TS(T2) < TS(T3): W1(A) is ignored and the schedule is view equivalent to T1, T2, T3 even though its precedence graph has a cycle.

When is Ti's read(Q) rejected?

When TS(Ti) < W-timestamp(Q), i.e. a younger transaction has already overwritten the value Ti should have read.

When would you prefer optimistic concurrency control?

When most transactions are read-only or rarely conflict, so validation almost always succeeds and the cost of locking or per-operation checks is avoided.


Summary

  • Every transaction gets a unique timestamp at start; the equivalent serial order is increasing timestamp order.

  • Each item keeps RTS(Q) and WTS(Q). A read is rejected if TS(Ti) < WTS(Q); a write is rejected if TS(Ti) < RTS(Q) or TS(Ti) < WTS(Q).

  • Rejected transactions are rolled back and restarted with a new timestamp.

  • Basic TO is conflict serializable and deadlock-free, but can cause starvation and non-recoverable schedules.

  • Thomas' write rule ignores obsolete writes and produces view-serializable schedules.

  • Strict TO, optimistic (validation) and multiversion schemes build on the same idea; MVCC is what real databases use for non-blocking reads.

Locking protocols avoid rollbacks but risk deadlocks. In the next chapter, Deadlocks in DBMS, we will see how databases prevent, detect and recover from them — and some prevention schemes will reuse the timestamps you just learned.