Version Vectors Separate Causality from Concurrency

Replicated data can receive writes at several nodes while communication between those nodes is delayed. When two versions meet later, a store has to decide whether one descends from the other or whether both were created independently.

A wall-clock timestamp gives a total-looking order, but clock order is not causal order. Two replicas can write during a partition, and whichever timestamp happens to be larger does not make that write a descendant of the other.

A version vector records progress per replica. Comparing those counters lets the system classify versions as equal, causally ordered, or concurrent. That classification preserves information that a single scalar timestamp discards.

One counter cannot represent independent progress

Suppose replicas A and B both hold version x. A client updates A while B is disconnected:

A: x -> x1
B: x

Later, another client updates B:

A: x1
B: x2

Neither update observed the other. Treating one as newer merely because its wall-clock timestamp is later hides the fact that two branches exist.

A scalar revision generated independently at each replica has the same problem. 17 at A and 22 at B do not establish causality unless both values come from one ordering authority, which adds a coordination boundary the replicated design may be trying to avoid.

A vector records each replica’s contribution

For replicas A, B, and C, a version vector can be represented as:

{A: 4, B: 2, C: 7}

Each component says how far the version has incorporated events attributed to that replica. A local write increments the local component.

If A holds:

v1 = {A: 4, B: 2}

and performs a new write, the resulting version is:

v2 = {A: 5, B: 2}

v2 is causally after v1 because every component in v2 is at least as large and one component is larger.

The vector is metadata about history, not a timestamp. Its values do not need to correspond to seconds or any physical clock.

Comparison produces a partial order

For vectors p and q, p dominates q when every component in p is greater than or equal to the corresponding component in q, with at least one strict increase.

Example:

p = {A: 5, B: 3}
q = {A: 4, B: 3}

p dominates q

The store can discard q when p represents the same logical object because p already includes the history represented by q.

Concurrency appears when neither vector dominates the other:

p = {A: 5, B: 2}
q = {A: 4, B: 3}

p is ahead on A and behind on B. q is ahead on B and behind on A. Neither version contains the full history of the other.

That result is the useful signal: both branches may need to survive until application-specific reconciliation occurs.

Missing components behave like zero

Implementations rarely need to store explicit zeroes for every known replica. These vectors are equivalent for comparison:

{A: 3}
{A: 3, B: 0, C: 0}

A comparison can treat an absent component as zero.

This representation helps sparse systems, but vector size still grows with the number of distinct replica identities that contribute writes. Replica identity management therefore becomes part of the protocol rather than a naming detail.

Merge joins histories without choosing a value

The component-wise maximum of two vectors forms their causal join:

p = {A: 5, B: 2}
q = {A: 4, B: 3}

join(p, q) = {A: 5, B: 3}

That operation merges causal context. It does not decide which application value should win.

If p contains shipping address X and q contains shipping address Y, the vector can establish that the values are concurrent. It cannot decide whether X, Y, both, or a newly computed value is correct.

Reconciliation remains a data-model decision. A set may union members, a counter may use a CRDT rule, a user-facing document may expose a conflict, and a domain workflow may reject automatic resolution.

A resolved write must carry both branches

Suppose a client reads both concurrent versions:

p = {A: 5, B: 2}
q = {A: 4, B: 3}

The client resolves them and writes a new value at A. The new causal context should first join both histories, then increment A:

join      = {A: 5, B: 3}
new write = {A: 6, B: 3}

The resulting version dominates both prior branches. A replica receiving it can safely classify both as ancestors.

If the resolver writes from only p, it produces something such as {A: 6, B: 2}. That version still remains concurrent with q, because it never incorporated B’s third event.

The causal context attached to a write therefore matters as much as the value being written.

Replica IDs require lifecycle rules

A vector assumes that a component name has stable meaning. Reusing a replica ID after losing its counter can make new events appear older than history already stored elsewhere.

For example, if other replicas have seen:

{A: 900}

and a replacement node starts again as A with counter 1, ordinary vector comparison treats its writes as ancestors of the old A history.

Safer designs preserve the counter durably, assign a fresh identity to a replacement incarnation, or use a protocol that explicitly handles membership epochs.

Retiring identities also needs care. Removing a component from stored vectors too early can erase causal evidence still required by a disconnected replica. Garbage collection is safe only when the system has a protocol-specific basis for concluding that the removed history can no longer reappear as relevant concurrent state.

Version vectors do not provide a global event order

Two concurrent vectors are intentionally incomparable. That is not a defect to patch with arbitrary tie-breaking if the application needs to preserve concurrent writes.

A total order is a different contract. Consensus logs, sequencers, or database serialization can provide stronger ordering at the cost of coordination. Version vectors serve systems that need causal classification without forcing every independent write through one global ordering point.

They also do not make replication instantaneous. A replica can remain stale until it receives newer state. The vector describes relationships among versions that exist; it does not deliver those versions.

Storage and wire formats need deterministic rules

A practical implementation needs a stable representation for replica IDs and counters. Comparison should operate on integer values rather than serialized field order.

For example, these JSON objects carry the same vector:

{"A": 5, "B": 3}

{"B": 3, "A": 5}

If vectors are signed, hashed, or used as cache keys, canonical serialization may matter. That requirement is separate from vector semantics and should be specified explicitly.

Counter overflow also deserves a defined policy. Silent wraparound destroys monotonicity for a replica component. Wide integer counters make rollover remote in ordinary operation, but the implementation should still reject or handle exhaustion rather than reuse low values.

Conflict metrics reveal topology and workload

Concurrent-version frequency can be operationally useful. A rise in conflicts may indicate longer partitions, replication lag, clients writing through several regions, or a workload whose ownership pattern no longer matches the replication strategy.

Useful measurements include:

concurrent versions created
concurrent versions resolved
age of unresolved branches
vector component count
replication lag by peer

These signals do not replace application correctness checks. They show how often the system enters states where reconciliation policy matters.

Causality is the information worth preserving

A replicated store does not always need to declare one of two disconnected writes the winner immediately. First it needs to know their relationship.

Version vectors encode enough per-replica history to make that distinction. Dominance identifies a causal successor. Incomparability identifies concurrent branches. A component-wise join records that both histories have been incorporated.

That partial order is narrower than a global sequence, but it matches the question replicated systems often need to answer: whether a version contains another version’s history, or whether both must still be treated as independent.