Vector Clocks

Order events across processes with no shared clock — and tell true causality apart from mere coincidence.

In a distributed system there is no single trustworthy clock, so you can't order events by timestamp. Vector clocks order them by *causality* instead — by whether one event could actually have influenced another. Each process keeps a vector of counters, one slot per process, that records how many events it knows about from everyone.

The three update rules

1Every process i keeps a vector V of length n (one entry per process), starting all zeros.
2Local event: process i increments its own entry, V[i] += 1.
3Send: increment V[i], then attach a copy of V to the message.
4Receive: take the element-wise max of the local vector and the message's vector, then increment V[i].

The element-wise max on receive is the key move: the receiver inherits everything the sender already knew, so its vector now reflects the full causal history flowing into that point.

Reading the vectors

Compare two event vectors V and W entry by entry. V happened-before W when every entry of V is ≤ the matching entry of W and at least one is strictly less. If neither happened-before the other, the events are concurrent — independent, with no cause-and-effect between them.

P1 local e1            -> [1,0,0]
P2 local e2            -> [0,1,0]
P1 sends msg (send)    -> [2,0,0]   attaches [2,0,0]
P2 receives msg        -> max([0,1,0],[2,0,0]) = [2,1,0], +1 own = [2,2,0]

e1 [1,0,0] vs recv [2,2,0]: every entry <=, one strictly < -> e1 happened-before
e2 [0,1,0] vs send [2,0,0]: neither <= the other      -> concurrent

Why not a single counter (Lamport clock)?

A scalar Lamport clock guarantees that if A caused B then A's number is smaller — but a smaller number does NOT prove causality, so it can't detect concurrency. A vector clock captures the full picture: it tells you exactly when two events are concurrent versus causally ordered.

Cost grows with the cluster

Each vector has one entry per process, so every message carries O(n) numbers for n processes. In large or churning systems that overhead — and tracking which processes exist — is the practical limit on naive vector clocks.

OperationTimeSpace

Per message / event · n = number of processesO(n)O(n)

Compare two events · element-wise comparisonO(n)O(1)

Check yourself

Two events have vectors [2,1,0] and [1,3,0]. What is their relationship?