Timestamp-Ordering Protocol

A schedule of concurrent transactions is conflict-serializable if it is equivalent to some serial execution of those same transactions, as captured by Conflict Serializability and its precedence-graph test. Two-phase locking achieves this indirectly, by preventing cycles in the conflict graph through blocking. The timestamp-ordering protocol takes a more direct route: it decides in advance which serial order the schedule must be equivalent to — the order of the transactions' timestamps — and then enforces every single conflicting operation to occur in a way consistent with that predetermined order. Formally, when a transaction `T` enters the system, the scheduler assigns it a unique timestamp `TS(T)`, drawn from a monotonically increasing source (a logical or system clock, or a counter). If `TS(Ti) < TS(Tj)`, the protocol guarantees the produced schedule behaves as if `Ti` executed entirely before `Tj` with respect to any data item they both access. To track this, every data item `Q` carries two auxiliary fields:

• W-timestamp(Q): the largest timestamp of any transaction that successfully executed `write(Q)`.
• R-timestamp(Q): the largest timestamp of any transaction that successfully executed `read(Q)`.

These two fields are the entire state the protocol needs — no lock tables, no wait queues. Whenever a transaction attempts to read or write `Q`, the scheduler compares `TS(T)` against the stored timestamps to check whether this operation is consistent with `T` acting at its assigned logical time. If a younger transaction has already read or written `Q` before an older transaction `T` gets around to it, then honoring `T`'s operation would violate the serial order — so `T` is aborted and restarted with a brand-new, larger timestamp, effectively pushing it later in the serial order it must respect.

The protocol's rules are split cleanly into a read rule and a write rule, each checking whether the requesting transaction is "too late" relative to some other transaction that has already touched the item.

Read rule. Transaction `T` issues `read(Q)`.

• If `TS(T) < W-timestamp(Q)`: some transaction that is younger than T in serial order has already written a newer value of `Q`. Letting `T` read now would mean `T` reads a value from "the future" relative to its assigned position — impossible in any equivalent serial schedule. Reject: abort `T`, restart with a new timestamp.
• Otherwise: the read is consistent with serial order. Execute `read(Q)`, and set `R-timestamp(Q) = max(R-timestamp(Q), TS(T))`.

Write rule. Transaction `T` issues `write(Q)`.

• If `TS(T) < R-timestamp(Q)`: a younger transaction has already read `Q`, presumably reading an earlier value that existed before `T`'s write. Allowing `T`'s write now would retroactively change what that younger reader should have seen. Reject: abort `T`, restart with a new timestamp.
• Else if `TS(T) < W-timestamp(Q)`: a younger transaction has already written a newer value of `Q`. Writing now would overwrite that newer value with an obsolete one, violating serial order. Under the basic protocol, reject: abort and restart. (The Thomas Write Rule, discussed below, instead simply ignores this write.)
• Otherwise: the write is consistent with serial order. Execute `write(Q)`, and set `W-timestamp(Q) = TS(T)`.

Every abort restarts the transaction with a completely fresh timestamp — never reusing the old one — since the old timestamp is precisely what caused it to be "too late." ```pseudocode // Global structures for each data item Q: W_timestamp[Q] = 0 // or timestamp of item's initial write R_timestamp[Q] = 0 function START_TRANSACTION(): T.timestamp = next_unique_timestamp() // strictly increasing return T function READ(T, Q): if T.timestamp < W_timestamp[Q]: ABORT_AND_RESTART(T) // too late: value already overwritten else: value = disk_read(Q) R_timestamp[Q] = max(R_timestamp[Q], T.timestamp) return value function WRITE(T, Q, new_value): if T.timestamp < R_timestamp[Q]: ABORT_AND_RESTART(T) // too late: a younger reader already saw an earlier value else if T.timestamp < W_timestamp[Q]: // Basic protocol: ABORT_AND_RESTART(T) // too late: a younger writer already wrote a newer value // Thomas Write Rule (alternative): // IGNORE the write (do not perform it, do not update W_timestamp[Q]) // and let T continue as if the write succeeded. else: disk_write(Q, new_value) W_timestamp[Q] = T.timestamp function ABORT_AND_RESTART(T): rollback_effects(T) T.timestamp = next_unique_timestamp() // new, strictly larger timestamp resubmit(T) ``` The following diagram shows the state machine each `read`/`write` request goes through, and how a single data item's `R-timestamp`/`W-timestamp` pair mediates every decision.

