AlgoPlus//structures / timestamp-ordering

Timestamp Ordering

A lock-free protocol: timestamps decide order, and out-of-order accesses abort.

R-TS(X)

0

W-TS(X)

0

Aborted

—

Legend

Allowed

Abort

T1 / T2

AI Tutor Workspace

—

In a nutshell

Instead of locks, this method stamps each transaction with a start-time number and makes every conflicting access obey that order. Each data item remembers when it was last read and last written; an operation that would break timestamp order is rejected, aborting and restarting that transaction with a fresh stamp. The result is serializable and can never deadlock.

Ready

Press play to begin the cinematic walkthrough.

Each transaction gets a timestamp; items track read/write timestamps. A read fails if a younger transaction already wrote; a write fails if a younger one read or wrote. Offending transactions abort and restart — lock-free and deadlock-free.

Key terms

Go deeper in the lesson

Read the full theory, intuition & complexity for Timestamp Ordering.