Skip to content

Version-Vector or Dotted-Context Exchange

Causal-metadata protocol — instantiates Asynchronous Replica Convergence

Tags each update with per-replica version counters and exchanges them, so replicas can tell a causally newer write from two genuinely concurrent ones instead of guessing by wall-clock time.

Version-Vector or Dotted-Context Exchange supplies the causal bookkeeping that lets replicas reason about order without a shared clock. Each update is stamped with a version vector — one counter per replica — and replicas exchange these vectors so any two values can be compared: either one causally descends from the other (and cleanly supersedes it) or neither does (and the two are genuinely concurrent — a real conflict). Its defining contribution is drawing that line between "newer" and "concurrent" precisely, so the system never mistakes two independent edits for one superseding the other. It carries the metadata and the comparison only; it deliberately does not merge or resolve — it tells the merge which case it is in.

Example

Two teammates edit the same note's title in an offline-first notes app while both are disconnected. Alice renames it; Bob, independently, renames it differently. A naive store using wall-clock "last write wins" would keep whichever laptop's clock read later and silently discard the other rename — a lost update nobody chose. With version vectors, Alice's edit carries a vector with her counter bumped, Bob's with his bumped.

On sync, comparing the two vectors shows neither dominates — Alice's leads on her counter, Bob's on his — so the system flags them as concurrent and surfaces both titles as siblings for a merge rule (or a person) to reconcile, rather than picking one by accident. Had Bob instead received Alice's rename and then edited, his vector would dominate hers and supersede it with no conflict at all. The metadata turned an invisible clobber into an explicit, honest choice.

How it works

Its distinctive mechanism is the partial order over versions. Each replica keeps a monotonic counter; a value's vector records the highest counter it has seen from every replica, so comparing two vectors component-wise answers "did this happen before that?" — one vector ≥ the other on every component means causal descent, while incomparable vectors mean concurrency. Dotted version vectors refine this by tracking each individual update as a "dot," which prunes metadata and avoids false conflicts as replicas come and go. The exchange piggybacks these vectors on updates so every replica shares a consistent view of what has been seen. What it hands downstream is a verdict — supersede or conflict — not a resolution.

Tuning parameters

  • Actor granularity — one counter per replica (compact) versus per client or per session (detects finer concurrency but inflates the vector). Misassigning actor identity — say, per-request — explodes the metadata or misses real concurrency.
  • Plain versus dotted version vectors — dotted contexts prune entries for retired replicas and avoid false conflicts, at the cost of more intricate bookkeeping; plain vectors are simpler but grow and can over-report conflicts.
  • Pruning / compaction — how aggressively to drop counters for replicas that have left. Caps unbounded growth as membership churns, but over-pruning risks losing causal information.
  • Exchange cadence — piggyback vectors on every update (freshest causal view, more overhead) or batch them (cheaper, slightly staler ordering).

When it helps, and when it misleads

Its strength is recovering true causal order in a system with no global clock, so concurrent updates are detected rather than silently collapsed — it is the metadata backbone that read-repair, the background exchange, and every merge rule lean on to decide whether to supersede or to flag a conflict.[1] Its limits are real: version vectors grow with the number of replicas or actors (metadata bloat), depend on stable actor identities, and — crucially — they tell you that two writes are concurrent, never how to reconcile them; resolution is a separate merge or conflict rule. The classic misuse is swapping version vectors for wall-clock timestamps "to keep it simple," which reintroduces the exact lost-update bug the vectors exist to prevent, or letting the vectors grow without bound. The discipline is to use stable per-replica actor IDs, prune with dotted contexts, and always pair the detection with an explicit rule for the concurrent case.

How it implements the components

Version-Vector or Dotted-Context Exchange fills the causal-metadata components — the ones a version-tracking protocol can fill:

  • causal_context_or_version_frontier — the version vector (or dotted context) is the causal frontier: a compact record of what each replica has seen, enabling the happens-before test.
  • version_token — each update's per-replica counter value is the version token that stamps the write and composes into the vector.

It does not decide how two concurrent values combine or which wins (that is CRDT-Like State Merge or a conflict rule) and does not perform the single-object compare-and-set of Optimistic Concurrency Check. It supplies the causal metadata those consume.

Notes

Version vectors and Optimistic Concurrency Check both compare versions, but for opposite purposes. Optimistic concurrency uses a single version token on a single object to reject a write whose base is stale — coordination that prevents divergence. Version vectors track many replicas' causal history to permit independent writes and classify the result as superseding or concurrent — bookkeeping that manages divergence after the fact. One says "no, retry"; the other says "both happened, now merge."

References

[1] Version vectors (kin to Lamport's vector clocks and the happened-before relation) capture causal history as one counter per replica, so two updates can be compared as one-precedes-the-other or concurrent; dotted version vectors, introduced in systems like Riak, track individual updates to keep the metadata compact and avoid spurious conflicts. The vector detects concurrency; it does not resolve it. ↩