Timestamp ordering protocol; Thomas write rule

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

1. Under wound-wait, what happens when an older transaction requests an item held by a younger one? from Lesson 6.6.4
2. What does 2PL guarantee, and what does it not? from Lesson 6.6.2
3. What is a blind write? from Lesson 6.4.3

1 · The Hook

Locks make transactions wait, and waiting can deadlock. Timestamp ordering never makes anyone wait for a lock: every transaction gets a timestamp at birth, and the DBMS simply insists that conflicting operations happen in timestamp order. An operation that arrives "too late" aborts its transaction, which restarts with a new timestamp. GATE traces these rules step by step.

2 · Predict First

TS(T1) = 1, TS(T2) = 2. Schedule: R1(A) W2(A) W1(A). Under timestamp ordering, which operation fails, and why?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

Predict First — the answer

W1(A) fails. T2 (younger) has already written A (WTS(A) = 2). Letting the older T1 write now would put T1's write after T2's, against timestamp order. T1 is aborted. (With the Thomas write rule, W1(A) is instead simply ignored.)

Timestamps

• Each transaction Ti gets a unique timestamp TS(Ti) when it starts (older = smaller).
• Each data item X keeps RTS(X) (largest TS of any transaction that read X) and WTS(X) (largest TS of any transaction that wrote X).

Basic timestamp ordering (TO) protocol

Ti issues read(X):

• If TS(Ti) < WTS(X): a younger transaction already overwrote X; Ti needs an older value → abort Ti (roll back, restart with a new timestamp).
• Otherwise: execute; RTS(X) = max(RTS(X), TS(Ti)).

Ti issues write(X):

• If TS(Ti) < RTS(X): a younger transaction already read X; Ti's write is too late → abort Ti.
• Else if TS(Ti) < WTS(X): a younger transaction already wrote X → abort Ti (basic TO).
• Otherwise: execute; WTS(X) = TS(Ti).

Thomas write rule

Modify the second write check: if TS(Ti) < WTS(X) (and TS(Ti) ≥ RTS(X)), ignore the write instead of aborting. The write is obsolete: a younger transaction has already written a newer value that nobody older has read.

Properties

Some schedules are allowed by 2PL but not TO, and vice versa.

Worked trace

TS(T1) = 10, TS(T2) = 20. Initially RTS = WTS = 0 for A and B.

T1 aborts (the lost-update pattern is refused).

4 · Visual

TS order:   older (small TS) ............................ younger (large TS)

read(X) by Ti :  TS(Ti) < WTS(X)  -> abort (value already overwritten by younger)
write(X) by Ti:  TS(Ti) < RTS(X)  -> abort (younger already read the old value)
                 TS(Ti) < WTS(X)  -> abort      (Thomas: ignore the write)
otherwise: do it and update RTS / WTS

5 · Worked Examples

Example 1 Easy

TS(T1) = 5. RTS(X) = 3, WTS(X) = 7. T1 issues read(X). Result?

Solution

5 < WTS 7 → abort T1.

Example 2 Medium

TS(T1) = 5. RTS(X) = 3, WTS(X) = 7. T1 issues write(X). Result under basic TO and under the Thomas write rule?

Solution

5 ≥ RTS 3, but 5 < WTS 7. Basic TO: abort. Thomas: ignore the write and continue.

Example 3 GATE

TS(T1) = 1, TS(T2) = 2, TS(T3) = 3. Schedule R1(A) W3(A) R2(A) W1(B). Under basic TO, which operations succeed?

Solution

R1(A): ok, RTS(A) = 1. W3(A): 3 ≥ RTS 1, 3 ≥ WTS 0 → ok, WTS(A) = 3. R2(A): 2 < WTS(A) = 3 → abort T2. W1(B): ok. So R1(A), W3(A), W1(B) succeed; T2 aborts.

8 · Connect the Dots

Chapter 6.6 controlled concurrency with locks; this lesson did it with timestamps. Last lesson of the phase: three brief topics: locking at several granularities, optimistic validation, and log-based recovery.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1 · MCQ · 1 mark(s) — Read rule

Under basic TO, Ti's read(X) is rejected when:

1. (A) TS(Ti) < RTS(X)
2. (B) TS(Ti) < WTS(X)
3. (C) TS(Ti) > WTS(X)
4. (D) RTS(X) = 0

Q2 · MCQ · 2 mark(s) — Thomas

TS(T1) = 4. RTS(X) = 2, WTS(X) = 6. T1 issues write(X). With the Thomas write rule:

1. (A) T1 aborts
2. (B) the write is ignored
3. (C) T1 waits
4. (D) the write is executed and WTS(X) = 4

Q3 · MSQ · 2 mark(s) — Properties

Which are true of basic timestamp ordering?

1. (A) It guarantees conflict serializability.
2. (B) It guarantees recoverable schedules.
3. (C) It never causes deadlock.
4. (D) A transaction may starve.

Q4 · NAT · 2 mark(s) — Trace

TS(T1) = 1, TS(T2) = 2. Under basic TO, schedule R2(A) W1(A) R1(B) W2(B). How many transactions abort?

Numerical answer: ________

Q5 · MCQ · 2 mark(s) — Trace

TS(T1) = 10, TS(T2) = 20. Schedule W2(A) R1(A). Under basic TO:

1. (A) both succeed
2. (B) T1 aborts at R1(A)
3. (C) T2 aborts at W2(A)
4. (D) R1(A) is ignored

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

timestamp ordering (TO)TS(Ti)read timestamp RTS(X)write timestamp WTS(X)TO read and write rulesThomas write ruleobsolete write