Time complexity. Each `read` or `write` operation performs a constant number of comparisons against `R-timestamp(Q)` and `W-timestamp(Q)`, plus (on success) a constant-time update of one field. So the per-operation overhead is `O(1)`, matching the cost of a lock-table lookup in two-phase locking but without any wait. If a transaction is aborted and restarted, its entire work is redone; the amortized cost depends on the abort rate, which grows with contention — in the worst case (adversarial timestamp assignment or extremely hot data items), a transaction could be repeatedly aborted, giving no worst-case upper bound on total restarts without an added rule such as "always assign a strictly increasing timestamp so eventual success is guaranteed once the transaction becomes the oldest active one touching `Q`." In practice, contention is moderate and the expected number of restarts per transaction is small.

Space complexity. The protocol needs exactly two extra timestamp fields per data item — `O(1)` per item, `O(n)` total for `n` items — dramatically less than a full lock table, and no wait-for graph is needed at all (compare to deadlock detection under 2PL).

Correctness argument. The claim is: any schedule produced by the timestamp-ordering protocol is conflict-equivalent to the serial schedule in which transactions appear in timestamp order. *Proof sketch. Consider any two transactions `Ti` and `Tj` with `TS(Ti) < TS(Tj)` that both access a common data item `Q`, with at least one operation being a write (a conflicting pair, per the definition used in <a class="wiki-link" href="/wiki/cs-db-conflict-serializability" data-track="wiki_article.body.wiki_link">Conflict Serializability</a>). There are three conflict cases: 1. <strong>`Ti` reads `Q`, `Tj` writes `Q`.</strong> The write rule guarantees that when `Tj` writes, `TS(Tj) \ge R\text{-timestamp}(Q)` at that moment — otherwise `Tj` would be aborted. Since `Ti`'s successful read updated `R-timestamp(Q)` to at least `TS(Ti)` before that check could fail against a smaller `TS(Tj)`, and `Tj`'s write only succeeds when it is not smaller than the current `R-timestamp(Q)`, the successful ordering places `Ti`'s read chronologically before `Tj`'s write in execution — matching `Ti \to Tj` in timestamp order. 2. <strong>`Ti` writes `Q`, `Tj` reads `Q`.</strong> The read rule ensures `Tj`'s read is rejected whenever `TS(Tj) < W\text{-timestamp}(Q)`. If `Ti`'s write already succeeded and set `W-timestamp(Q) = TS(Ti)`, then for `Tj`'s subsequent read to succeed we need `TS(Tj) \ge TS(Ti)`, i.e., `Ti \to Tj`, consistent with timestamp order — and the read actually observes `Ti`'s write (or a later one), never a stale value from a transaction younger than `Ti`. 3. <strong>`Ti` writes `Q`, `Tj` writes `Q`.</strong> The basic write rule rejects `Tj`'s write whenever `TS(Tj) < W\text{-timestamp}(Q)`. A successful sequence of writes on `Q`, therefore, has `W-timestamp(Q)` monotonically increasing, so the final stored value reflects the write from the transaction with the largest timestamp among those that actually wrote — exactly the value a serial execution in timestamp order would leave behind. In every conflicting pair, the protocol's accept/reject rules force the effective order of execution on `Q` to agree with the timestamp order* of `Ti` and `Tj`. Since this holds for every conflicting pair across every data item, the precedence graph built over all transactions (the conflict graph used to test Conflict Serializability) can only have edges pointing from smaller to larger timestamps — an inherently acyclic ordering (a linear order can never induce a cycle). By the serializability theorem, an acyclic conflict graph implies the schedule is conflict-serializable, and specifically equivalent to the serial schedule ordered by timestamp. `∎`

Deadlock freedom. Because no transaction ever waits — every conflict is resolved immediately by aborting one side — there is no possibility of a circular wait, hence no deadlocks. This is a structural guarantee, not a probabilistic one.

Honest tradeoffs.

