Skip to content

Version Vector

Versioning artifact — instantiates Shared-State Consistency Contract Design

Tags each version of a value with a per-replica counter map, so the system can tell whether two versions are causally ordered or genuinely concurrent — and thus in conflict.

Version Vector is the artifact that records causal order as data. Each value carries a vector of per-replica update counters; comparing two vectors reveals their relationship exactly: if every counter in one is greater-than-or-equal to the other (and at least one is strictly greater), the first causally descends from the second and is safely newer; if each has some counter the other exceeds, the two are concurrent — neither happened before the other, so they are a genuine conflict. Its distinguishing contribution is precision about ordering: it encodes the happens-before relation, letting every other mechanism distinguish "safe to overwrite" from "must reconcile" — something a single wall-clock timestamp fundamentally cannot do. It detects conflicts; it deliberately does not resolve them.

Example

A contacts app syncs across a user's phone and laptop, each an offline-capable replica. Offline, the phone edits a contact (vector becomes {phone:2, laptop:1}) while the laptop edits the same contact differently ({phone:1, laptop:2}). When they sync, neither vector dominates the other — each has a counter the other exceeds — so the system knows these are concurrent edits and surfaces a real conflict for resolution, rather than silently discarding one. Contrast a later phone edit made after seeing the laptop's version: its vector {phone:3, laptop:2} dominates {phone:1, laptop:2}, so the system knows it is simply newer and overwrites with no conflict. A lone timestamp could not have told these two situations apart — both would have looked like "one is later."

How it works

The distinguishing mechanic is element-wise vector comparison standing in for synchronized clocks. Each replica increments its own slot on every write it originates; a value carries the accumulated vector; comparing two values is a per-element check yielding dominates, dominated-by, or concurrent. This makes Lamport's happens-before relation a first-class, storable property of each version. Refinements such as dotted version vectors extend the scheme to stay correct under sloppy quorums. The artifact is a substrate: read repair, multi-leader resolution, and session tokens all consume its verdicts.

Tuning parameters

  • Vector scope — per-key, per-object, or coarser: finer scope is more precise but multiplies metadata.
  • Actor granularity — one slot per replica vs. per client: precision versus vector explosion as writers grow.
  • Pruning policy — how retired replica slots are dropped to bound size: too aggressive risks false concurrency or lost causality.
  • Plain vs. dotted — dotted version vectors add correctness under sloppy quorums at the cost of complexity.
  • Concurrency handling — whether concurrent versions are surfaced to a resolver or eagerly auto-merged.

When it helps, and when it misleads

Its strength is honest conflict detection: it never falsely overwrites a concurrent write the way last-write-wins can, and it captures order without any synchronized clock — the trustworthy substrate for merge and repair.

It misleads in two directions. First, vectors grow with the number of writers and can bloat, so real systems prune — and pruning is exactly where subtle causality bugs hide, since dropping a slot too eagerly can turn a real ordering into apparent concurrency or vice versa.[1] Second, and more common: it detects conflicts but says nothing about resolving them, so pairing version vectors with a last-write-wins rule throws away the very concurrency information you paid to compute. The backwards move is storing version vectors and then resolving with wall-clock timestamps anyway. The discipline is simple — if you pay for version vectors, resolve with them (a real merge), not with clocks.

How it implements the components

  • version_token — the per-replica counter vector attached to each value is the canonical version token other mechanisms compare.
  • visibility_and_order_relation — the vector encodes the happens-before / causal order directly, making the ordering relation an inspectable property of the data.

It does not resolve the conflicts it surfaces (conflict_resolution_rule) — that is Multi-Leader Replication with Conflict Resolution and the merge mechanisms — nor hold a client-session watermark (client_observation_model, Session-Guarantee Token) or provide real-time total ordering (Linearizable Read/Write Protocol / Hybrid Logical Clock).

Notes

Version Vector is infrastructure other mechanisms depend on, not a standalone feature: quorum reads, read repair, multi-leader resolution, and session tokens all rely on its concurrent-vs-ordered verdict. When it is under-scoped or over-pruned, those consumers fail quietly — a false "not concurrent" leads directly to a silently lost write downstream — so its sizing decisions deserve the same scrutiny as the protocols above it.

References

[1] Version vectors encode Lamport's happens-before relation (1978) as per-actor counters. Their size grows with the number of distinct writers, which is why production systems prune slots or adopt dotted version vectors — and pruning is a frequent source of subtle causality bugs. ↩