Vector Clocks and Causal Consistency

Symptom

You took the lesson from T058 and stopped trusting wall clocks. Every event now carries a Lamport timestamp, and your writes are ordered by it. The vanishing updates stopped.

Then a different bug arrives. A user edits their profile from a phone and a laptop within the same minute. The two edits never saw each other, so the correct behaviour is to detect a conflict and either merge or ask. Instead one silently overwrote the other, because the laptop’s write happened to carry Lamport timestamp 47 and the phone’s carried 44, and 47 > 44, so the system concluded the laptop’s write came after and knew about the phone’s.

It did not. The two are concurrent. Nothing about them is ordered. Your clock manufactured an order that the underlying causality does not support, and then your last-write-wins rule acted on that fiction and threw away real data.

Here is the sharper version of the problem. Given two Lamport timestamps $L(a) < L(b)$, what can you conclude?

Almost nothing. Either $a \to b$, or $a$ and $b$ are concurrent. The one thing you can conclude is the contrapositive: if $L(a) \ge L(b)$ then $a$ definitely did not happen before $b$. That is a real fact and it is much weaker than what your code assumed.

The symptom, in one line: Lamport clocks can tell you that an order exists, but not that one doesn’t. And detecting concurrency, not detecting order, is what conflict resolution actually needs.

Statement

A vector clock fixes exactly this, and the fix is complete.

Each of $n$ processes keeps a vector $V$ of $n$ counters. Process $i$ increments $V[i]$ on each local event, attaches $V$ to every message, and on receipt sets $V[k] \leftarrow \max(V[k], V_{\text{msg}}[k])$ for every $k$, then increments its own entry.

Define $V(a) \le V(b)$ to mean $V(a)[k] \le V(b)[k]$ for all $k$, and $V(a) < V(b)$ to mean $V(a) \le V(b)$ with at least one strict inequality.

$a \to b$ if and only if $V(a) < V(b)$. Two events are concurrent exactly when neither vector dominates the other.

The word doing the work is iff. Lamport gives you an implication; vector clocks give you an equivalence. That upgrade is the entire content of the result, and it is what makes concurrency detectable.

And there is a price, which is also a theorem: any timestamping scheme that characterizes happens-before in a system of $n$ processes needs $n$ components. Charron-Bost proved this in 1991. The $O(n)$ metadata is not an artifact of Fidge’s particular construction, it is the information-theoretic cost of the guarantee. You cannot be clever and get it in $O(\log n)$.

Argument

Forward direction: $a \to b \implies V(a) < V(b)$.

By induction over the happens-before relation’s three generating cases. If $a$ and $b$ are consecutive events in the same process, $b$’s vector is $a$’s with one entry incremented, so $V(a) < V(b)$. If $a$ is a send and $b$ is the matching receive, the merge takes a componentwise max with $V(a)$, so every entry is at least as large, and the local increment makes one strictly larger. Transitivity of the componentwise order closes the induction.

Reverse direction: $V(a) < V(b) \implies a \to b$. This is the direction Lamport clocks fail, and the proof is short.

Let $a$ be an event at process $i$. By construction $V(a)[i]$ is the count of events at process $i$ up to and including $a$, and this entry is only ever incremented by process $i$ itself. Every other process learns about it solely through the max-merge on message receipt.

Now suppose $V(a) \le V(b)$, so in particular $V(b)[i] \ge V(a)[i]$. If $b$ is also at process $i$, then $b$ is at least as late in the local sequence, so $a \to b$ or $a = b$. If $b$ is at some other process $j$, then process $j$ can only have $V[i]$ that large by having received a chain of messages that ultimately originates at process $i$ at or after event $a$. That chain is a happens-before path from $a$ to $b$. $\blacksquare$

The mechanism, stated plainly: entry $i$ of a vector is a claim about what process $i$ has done, and the only route by which that claim can travel to another process is a message. So a large entry is evidence of a causal path, and the vector is a record of the frontier of everything you have transitively heard about.

Concurrency, then, is the failure of both comparisons. If $V(a) \not\le V(b)$ and $V(b) \not\le V(a)$, each event knows something the other does not, so no causal path runs in either direction. That is exactly the conflict your last-write-wins rule was papering over.

A trace, so the vectors are concrete. Three processes, $A$, $B$, $C$.

1. $A$ writes. $V_A = (1,0,0)$.
2. $A$ sends to $B$. $B$ receives and writes: $V_B = (1,1,0)$.
3. Independently, $C$ writes, having heard from nobody: $V_C = (0,0,1)$.

Compare $B$’s write and $C$’s write. $(1,1,0)$ versus $(0,0,1)$: the first is larger in components 1 and 2, the second is larger in component 3. Neither dominates, so they are concurrent, correctly. Compare $A$’s write with $B$’s: $(1,0,0) \le (1,1,0)$ and they differ, so $A \to B$, correctly. Lamport clocks would have given these events the scalars 1, 2, and 1, and the comparison between $B$ at 2 and $C$ at 1 would have reported a spurious order.

