Logical Time: Lamport & Vector Clocks

Ordering events without a shared clock

In a distributed system you cannot trust wall clocks to order events, and there is no shared clock at all. Yet you constantly need to answer "did A happen before B, or were they concurrent?" Logical clocks answer that using only message passing, via Lamport's happens-before relation (written A → B):

• If A and B are on the same node and A came first, then A → B.
• If A is a send and B is the matching receive, then A → B.
• Transitivity: if A → B and B → C then A → C.
• If neither A → B nor B → A, the events are concurrent, written A ∥ B. Concurrency is the interesting case: it is where two clients may have independently updated the same thing.

Lamport clocks

Each node keeps an integer counter. Increment it on every local event; stamp outgoing messages; on receive, set your counter to max(local, received) + 1. The guarantee: if A → B then L(A) < L(B). This gives a total order (break ties by node id) that never contradicts causality: enough to agree on a single order for a replicated log.

The catch, and the single most-probed point here: the implication only goes one way. L(A) < L(B) does not imply A → B. Two concurrent events on different nodes can have any Lamport values, so a smaller timestamp tells you nothing about causation. Lamport clocks cannot detect concurrency. They can order everything; they cannot tell you which orderings were forced by causality and which were arbitrary.

Vector clocks

Each node keeps a vector with one counter per node. On a local event, increment your own slot. On send, attach your whole vector. On receive, take the element-wise max, then increment your own slot. Compare two vectors:

• V(A) < V(B) (every element ≤, at least one <) means A → B.
• V(B) < V(A) means B → A.
• Neither dominates means A ∥ B, concurrent, and if they touched the same key, a conflict.

node A: [1,0,0] --send--> node B receives, takes max, bumps self -> [1,1,0]
meanwhile node C, no contact: [0,0,1]
compare [1,1,0] vs [0,0,1]: A-slot 1>0 but C-slot 0<1 -> neither dominates -> CONCURRENT

That detection is why Dynamo and Riak use vector clocks (technically version vectors, one entry per replica) to surface siblings: when a read finds two concurrent versions, it returns both to the application (or a merge function / LWW / CRDT) rather than silently picking one and losing a write.

Interview nuance, the costs. Vector clocks are O(N) in the number of participants. Worse, in a system with many transient actors (mobile clients writing directly), the vector grows without bound because each new writer adds a slot, and you cannot easily garbage-collect entries for actors that may still return. This GC / unbounded-growth problem is why Dynamo keys version vectors on the small fixed set of storage nodes rather than per-client, and why pruning old entries risks false-concurrent readings.

Recap: Lamport clocks give a causality-respecting total order but cannot detect concurrency; vector/version clocks do detect concurrency and let leaderless stores surface conflict siblings, at O(N) size and a real garbage-collection problem when actors churn.