← 🔀 Transactions & Concurrency Control
Subtopic 6 of 7

6.6Timestamp ordering

The idea

Timestamp ordering gives every transaction a timestamp and aborts any operation that arrives "too late" for its timestamp.

Think of it like this: Numbered tickets at a counter: a ticket holder cannot change something that a later ticket has already changed.

Why it exists

Questions give a schedule and ask which transaction aborts or what RTS/WTS end up as.

How it works

  1. Each item keeps RTS (largest reader timestamp) and WTS (largest writer timestamp).
  2. Read: abort if TS(T) < WTS; else RTS = max(RTS, TS).
  3. Write: abort if TS(T) < RTS; if TS(T) < WTS abort (or skip under Thomas); else WTS = TS.
  4. Result is conflict serializable in timestamp order and deadlock free.

Worked example: r1(A) w2(A) w1(A) with TS 1 and 2.

w1(A): TS 1 < WTS 2, so T1 aborts (basic), or the write is ignored under Thomas's rule.

Now play with it

  • →Tick the Thomas box and see the verdict change.
  • →Run the "write too late" example.
operationRTS(item) afterWTS(item) afterwhat happens
r1(A)10ok, RTS = 1
w2(A)12ok, WTS = 2
w1(A)12abort T1: TS 1 < WTS 2
r3(A)32ok, RTS = 3
w3(B)03ok, WTS = 3
Aborted transactionsT1

Read(X) by Ti: abort if TS(Ti) < WTS(X), else RTS = max(RTS, TS). Write(X) by Ti: abort if TS(Ti) < RTS(X); if TS(Ti) < WTS(X) abort (or ignore the write under Thomas), else WTS = TS(Ti). Timestamp ordering is conflict serializable and deadlock free, but not necessarily recoverable.

Check yourself

Thomas's write rule ignores a write when

Remember: Read: TS ≥ WTS. Write: TS ≥ RTS and TS ≥ WTS (Thomas ignores the second failure).
Exam notes (the dense version)

Each transaction gets a timestamp; each item keeps RTS and WTS. Read(X) by Ti: abort if TS(Ti) < WTS(X). Write(X): abort if TS(Ti) < RTS(X); if TS(Ti) < WTS(X) abort, or ignore the write under Thomas's write rule. Schedules are conflict serializable in timestamp order and deadlock free, but not necessarily recoverable or cascadeless.

Previous year questions: Transactions & Concurrency Control (15)

PYQs are grouped by topic, so this is the full set for Transactions & Concurrency Control; try the ones that match this subtopic. Open all 15 on the topic page.