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).
Related¶
- Instantiates: Shared-State Consistency Contract Design — the ordering substrate the contract's conflict-handling mechanisms build on.
- Sibling mechanisms: Multi-Leader Replication with Conflict Resolution · Read Repair · Session-Guarantee Token · Hybrid Logical Clock · CRDT-Like State Merge
Editorial Notes¶
Form Classification¶
Form family: Representation, Specification & Plan
Rationale: Version Vector operates as a static representation, map, specification, schema, or prospective plan that externalizes information because it 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.
Independent corroboration: The frozen evidence defines Version Vector as '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', so its operative form is Representation, Specification & Plan.
Nearest alternative: Record, Log & Register — Version Vector includes features of a persistent ledger, log, register, or case record that preserves history and traceability, but its defining operation is a static representation, map, specification, schema, or prospective plan that externalizes information.
Review outcome: Independent reviewer agreement; medium confidence.
Origin Attribution¶
Primary origin: Computer Science & Software Engineering
Origin pattern: Single lineage
Present-day reach: Specialized
Rationale: Both independent reviews identify computer science as the historical home of the operation—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.. The retained alternates document formative adjacent traditions; the reach field, not the origin field, carries later applicability.
Related originating lineages:
- Data Science & Analytics — Data science's modeling, validation, and monitoring tradition contributes a separate formative lineage to the mechanism's version vector logic.
- Engineering & Design (beyond software) — Engineering design, reliability, and systems-safety practice supplies a parallel or contributing lineage for the mechanism's defining operation: 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.
Review resolution: Both blind reviewers independently place the defining operation—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.—in computer science. Their queued differences are secondary: alternate_origin_disagreement, origin_mode_disagreement, domain_reach_disagreement, encyclopedia_synthesis_disagreement. Reviewer A uniquely contributes ['data_science']; reviewer B uniquely contributes ['engineering_design']. I preserve the full evidence-supported union of 2 alternate domain(s), without a numeric cap. origin_mode=single_lineage reflects the more specific lineage judgment in reviewer B's evidence, while domain_reach=specialized separately records present-day portability. The affirmative encyclopedia-synthesis finding is preserved, and confidence=high uses the more conservative reviewer level.
Encyclopedia synthesis: The exact catalogued form synthesizes established practice rather than reproducing a single standard historical label.
Review outcome: Reconciled after independent review; high confidence.
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] Preguiça, Nuno Manuel Ribeiro. "Brief Announcement: Efficient Causality Tracking in Distributed Storage Systems with Dotted Version Vectors". Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing 335–336 (2012). Shows that client-based version vectors grow with the number of writers and that bounding causal metadata can lose ordering information and create false conflicts. registry ↩ Show verification details
Supported in partVerified against the publisher's abstract
The abstract backs only the growth half of the claim: version-vector size scales with concurrent writers, not that pruning slots causes false conflicts.
“to precisely track causality with information with size bounded by the degree of replication, and not by the number of concurrent writers”