Version Vectors Distinguish Concurrent Updates from Causal Successors

Replicated data can receive writes at different nodes while communication between those nodes is delayed. When versions later meet, a scalar revision number can say that two values differ, but it cannot always say whether one descends from the other or both were produced independently.

A version vector records progress per replica. Comparing those counters provides a partial order: one version can dominate another, the vectors can be equal, or neither can dominate. The last case identifies concurrent histories that require an explicit reconciliation rule.

A vector records causal progress by replica

For replicas A and B, a version can be represented as a map of counters:

{A: 3, B: 1}

When A creates a new local version, it increments its own component. When a replica incorporates another version, it first merges component-wise maxima, then increments its own component for a new local event.

max({A:3, B:1}, {A:2, B:4}) = {A:3, B:4}

The counters are logical metadata. They do not represent wall-clock time and do not require synchronized clocks.

Dominance identifies a causal successor

Vector X dominates vector Y when every component in X is greater than or equal to the corresponding component in Y and at least one component is greater.

X = {A:3, B:2}
Y = {A:2, B:2}

X dominates Y

If a stored value carries Y and an incoming value carries X, the metadata establishes that X includes causal progress beyond Y. A system can replace Y with X without treating the pair as independent conflicting edits, subject to its data model.

Equal vectors represent the same observed causal frontier even if duplicate delivery caused the version to arrive again.

Incomparable vectors identify concurrency

Suppose communication is interrupted after both replicas have observed {A:1, B:1}. A writes locally and produces {A:2, B:1}. B also writes locally and produces {A:1, B:2}.

left  = {A:2, B:1}
right = {A:1, B:2}

Left is greater in component A. Right is greater in component B. Neither dominates the other, so the updates are concurrent in the causal order.

This does not mean the writes occurred at the exact same physical time. They may be seconds or hours apart. Concurrency here means neither version includes the other in its causal history.

Conflict detection is separate from conflict resolution

A version vector can identify concurrent versions, but it does not decide which application value should survive. Resolution belongs to the data model.

A key-value store may retain siblings and ask a later read or write to reconcile them. A structured data type may merge fields. Another application may apply a deterministic domain rule. Discarding one side solely because its server clock is later replaces causal information with a clock-based policy and can lose an independent update.

The vector therefore answers an ordering question. It is not itself a merge algorithm.

Replica identity affects metadata size

A straightforward vector carries one counter per participating replica. That is manageable for a stable, bounded replica set, but expensive when writers are numerous or ephemeral.

Replica identifiers also need lifecycle rules. Reusing an identifier after its counter resets can make new events appear older than historical events from the previous owner of that identifier.

Systems with dynamic membership often use variants or additional mechanisms to compact causal metadata. Any compaction scheme must preserve the ordering facts required by the application’s reconciliation semantics.

Merge uses maxima, not addition

When two causal contexts meet, each component represents observed progress for one replica. Combining contexts therefore takes the maximum counter for each component.

v1 = {A:5, B:2, C:1}
v2 = {A:3, B:4, C:1}

merge(v1, v2) = {A:5, B:4, C:1}

Adding counters would invent events. The merged context says that events through A5 and B4 have been observed; it does not claim seven events at either replica.

A subsequent local write at C can increment C and produce {A:5, B:4, C:2}. That new version dominates both input contexts.

Causal metadata belongs with the version it describes

The comparison is reliable only when value and causal metadata move together through storage, replication, retries, and repair. Updating a payload while accidentally retaining an older vector can misclassify later comparisons.

Persistence should therefore treat the value and its version vector as one logical record. Replication protocols should transfer both, and conditional writes should compare against the causal state expected by the operation.

Version vectors are most useful when the system must preserve independent writes rather than force every mutation through one global serialization point. They provide a compact rule for that decision: dominance marks causal succession; incomparability marks concurrent history; application semantics decide what to do with the concurrent values.