What causal consistency then means. A store is causally consistent if, whenever $a \to b$, every process observes $a$ before $b$. Concurrent writes may be observed in different orders by different processes, and that is permitted. This is the strongest consistency model achievable without giving up availability during a partition, which is why it sits exactly where it does in the CAP landscape (T066).

Forbids

A single scalar that detects concurrency. By Charron-Bost’s lower bound, no timestamp of dimension less than $n$ characterizes happens-before among $n$ processes. Sequence numbers, hybrid logical clocks, and Lamport clocks all fail this, necessarily and not through poor design.

Last-write-wins as a correct conflict resolution strategy. LWW does not resolve conflicts, it hides them by picking one. When two writes are concurrent, there is no fact of the matter about which is later, so any rule that names a winner is discarding a real update. This is fine when the data is a cache entry and catastrophic when it is a shopping cart.

Constant-size causal metadata in a system with unboundedly many writers. If every client is its own actor in the vector, the vector grows without bound. This is a genuine operational problem and the mitigations (below) are all lossy in some direction.

Detecting causality between events in systems that never exchanged messages. Vector clocks track potential causality through the message graph only. If process $A$ influences process $B$ through a side channel — a shared database, a human reading a dashboard and typing a command, a file on disk — the clocks see independence where a real causal link exists. Lamport is explicit about this: happens-before is about the message-passing structure, and anything outside it is invisible.

Does not forbid

It does not forbid smaller causal metadata in practice, and the systems that do it are worth naming. Riak’s dotted version vectors bound the vector by the number of server replicas, not clients, by having the coordinating server own the entry. A three-replica cluster carries three entries regardless of how many million clients write. Cassandra skips vectors entirely and uses LWW with client timestamps, accepting silent loss as a documented tradeoff. CockroachDB and YugabyteDB use hybrid logical clocks, which are scalars plus bounded physical-clock error, and get most of the ordering benefit for $O(1)$ metadata while explicitly not characterizing concurrency. Each of these is a real engineering answer to the $O(n)$ cost, and each pays somewhere.

It does not forbid pruning. Entries for actors that have been inactive longer than a known bound can be dropped, at the cost of occasionally reporting concurrent events as ordered. Riak prunes on both age and vector length. The guarantee degrades gracefully rather than breaking, which is the right shape for a production system.

It does not mean causal consistency is enough for everything. It is not. Causal consistency permits two concurrent “withdraw” operations to both succeed and drive the balance negative, because they are genuinely concurrent and causal consistency has nothing to say about them. If you need a global invariant across concurrent operations, you need consensus (T064), and the CALM theorem (T067) tells you exactly which invariants have this property.

It does not require vector clocks specifically, which is the misreading that sends teams down a long implementation road they did not need. If your data type is a CRDT — a G-counter, an OR-set, a LWW-register with a proper lattice — concurrent updates merge deterministically and you never need to detect the conflict because you never need to resolve it. Automerge and Yjs power collaborative editors this way, and Redis CRDTs and Azure Cosmos DB ship it commercially. Detecting concurrency matters only when resolution requires a decision. Design the type so it doesn’t, and the whole apparatus becomes unnecessary.

It does not mean version vectors and vector clocks are the same thing, and conflating them causes real bugs. A vector clock timestamps events and its entries are per-process. A version vector timestamps replicas of an object and its entries are per-replica. They have identical mechanics and different domains, and code that indexes one by the other’s actor set will produce comparisons that are meaningless rather than merely wrong.

Boundary

The $O(n)$ cost is real and it is where all the engineering happens. Concretely, in a 1000-node cluster with 8-byte counters, a full vector is 8000 bytes of metadata per version. For an object whose payload is a 200-byte JSON blob, the causality tracking is forty times the size of the data. This is why nobody runs unbounded vector clocks at scale.

The escape routes, ordered by how much they give up:

• Bound the actor set. Server-side dotted version vectors: entries scale with replicas (typically 3 to 5), not clients. Nearly free, and the standard answer.
• Prune stale entries. Bounded size, occasional false ordering.
• Use a scalar plus bounded clock error. Hybrid logical clocks. $O(1)$, and you lose concurrency detection but keep causal ordering under a real-time bound.
• Make conflicts impossible. CRDTs. You stop needing the detection at all, at the cost of constraining the data type to something with a merge.

What remains, after all of them: causality tracked through message passing only. Any influence that leaves your system and re-enters it — a user, a cron job, an external API — is a causal edge your clocks do not have and cannot infer. And the direction the whole subject is heading is the last bullet: the cheapest concurrency detector is a data type that does not care.

Read next