Lamport Clocks and Vector Clocks: Ordering Events Without a Shared Clock

The idea: order from messages, not from clocks

Machines in a distributed system have no shared clock, and their own clocks drift. So "which happened first?" cannot be answered by comparing wall-clock times. Leslie Lamport's answer (1978) is to use only what the processes can see: the order of events on each process, and the fact that a message is received after it was sent. A logical clock is a counter that follows these two rules, so that timestamps respect cause and effect.

On the canvas	Meaning
P1, P2, P3 and their lines	three processes; time runs left to right (down on a phone); the clocks under each name are its current values
dot with a letter	one event: grey local, blue send, green receive; L= is its Lamport time, [P1,P2,P3] its vector
arrow	a message, from its send event to its receive event
orange / yellow	the two events being compared / the causal past of the later one
total order	all events sorted by (L, process id)

Happened-before

Event e happened before f (written e → f) when e comes earlier on the same process, or e sends a message that f receives, or there is a chain of such steps from e to f. Only then can e have influenced f. When neither e → f nor f → e, the two are concurrent (e ∥ f): no information could pass between them, whatever the wall clocks said. Compare on the page shows this directly: it colours the causal past of the later event yellow (Demo 3: a happened-before chain).

The Lamport clock

Each process keeps one integer L, starting at 0:

• before each event (local or send), L = L + 1; a message carries the sender's L;
• on a receive, L = max(L, Lmsg) + 1.

The max is the point: a receiver whose clock is behind jumps ahead of the sender, so the receive always gets a larger number than the send (Demo 2: a receive takes the max: P3 is at 3 when P1's message with L=1 arrives, so it goes to 4; P2 jumps from 0 to 6). By induction along any chain, e → f implies L(e) < L(f): the clock condition.

Why Lamport cannot see concurrency

The converse is false. In Demo 5: Lamport order but concurrent, P1 has three local events a, b, c (L = 1, 2, 3) and P3 one event d (L = 1). L(d) < L(c), yet no message connects them: d did not happen before c. From two Lamport timestamps you can only conclude "f did not happen before e" when L(e) < L(f); whether e → f or e ∥ f stays open. Equal values do say something: L(e) = L(f) means concurrent (Demo 4: concurrent events).

Vector clocks

A vector clock (Fidge and Mattern, 1988) keeps one counter per process. Entry V[j] on process i means "I have seen the first V[j] events of P_j".

• before each event, process i adds 1 to its own entry V[i]; a message carries the whole vector;
• on a receive, take the entry-wise max of the two vectors, then add 1 to the own entry.

Two vectors compare entry by entry:

Vectors	Example	Meaning
V(e) ≤ V(f) in every entry, and not equal	[1,0,0] vs [2,2,2]	e → f
V(e) ≥ V(f) in every entry, and not equal	[2,1,0] vs [2,0,0]	f → e
some entries larger, some smaller	[0,0,1] vs [3,0,0]	e ∥ f (concurrent)

Unlike Lamport time this works both ways: e → f exactly when V(e) < V(f). The price is size: n counters per message and per stored version instead of one.

Detecting a conflict

Replicated stores use this to find conflicting writes. In Demo 6: vector clocks detect a conflict, P1 writes x=1 ([1,0,0]) and P3 writes x=2 ([0,0,1]), neither having heard of the other, and both are replicated to P2. The vectors are concurrent, so neither write is "newer": a store like Dynamo or Riak keeps both versions as siblings and lets the client merge them on the next read. A store that resolves by last-write-wins on (L, id) or on wall-clock time keeps x=2 and drops x=1 without telling anyone. When one write saw the other (its vector is larger), it simply replaces it.

A total order from Lamport time

Lamport time is still useful. Sorting all events by (L, process id) gives a total order: every pair is ordered, every process computes the same order from the timestamps alone, and it respects every arrow (if e → f then L(e) < L(f)). Concurrent events are ordered arbitrarily, here lower process id first (Demo 7: total order, ties by process id). Lamport used this order for distributed mutual exclusion, and it is the basis of total-order broadcast.

See also Consistency Patterns (causal consistency is happened-before applied to reads), CRDTs (data types that merge concurrent updates instead of keeping siblings), Chandy–Lamport snapshots (a consistent cut respects happened-before), Quorum reads and writes and Raft, whose terms are a logical clock too.

Wall clocks can be kept close with NTP, which measures a clock's offset from four timestamps, but never exactly: an uneven network path leaves an error no message exchange can see. That is why event order needs logical clocks like these.

What the page leaves out

Messages here are delivered at once, so no other event happens while one is in flight and messages never cross or arrive out of order; real networks delay, reorder and lose them, and the rules work unchanged. The page also skips: version vectors (one entry per replica rather than per process, as Dynamo and Riak use), dotted version vectors and the pruning of old entries, matrix clocks, hybrid logical clocks (physical time plus a Lamport counter, used by CockroachDB and MongoDB), Google Spanner's TrueTime, and the cost of vector clocks as the number of processes grows.

References

Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System (1978)

Friedemann Mattern: Virtual Time and Global States of Distributed Systems (1988)

DeCandia et al.: Dynamo, Amazon's Highly Available Key-value Store (2007), vector clocks and siblings