Vector Clocks/Version Vectors and Detecting Concurrent Updates

Learning outcomes

Two AtlasMart regions disconnect after both have seen catalog version 1. East edits a description while West edits the same aggregate independently. A scalar counter can assign both branches “version 2,” which cannot tell whether the values are duplicates or siblings. A version vector carries per-actor counters so the merge layer can ask a richer question: did one version include the other's causal history, or are they concurrent?

1. From one scalar to one counter per actor

For a fixed actor set such as [east, west, central], a vector might be {east:4, west:2, central:7}. Each component summarizes how many updates from that actor are included in the version's causal context. When an actor performs a new update, it increments its own entry. When contexts are joined, the component-wise maximum summarizes the union of known history.

2. Component-wise comparison detects concurrency

Let vectors A and B use the same actor coordinates. If every component of A is less than or equal to B and at least one is smaller, A is an ancestor of B: B's context contains all updates summarized by A plus more. If each vector has at least one component greater than the other, neither contains the other's history. The versions are concurrent.

This answers a question Lamport scalar clocks cannot answer from timestamps alone. Lamport gives an order compatible with causality; a vector exposes incomparability under its actor model.

3. Siblings are detected conflicts, not automatically solved conflicts

When East and West edit the same AtlasMart value while disconnected, vector comparison can say “these are concurrent siblings.” It cannot decide whether to keep East, keep West, union fields, add quantities, reject both, ask a human, or apply a conflict-free replicated datatype. Resolution is a domain policy covered later in Chapter 18.

4. Actor identity and vector growth are operational design problems

The textbook vector has one component per actor. If “actor” means every ephemeral process or mobile client ever created, metadata can grow without bound and identities become difficult to retire safely. Real systems therefore choose stable replica IDs, summarize client causality differently, prune retired actors only with protocol evidence, or use variants designed to bound or compress causal metadata.

The exact variant matters. Calling every causal-context structure a “vector clock” can hide differences between event clocks, replica version summaries, client contexts, and per-key siblings. This course uses the simple fixed-actor vector to teach comparison semantics, then explicitly labels its scalability limit.

5. Dynamo as a concrete historical example

Amazon's Dynamo paper describes versioning objects and reconciling divergent versions in a highly available key-value design. Its discussion is useful because it ties causal version information to a real conflict scenario: multiple versions can survive a partition and later require reconciliation. The lesson does not copy Dynamo as a universal algorithm; modern systems use many different conflict/version schemes.

6. Deliberately wrong approach — scalar “version = previous + 1” on disconnected writers

Both East and West read scalar version 1, disconnect, and independently produce version 2. Equality now collapses two possibilities: both replicas might hold the same propagated update, or they might hold different concurrent updates derived from the same parent. Adding a node-ID tie-breaker makes the outcome deterministic but still silently discards one branch.

The repair is to preserve enough causal context to distinguish the branches, then apply a domain-specific merge/selection rule. If multi-writer conflict is unacceptable, a stronger repair may be single-owner routing or coordinated conditional writes rather than carrying more metadata.

7. AtlasMart lab — detect siblings with version vectors

ACTORS = ("east", "west", "central")

def zero():
    return {a: 0 for a in ACTORS}

def increment(v, actor):
    out = dict(v)
    out[actor] += 1
    return out

def merge(a, b):
    return {k: max(a[k], b[k]) for k in ACTORS}

def relation(a, b):
    a_le_b = all(a[k] <= b[k] for k in ACTORS)
    b_le_a = all(b[k] <= a[k] for k in ACTORS)
    if a == b:
        return "equal"
    if a_le_b:
        return "ancestor"
    if b_le_a:
        return "descendant"
    return "concurrent"

base = zero()
base = increment(base, "central")
east_seen = dict(base)
west_seen = dict(base)

east_write = increment(east_seen, "east")
west_write = increment(west_seen, "west")

print("base       ", base)
print("east write ", east_write)
print("west write ", west_write)
print("east vs west:", relation(east_write, west_write))

joined_context = merge(east_write, west_write)
print("merged causal context:", joined_context)

resolved = increment(joined_context, "central")
print("after explicit resolution:", resolved)
print("east -> resolved:", relation(east_write, resolved))
print("west -> resolved:", relation(west_write, resolved))

print("\nWRONG scalar versions")
print("east scalar=2, west scalar=2 -> equality cannot tell same history from concurrent branches")

print("\nmetadata cost")
for actors in (3, 30, 300):
    print(f"{actors:3} actors -> textbook vector carries O({actors}) counters per tracked context")

Expected output

base        {'east': 0, 'west': 0, 'central': 1}
east write  {'east': 1, 'west': 0, 'central': 1}
west write  {'east': 0, 'west': 1, 'central': 1}
east vs west: concurrent
merged causal context: {'east': 1, 'west': 1, 'central': 1}
after explicit resolution: {'east': 1, 'west': 1, 'central': 2}
east -> resolved: ancestor
west -> resolved: ancestor

WRONG scalar versions
east scalar=2, west scalar=2 -> equality cannot tell same history from concurrent branches

metadata cost
  3 actors -> textbook vector carries O(3) counters per tracked context
 30 actors -> textbook vector carries O(30) counters per tracked context
300 actors -> textbook vector carries O(300) counters per tracked context

The East and West vectors are incomparable, so the lab classifies them as concurrent. After an explicit reconciliation, the merged context includes both branches and the central actor increments its own component. The last lines make the metadata cost visible: the simple representation scales with the actor set.

Verification checklist

• Both regional writes begin from the same central context.
• Each writer increments only its own component.
• Component-wise comparison returns concurrent.
• A merged context is the component-wise maximum.
• The lesson never claims vector metadata itself chooses the correct business merge.

8. Production judgment and next bridge

Use causal version metadata when the system permits multiple writers and must preserve rather than silently overwrite concurrent work. Keep actor identity stable and documented, test actor replacement/retirement, and monitor sibling/conflict rates. Do not add vector complexity to a workload that can more safely use single ownership or one linearizable conditional mutation.

Lesson 4 returns to the need for time-like values. Hybrid logical clocks combine a physical-time component with logical correction so timestamps remain close to physical time while preserving causal monotonicity. They reduce neither clock uncertainty nor the need for explicit conflict semantics.

Authoritative references

• DeCandia et al. — Dynamo: Amazon’s Highly Available Key-value Store — concrete use of object versioning and reconciliation in a highly available store
• Almeida, Almeida & Baquero — Bounded Version Vectors — version vectors as causality tracking plus metadata-growth discussion
• Lamport — Time, Clocks, and the Ordering of Events — baseline logical-clock model contrasted with vector-style causality detection