Distributed systems
Vector clocks and causality: interview questions and how to answer them
Vector clocks track causality rather than time: they can tell you that one version descends from another, or that two versions are concurrent and must be merged — something wall-clock timestamps cannot do.
Written and reviewed by Sahil Srivastav
What it actually is
A vector clock is a map from node identifier to counter, carried alongside a value. A node increments its own entry when it writes, and merging two clocks takes the element-wise maximum. Comparing two clocks then answers a question about causality: A happened before B if every entry of A is less than or equal to B’s and at least one is strictly less; if neither dominates the other, the versions are concurrent.
That last case is the point. Two clients that both read version {a:1} and both write produce {a:1,b:1} and {a:1,c:1} — neither descends from the other, so the system knows a genuine conflict occurred rather than guessing. A wall-clock timestamp cannot represent this: it always yields an order, even when there is no causal relationship, so it silently picks a winner.
A Lamport clock is the cheaper cousin: one counter, incremented on every local event and advanced to `max(local, received) + 1` on receipt. It guarantees that if A happened before B then L(A) < L(B), but not the converse — so it gives a consistent total order, not conflict detection. Vector clocks cost O(nodes) space and give the detection.
Why it matters in production
Because last-write-wins is the default in a great many systems and it quietly deletes data. Two concurrent updates to the same shopping cart, profile, or document with LWW leave one of them gone, and the loser is chosen by whichever machine had the later clock reading — with clock skew, that may be the update that happened first. Teams discover this as “the user says their change disappeared”, which is nearly impossible to reproduce.
Causality is also the foundation of the session guarantees users actually notice. Read-your-writes, monotonic reads, and “the reply appears after the comment it replies to” are all causal properties, and enforcing them requires tracking dependencies rather than timestamps. A feed that shows a reply above its parent is a causality bug, not a sorting bug.
And it explains why multi-region active-active is hard in a specific, describable way. Once two regions accept writes for the same key, you own a merge function, and choosing between LWW, siblings, and a CRDT is the design decision the architecture rests on.
How it works
Happens-before is a partial order
Lamport’s relation: an event happens before another if it precedes it in the same process, or it is a message send whose receive is the other, plus transitivity. Events not related either way are concurrent. The crucial consequence is that a distributed system has no natural total order of events — imposing one is a choice, and choosing badly is how conflicts get hidden rather than resolved.
Comparison rules
Given clocks V and W: V < W if every V[i] <= W[i] and some V[i] < W[i]; symmetrically for W < V; otherwise concurrent. A replica receiving a write whose clock dominates its own simply overwrites — that is a normal causal update. A replica receiving a concurrent clock must keep both versions or apply a merge, because discarding either loses a write nobody has seen.
Siblings and the application’s merge
Dynamo-style stores return all concurrent versions to the client as siblings. The application resolves them with domain knowledge — union the cart items, take the higher tier, ask the user. This is more work but it is honest: the conflict is surfaced where the semantics live. The failure mode to watch is sibling explosion, where clients read and write without resolving and the version set grows.
Why clocks need pruning
A vector clock grows an entry per writer, so a key written by thousands of clients accumulates a large clock. Practical systems bound it: keyed by server rather than client, capped with a timestamp-ordered eviction of the oldest entries, or replaced with dotted version vectors, which fix the sibling-growth anomaly that naive vector clocks exhibit when clients read-modify-write without carrying a context.
Hybrid logical clocks
HLCs combine a physical timestamp with a logical counter: the physical part keeps values close to real time so they are human-readable and comparable across the system, and the logical part guarantees the happens-before property even when the physical clocks disagree. This is what CockroachDB and similar systems use to get timestamps that are both meaningful and causally sound, without requiring atomic clocks.
Implementing it
Decide the conflict policy per field, not per system. A profile’s `display_name` may be fine with last-write-wins; a cart’s item set needs a union; a counter needs a CRDT or a per-replica accumulation. A single global policy is always wrong for some field.
If you use LWW, use a causally sound timestamp — an HLC or a server-assigned monotonic sequence — never the client’s wall clock. A client with a clock five minutes fast can pin a value permanently, because every later write looks older.
Carry the version context through read-modify-write cycles. A client that reads version {a:3} and writes without echoing it back forces the server to treat the write as concurrent with everything, which is where sibling explosion comes from.
Where you only need session guarantees rather than full conflict detection, a single opaque version token per session — the highest version the client has observed, sent with each request — is far cheaper than a vector clock and gives read-your-writes and monotonic reads.
Interview questions and how to answer them
Why can’t you order events in a distributed system by timestamp?
Because the timestamps come from different clocks. NTP keeps them within milliseconds at best, and a correction can step a clock backwards, so two events microseconds or milliseconds apart may carry timestamps in the wrong order. Worse, a timestamp comparison always produces an order, so it cannot tell you that two events were genuinely concurrent and need merging.
Walk me through a vector clock detecting a conflict.
Both clients read a value with clock {a:1}. Client B writes via node b, producing {a:1,b:1}; client C writes via node c, producing {a:1,c:1}. Neither dominates: {a:1,b:1} has b:1 > 0 while {a:1,c:1} has c:1 > 0. So the replica keeps both as siblings. A subsequent client that reads both and writes a merged value with clock {a:1,b:1,c:1} dominates them both, and the siblings collapse.
What is the difference between a Lamport clock and a vector clock?
A Lamport clock is a single counter and guarantees only one direction: if A caused B then L(A) < L(B). It cannot distinguish concurrency from causation, so it is useful for producing a deterministic total order (with node id as a tiebreak) but not for conflict detection. A vector clock keeps one counter per node, which is what allows the “neither dominates” comparison that identifies concurrent writes.
When is last-write-wins acceptable?
When losing one of two concurrent writes is genuinely harmless, and the timestamp source is causally sound. A cache entry, a presence status, a most-recent-seen marker: overwriting is the semantics you want. It is not acceptable for anything accumulative — set membership, balances, collaborative text — because the discarded write represented real intent.
How would you implement read-your-writes on an eventually consistent store?
Have the write return a version token and have the client send it with subsequent reads. The server either routes to a replica known to have applied that version or waits briefly for it, and otherwise falls back to the primary. This is a causal-session guarantee implemented with one opaque token, and it is much cheaper than full vector clocks because it only tracks what this client has seen.
What do hybrid logical clocks add?
Timestamps that are simultaneously close to physical time and consistent with happens-before. The physical component makes values comparable and debuggable across nodes; the logical component is bumped when the physical clock has not advanced past a received timestamp, so causality is never violated even under skew. It gives most of the practical benefit of causal tracking at constant size.
Answers that lose the round
- Ordering distributed events by wall-clock timestamp and calling the result causality
- Claiming last-write-wins “resolves” conflicts when it discards one of them, chosen by clock skew
- Asserting that a vector clock gives a total order — it deliberately does not, and concurrency is the information it adds
- Confusing Lamport clocks with vector clocks: Lamport gives a consistent total order but cannot detect concurrency
- Letting vector clocks grow unbounded by keying entries on clients instead of servers
- Reading siblings and writing back without resolving them, which multiplies versions instead of collapsing them
- Assuming NTP makes timestamps comparable — typical skew is milliseconds to tens of milliseconds and corrections can move a clock backwards
FAQ
Are vector clocks still used?
Yes, though often in refined forms. Riak uses dotted version vectors, Cassandra’s counters and Dynamo-derived systems track per-replica state, and CRDT libraries carry version vectors internally. The refinements exist because naive vector clocks grow with the number of writers and can produce false concurrency when clients do not preserve context.
What is a CRDT’s relationship to this?
A CRDT sidesteps the conflict question by choosing data types whose merge is commutative, associative, and idempotent — a grow-only set, a PN-counter, an LWW-register with a causal timestamp. You still need causality information inside the type, but the application never sees siblings, because merging is always defined. The cost is being restricted to those types and to their metadata overhead.
Does Google Spanner avoid all of this?
It avoids the conflict-resolution problem by serialising writes through consensus rather than accepting concurrent ones, and it uses TrueTime — GPS and atomic clocks giving a bounded uncertainty interval — to assign commit timestamps that respect real time. It pays for that with a commit wait and with hardware most deployments do not have.