Short note: Timestamp ordering in CC

Timestamp ordering gives each transaction a unique timestamp when it starts (a Lamport clock or a global timestamp from server id and local clock in a distributed system). Conflicting operations are executed in timestamp order, so the result is equivalent to running transactions serially in timestamp order. No locks are used, so no deadlock.

Each object keeps a write timestamp (of the last committed write) and read timestamps (of transactions that read it). For a transaction T with timestamp Tc:

• Write rule: T's write is allowed only if Tc ≥ the maximum read timestamp of the object and Tc > the write timestamp of the committed version. Otherwise T is aborted (it would invalidate a later read).
• Read rule: T's read is allowed if Tc > the write timestamp of the committed version; if a tentative version from an earlier transaction exists, T waits until it commits or aborts. If Tc is smaller than the write timestamp, T is too late and is aborted.

An aborted transaction restarts with a new, later timestamp. Timestamp ordering is deadlock-free, but it causes restarts; keeping multiple versions of objects reduces the number of aborts.