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 — 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] 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. withdrawn registry ↩