• Starvation is possible: a transaction repeatedly restarted with new timestamps could, in principle, always end up "too late" again if it is unlucky and long-running while short transactions race past it. Practical implementations must sometimes freeze a transaction's timestamp temporarily or give priority boosts to prevent live-lock.
• Cascading aborts: if `Ti` writes a value that `Tj` (with `TS(Tj) > TS(Ti)`) reads, and `Ti` later aborts for unrelated reasons, `Tj` must also abort — the schedule is not guaranteed recoverable without extra buffering (e.g., delaying commit of `Tj` until `Ti` commits).
• More restarts under contention than a well-tuned lock-based scheme, because T/O aborts eagerly the instant an out-of-order access is detected, rather than allowing a transaction to wait for the resource to free up.
• The Thomas Write Rule improves on the basic write rule: if `TS(Ti) < W-timestamp(Q)` but `TS(Ti) \ge R\text{-timestamp}(Q)`, then `Ti`'s write, if performed, would immediately be overwritten (in serial order) by the already-completed younger write — so it is safe to simply skip it rather than abort `Ti`. This preserves correctness (the final database state is identical to what a valid serial schedule would produce) while avoiding an unnecessary abort, strictly increasing concurrency over the basic protocol.

Consider three transactions accessing a single data item `A`, with timestamps assigned at start:

Initial state: `R-timestamp(A) = 0`, `W-timestamp(A) = 0`. Trace of interleaved operations, arriving in this real-time order (not timestamp order — that is the whole point):

Walk through the reasoning at each abort:

• Step 2: T1 (timestamp 10, the "oldest") tries to read `A` after T2 (timestamp 20) has already written it. In the serial order the protocol must simulate, T1 comes before T2 — so T1 should have read `A`'s value before T2 overwrote it. But physically, T2's write already happened. There is no way to retroactively give T1 an "earlier" view, so T1 must be aborted and pushed to a later logical position (a new timestamp, 40, making it now "younger" than both T2 and T3).
• Step 3: T3 (timestamp 30) writes after T2 (timestamp 20) wrote — this is fine since `30 > 20`, consistent with T2 acting before T3.
• Step 5: T2 (original timestamp 20) tries to read `A`, but `W-timestamp(A)` is now 30 (set by T3, whose logical position is after T2). Reading now would mean T2 reads a value that (in serial-order terms) belongs to a later transaction — a violation. T2 must abort and restart at 50.

At the end, the surviving execution order (by final, possibly-restarted timestamps) is: T2 (write, 20) → T3 (write, 30) → T1′ (read, 40) → T2′ (pending). This matches a legitimate serial order — the protocol never let an inconsistency slip through; it paid for that guarantee with two restarts.

The timestamp-ordering protocol emerged from the broader effort in the 1970s and 1980s to formalize concurrency control theoretically, connecting operating-systems-style scheduling with the emerging theory of database transactions and serializability.

Timestamp-ordering's core insight — resolve conflicts by comparing logical time instead of acquiring locks — persists throughout modern systems, even where the exact basic protocol described above is rarely deployed unmodified:

• Distributed databases (e.g., early systems like SDD-1, and conceptually in Google's Spanner-style designs) use timestamps, sometimes tied to physical or hybrid logical clocks, to order transactions across machines without a centralized lock manager, since coordinating locks across a network is far more expensive than comparing timestamps.
• Optimistic and multiversion concurrency control in systems like PostgreSQL, Oracle, and MySQL's InnoDB (under snapshot isolation) generalize the timestamp-ordering idea: instead of aborting a transaction whenever it is "too late," these systems keep multiple versions of each data item so that older transactions can still read a version consistent with their logical time — a direct evolution toward <a class="wiki-link" href="/wiki/cs-db-multiversion-concurrency-control" data-track="wiki_article.body.wiki_link">Multiversion Concurrency Control</a>.
• Real-time and embedded databases, where predictable, non-blocking behavior matters more than raw throughput, favor timestamp-based schemes precisely because they are deadlock-free and never make a transaction wait indefinitely for a lock.
• Version vectors and logical clocks in distributed systems (e.g., Lamport clocks, vector clocks) borrow the same conceptual machinery — comparing timestamps to establish a consistent partial or total order of events — that underlies this protocol's read/write rules.

Ask the tutor: How does the Thomas Write Rule change the correctness proof compared to the basic protocol?