Logical clocks: ordering without a shared clock

Two servers log events. Server A writes balance = 50 at 10:00:00.120, and server B writes balance = 80 at 10:00:00.115. Which write came last, and so wins?

The timestamps say A's. But each timestamp comes from that machine's own clock, and clocks drift. Even with NTP keeping them in step, two machines can disagree by milliseconds across a data centre and by far more across the internet, and a clock can jump backwards when it is corrected. If B's clock runs 10 ms slow, B's write really came second. Physical time can't tell you.

In 1978 Leslie Lamport pointed out that you often don't need the real time at all. What matters is cause and effect: could one event have influenced the other? That can be tracked with plain counters, called logical clocks.

process

One machine or thread with its own sequence of events. Each gets a horizontal line on the diagram, with time running left to right.

event

Something a process does: a local step, sending a message, or receiving one. Drawn as a dot, named by process and position (b2 is B's second event).

happened before (→)

e → f if e comes before f on the same process, or e is the sending of a message that f receives, or there is a chain of these from e to f.

concurrent

Neither e → f nor f → e: no chain of messages links them, so neither could have affected the other, whatever the wall clocks say.

Lamport clock

One counter per process. Tick it before every event; a message carries the sender's count, and a receiver first jumps to the larger of its own count and the message's.

vector clock

One counter for every process, kept by every process. It records how many events of each process are in an event's past.

Three processes, two messages: A tells B something, then B tells C. Step through and watch each event get its stamp. Local events and sends tick the clock by one. A receive first takes the larger of the local clock and the stamp the message carries, then ticks.

The rule only works in one direction. Lamport clocks never put an effect before its cause, but a smaller timestamp does not mean an event came first.

Sorting by (timestamp, process name) gives a total order that never contradicts →. Every process can work it out from the stamps alone, so they all agree on one order of events. Lamport used it to build mutual exclusion without a central lock server, and systems use it to agree on an order of writes. Between concurrent events, though, the order it picks is arbitrary.

Before each receive, say what stamp it gets. At the end, say whether one event happened before another or the two are concurrent.

A Lamport timestamp is one number, so it can't tell "happened before" from "concurrent": the pair (1, 4) above looks just like a real cause and effect. Vector clocks (Fidge and Mattern, independently, in 1988) fix this by keeping one counter per process:

• A local event or a send: add one to your own entry. A message carries the sender's whole vector.
• A receive: take the larger of each entry, yours or the message's, then add one to your own entry.

Entry $i$ of an event's vector counts the events of process $i$ in its past, including itself if it is on process $i$. To compare, $V(e) < V(f)$ means every entry of $V(e)$ is $\le$ the matching entry of $V(f)$, and at least one is smaller. Then e → f exactly when V(e) < V(f), and two events are concurrent exactly when neither vector is smaller.

The price is size: a vector has one entry per process, so it grows with the cluster. Amazon's Dynamo stored vector clocks with each value so that, after a network split, it could tell an update that replaced another from two concurrent updates that conflict and must both be kept. Riak's version vectors do the same job, with one entry per replica rather than per client.

• Machines' clocks drift, so wall-clock times can't order events across machines. Happened-before (→) is what counts: same-process order, send before receive, and chains of these.
• Lamport clocks: tick before every event; on a receive, $L \leftarrow \max(L, t_m) + 1$. Then e → f ⇒ L(e) < L(f), but not the converse.
• Ties broken by process give a total order everyone agrees on, consistent with →. It is used for mutual exclusion and for ordering writes.
• Vector clocks: one entry per process; tick your own entry, merge with an elementwise max on a receive (then tick). e → f ⇔ V(e) < V(f), and incomparable vectors mean concurrent.
• Concurrent means causally unrelated, not simultaneous. Vector clocks and version vectors (Dynamo, Riak) use this to spot conflicting writes, at the cost of one entry per process or replica.