Timestamp Ordering

Timestamp ordering enforces serializability *without locks*. Each transaction gets a timestamp the moment it starts — a smaller number means older. The database then guarantees the schedule is equivalent to running the transactions in timestamp order. Because it aborts rather than waits, it can never deadlock.

What each item remembers

Every data item X carries two stamps: R-TS(X), the timestamp of the *youngest* transaction that has read it, and W-TS(X), the youngest that has written it. An operation arriving 'too late' relative to these is rejected.

The basic ordering rules

1. 1Read(X) by transaction T: if TS(T) < W-TS(X), a younger transaction already wrote a value T should have seen — abort and restart T. Otherwise read, and set R-TS(X) = max(R-TS(X), TS(T)).
2. 2Write(X) by T: if TS(T) < R-TS(X), a younger transaction already read the old value — abort T. If TS(T) < W-TS(X), a younger write already exists — abort under the basic rule. Otherwise write, and set W-TS(X) = TS(T).

Thomas's Write Rule — a smarter write

The basic write rule aborts a write whenever TS(T) < W-TS(X). But Thomas's write rule notices that such a write is simply *obsolete*: a younger transaction has already written a newer value to X, so this old write would immediately be overwritten anyway. Instead of aborting T, it just ignores (skips) the write and lets T continue.

Write(X) by T:
  if TS(T) < R-TS(X):            abort T        -- a younger txn already read X
  else if TS(T) < W-TS(X):       ignore write   -- Thomas's rule: obsolete write, skip it
  else:                          do write; W-TS(X) = TS(T)

Worked example. Suppose W-TS(X) = 12 (a transaction stamped 12 already wrote X). Now an older transaction stamped 5 tries to write X. Since 5 < 12 and no younger transaction has *read* X, the basic rule would needlessly abort transaction 5. Thomas's write rule instead discards transaction 5's write and lets it proceed — the newer value from transaction 12 rightly wins.