Timestamp-Based Concurrency Control

Locking discovers a serialization order at run time, through the order of lock points. Timestamp ordering fixes the order in advance: every transaction gets a unique timestamp when it starts, and the system allows a conflicting operation only if it respects timestamp order. A transaction that would violate the order is rolled back and restarted with a new timestamp. No transaction ever waits, so there are no deadlocks.

Timestamps are also used with locking, to decide who waits and who is rolled back in the wait-die and wound-wait deadlock-prevention schemes. The tasks are to trace the timestamp-ordering rules on a schedule, to apply the Thomas write rule, and to say what happens under wait-die and wound-wait.

Timestamps. $TS(T_i)$ is assigned when $T_i$ starts, from a system clock or a counter; if $T_i$ starts before $T_j$, then $TS(T_i) < TS(T_j)$. A smaller timestamp means an older transaction.

Item timestamps. For each item $X$:

Both start at 0.

Basic timestamp-ordering (TO) protocol.

A rolled-back transaction restarts with a new, larger timestamp.

Thomas write rule. Change only the second write test: if $TS(T_i) < \text{W-TS}(X)$ (and the read test passed), ignore the write instead of rolling back. The write is obsolete: a younger transaction has already written $X$, and nobody between them read the value $T_i$ would write.

Deadlock prevention with timestamps (used with locking). When $T_i$ requests an item held by $T_j$:

In wait-die only older transactions wait for younger ones; in wound-wait only younger transactions wait for older ones. Waits therefore always point in one direction of age, so no cycle can form. A rolled-back transaction keeps its original timestamp, so it eventually becomes the oldest and cannot starve.

For each operation in order: look up the item's $\text{R-TS}$ and $\text{W-TS}$, apply the tests, and either update the timestamps or roll back the transaction. A table with one row per operation and columns for the test, the outcome and the new timestamps keeps the trace honest.

Why TO gives conflict serializability. Every executed pair of conflicting operations is ordered by timestamp: a read is allowed only after writes from older transactions, a write only after reads and writes from older transactions. So every edge $T_i \to T_j$ of the precedence graph has $TS(T_i) < TS(T_j)$, the graph is acyclic, and the schedule is conflict equivalent to the serial schedule in timestamp order.

What the Thomas write rule guarantees. The rule in effect deletes each obsolete write from the transaction that issued it. The operations that are actually executed pass every basic TO test, so they are conflict equivalent to the serial schedule in timestamp order. Read with the ignored writes left in place, the submitted schedule need not be conflict serializable: Example 4 is accepted, is not conflict serializable, and is view serializable. Do not stretch this to "every schedule the rule accepts is view serializable as written": a transaction that reads an item after an ignored write by another transaction can make the as-written schedule fail the view test, although the executed schedule is still serializable. A read after its own obsolete ignored write instead fails the timestamp read check and aborts.

Deadlock and starvation. Basic TO never makes a transaction wait, so it is deadlock-free. A long transaction can, however, be rolled back again and again (each restart gets a new, larger timestamp, which can be invalidated again), so starvation is possible.

Recoverability. Basic TO says nothing about commits, so it can produce schedules that are not recoverable or not cascadeless. Strict TO delays a read or write of $X$ until the other transaction that last wrote $X$ has committed or aborted.

TO and 2PL accept different schedules. Neither set contains the other: TO forces the timestamp order, 2PL forces the lock-point order and the no-acquire-after-release rule (Examples 5 and 6).

Example 1: a full trace. $TS(T_1) = 10$, $TS(T_2) = 20$, $TS(T_3) = 30$; $S = R_1(A)\, R_2(B)\, W_2(A)\, R_3(B)\, W_3(A)\, W_1(B)$.

$T_1$ is rolled back at its last operation: younger $T_2$ and $T_3$ have already read the old $B$.

Example 2: a read rejected. $TS(T_1) = 5$, $TS(T_2) = 10$, $S = W_2(A)\, R_1(A)$. After $W_2(A)$, $\text{W-TS}(A) = 10$; $R_1(A)$ has $5 < 10$, so $T_1$ is rolled back: it would read a value from its future.

Example 3: the read test also beats the Thomas rule. $TS(T_1) = 5$, $TS(T_2) = 10$, $S = R_1(A)\, R_2(A)\, W_2(A)\, W_1(A)$. At $W_1(A)$, $\text{R-TS}(A) = 10 > 5$, so $T_1$ is rolled back under both basic TO and the Thomas write rule: the Thomas rule relaxes only the write-write test.

Example 4: the Thomas write rule. $TS(T_1) = 1$, $TS(T_2) = 2$, $TS(T_3) = 3$; $S = R_1(A)\, W_2(A)\, W_1(A)\, W_3(A)$, the view-serializable but not conflict-serializable schedule from Schedules and Serializability. At $W_1(A)$: $\text{R-TS}(A) = 1 \le 1$ passes, but $\text{W-TS}(A) = 2 > 1$. Basic TO rolls $T_1$ back; the Thomas rule ignores $W_1(A)$, and the schedule completes, view equivalent to $T_1 T_2 T_3$.

Example 5: TO accepts a schedule 2PL cannot produce. $S = R_1(A)\, W_2(A)\, R_3(B)\, W_1(B)$ is not producible by 2PL (lock note, Example 3). With $TS(T_3) < TS(T_1) < TS(T_2)$ every test passes, and $S$ runs under basic TO, equivalent to $T_3 T_1 T_2$.

Example 6: 2PL accepts a schedule TO rejects. $S = R_2(A)\, W_1(A)$ with $TS(T_1) < TS(T_2)$. 2PL produces it ($T_2$ releases its S lock, then $T_1$ takes X), serial order $T_2 T_1$. Basic TO rolls back $T_1$ at $W_1(A)$, because $TS(T_1) < \text{R-TS}(A) = TS(T_2)$.

Example 7: wait-die and wound-wait (Figure 1). $TS(T_1) = 5$ (older), $TS(T_2) = 10$.

With the deadlock of the lock note ($T_1$ holds $A$ and wants $B$, $T_2$ holds $B$ and wants $A$), wait-die lets $T_1$ wait and kills $T_2$ when it requests $A$; wound-wait rolls back $T_2$ as soon as $T_1$ requests $B$. Either way no cycle forms.

Example 8: the Thomas rule can change who is rolled back. $TS(T_1) = 10$, $TS(T_2) = 20$, $TS(T_3) = 30$; $S = R_1(A)\, W_3(A)\, W_2(A)\, R_2(B)\, W_1(B)\, W_3(B)$. Convention: a rolled-back transaction's remaining operations are dropped from the trace, and it is not restarted within it.

Basic TO rolls back $T_2$; the Thomas rule saves $T_2$ by ignoring its obsolete write, but $T_2$ then reads $B$, and that read is what later forces $T_1$ back. Both runs lose exactly one transaction. The Thomas rule never rejects a write that basic TO accepts, but it does not promise fewer rollbacks overall, because the transactions it saves keep running and change the timestamps.

Common misconceptions.