Vector clocks reveal two concurrent writes

Two people edit an old shopping list. One removes milk; the other adds bread while keeping milk. When their versions meet, comparing a single timestamp cannot tell you whether one edit knew about the other. A vector clock keeps separate progress for each writer, allowing the system to recognize two causal branches and preserve both for a decision.

This lesson is for students who understand a tuple and a Python set. We will use three fixed writers, compare their vectors component by component, and run a removal that reappears under a union policy. The example is a synthetic version-history model in one Python process. It does not run Dynamo, exchange network packets or implement a complete replicated shopping list.

A vector summarizes a prefix of each writer’s history

Assign fixed positions to writers A, B and C. A version carrying (1, 2, 0) knows A’s first write and B’s first two writes, but no write from C. This interpretation assumes one serialized writer per identity, monotonically increasing counters, complete propagation of observed context, and no lost components. A component is a write count in this model, not a physical time or a quantity of groceries.

We are tracking versions created by writes. Observing a version merges its context into the receiving writer’s knowledge, without creating another object version or incrementing a counter. The next write increments that writer’s own component. A vector-clock model that assigns timestamps to every receive event uses a different event convention; do not insert extra receive increments into the calculations below.

For two vectors, first check equality. Otherwise, the left version is before the right if every left component is less than or equal to its counterpart. At least one component must then be strictly smaller. Reverse the test for after. If neither direction works, the versions are concurrent: each contains some write absent from the other’s causal history.

Python’s ordinary tuple comparison is unsuitable. It compares lexicographically and stops at the first differing component. It would rank (1, 1, 0) above (1, 0, 1), even though the first is larger at B and smaller at C. A consistent total ordering of tuples is not the componentwise partial ordering that this question needs.

Make the two branches visible

A writes the initial list containing milk, producing (1, 0, 0). B and C each observe that version. B removes milk and writes an empty list, producing (1, 1, 0). C adds bread to the older list and writes milk plus bread, producing (1, 0, 1). Neither writer has observed the other’s new version.

View full-size image ↗

Both new versions descend from the initial one: all components of (1, 0, 0) are at most their counterparts in each new vector. The two new vectors are incomparable with each other. The chart’s opposing B and C comparisons are the evidence. Which function call happened first in our central script does not add an observation edge between the writers.

Dynamo’s 2007 paper, section 4.4 “Data Versioning”, describes immutable object versions, vector-clock comparison, and context returned to a client when branches need reconciliation. It distinguishes identifying a descendant from choosing the meaning of a merge. Our three fixed writers make that distinction small enough to calculate without reproducing Dynamo’s routing, quorum or persistence machinery.

A small implementation with an explicit identity contract

The code uses a frozen Version containing a three-integer clock and a frozenset of item names. The comparison accepts only three-component tuples of nonnegative built-in integers; booleans do not qualify as counters. Writer positions are the integers zero, one and two. Calls on each writer are serialized by this script.

Use exactly one Writer instance for each actor within a run, retain it throughout that run, and pass genuine versions from that run to observe. The class does not allocate globally unique identities, persist counters or authenticate incoming history. Creating another Writer with an existing actor number is possible in Python but violates the causal model’s identity contract.

The write method accepts a finite iterable of nonempty built-in strings. It consumes the iterable once into a frozenset; repeated item names collapse, and an empty iterator creates an empty list value. Passing one string or bytes object is rejected so it cannot accidentally become a collection of individual characters. Validation finishes before the writer’s clock changes. The example stores whole values and is not a bounded-memory streaming implementation.

from dataclasses import dataclass


def check_vector(vector):
    if type(vector) is not tuple or len(vector) != 3:
        raise TypeError('a clock is a three-component tuple')
    if any(type(x) is not int or x < 0 for x in vector):
        raise ValueError('clock components are nonnegative built-in integers')


def relation(left, right):
    check_vector(left)
    check_vector(right)
    if left == right:
        return 'equal'
    if all(a <= b for a, b in zip(left, right)):
        return 'before'
    if all(b <= a for a, b in zip(left, right)):
        return 'after'
    return 'concurrent'


@dataclass(frozen=True)
class Version:
    clock: tuple
    items: frozenset

    def __post_init__(self):
        check_vector(self.clock)
        if type(self.items) is not frozenset:
            raise TypeError('items must be a frozenset')
        if any(type(item) is not str or not item for item in self.items):
            raise TypeError('item names must be nonempty built-in strings')


class Writer:
    def __init__(self, actor):
        if type(actor) is not int or not 0 <= actor < 3:
            raise ValueError('actor must be 0, 1 or 2')
        self.actor = actor
        self.clock = (0, 0, 0)

    def observe(self, version):
        if type(version) is not Version:
            raise TypeError('observe expects a Version')
        self.clock = tuple(max(a, b) for a, b in zip(self.clock, version.clock))

    def write(self, items):
        if isinstance(items, (str, bytes)):
            raise TypeError('provide a finite iterable of item names')
        next_clock = list(self.clock)
        next_clock[self.actor] += 1
        version = Version(tuple(next_clock), frozenset(items))
        self.clock = version.clock
        return version

A useful way to check the comparison is to imagine explicit write identifiers: A1, A2, B1 and so on. A vector expands into a prefix set at each actor. Componentwise dominance corresponds to inclusion of these sets. Observing context unions the known prefixes, which is why componentwise maximum is sufficient. A write then creates one new identifier at its actor and records that identifier together with the already known history.

Under the stated fixed-identity rules, this explains both directions of the causal test for the generated write versions. A causal predecessor’s identifiers are included in its descendant’s history. If one version’s entire history is included in another’s, its own write identifier is included too. That later version therefore knows the earlier write. This argument does not justify comparing forged records or histories whose components have been discarded.

Merging context is separate from choosing a value

When A observes both branches, its clock becomes the componentwise maximum (1, 1, 1). That is a joined context. A has not yet written a new shopping list. After the application chooses a value, A’s next write increments its own component and produces (2, 1, 1).

Append this case to the implementation. The first run chooses set union. The second A instance is an independent alternative execution starting from the same observed branches, not a second live owner of A’s identity.

A, B, C = [Writer(i) for i in range(3)]
base = A.write(['milk'])
B.observe(base)
C.observe(base)
removed = B.write([])
added = C.write(['milk', 'bread'])
assert base.clock == (1, 0, 0)
assert removed.clock == (1, 1, 0)
assert added.clock == (1, 0, 1)
assert relation(removed.clock, added.clock) == 'concurrent'
assert relation(base.clock, removed.clock) == 'before'
assert relation(base.clock, added.clock) == 'before'
A.observe(removed)
A.observe(added)
joined_context = A.clock
assert joined_context == (1, 1, 1)
union_result = A.write(removed.items | added.items)
assert union_result.clock == (2, 1, 1)
assert relation(removed.clock, union_result.clock) == 'before'
assert relation(added.clock, union_result.clock) == 'before'
print('remove:', removed.clock, sorted(removed.items))
print('add:', added.clock, sorted(added.items))
print('relation:', relation(removed.clock, added.clock))
print('joined context:', joined_context)
print('union write:', union_result.clock, sorted(union_result.items))
assert 'milk' in union_result.items

# Same observed branches, a different explicit value decision.
A2 = Writer(0)  # Independent alternative run; not another live actor A.
A2.observe(removed)
A2.observe(added)
resolved = A2.write(['bread'])
assert resolved.clock == union_result.clock
assert resolved.items != union_result.items
print('alternative write:', resolved.clock, sorted(resolved.items))

The union result contains milk. B’s empty list has no element that can remove milk from C’s version. A vector clock detects that the branches diverged; it does not encode a rule saying which absence should defeat which presence. The return of milk is a consequence of the selected value policy, not a failure to recognize concurrency.

View full-size image ↗

Dynamo’s section 4.4 explicitly notes that its shopping-cart reconciliation can preserve additions while allowing deleted items to resurface. The paper’s context example and Figure 3 also show why a new reconciled write must carry knowledge of both branches. Our alternative retaining bread only represents an explicit application or user decision. It is not an automatic deletion algorithm supplied by the vector.

Both alternative executions produce the same vector with different contents. They belong to different runs, so this is not a collision inside the assumed unique-writer history. It demonstrates that a vector is not a content hash. Within one valid run, an equal clock can accompany a duplicate copy of a version. If two incompatible values claim the same clock, investigate identity reuse, reset, corrupted context or some other broken assumption instead of silently calling them equivalent data.

Keep the context that makes the comparison meaningful

Space has a cost. This model uses three components because membership is fixed. With many independently identified writers, metadata can grow; comparison and joining must inspect the relevant components. Replacing an absent component with zero is valid for a writer whose history is genuinely unknown in the represented context. It is not a harmless way to forget a component that was previously present.

Dynamo discusses a timestamp-based component truncation scheme in section 4.4 and warns that descendant relationships may then be derived inaccurately. The following controlled projection illustrates information loss. It does not implement that system’s aging policy.

def erase_c(clock):
    return (clock[0], clock[1], 0)

assert relation(removed.clock, added.clock) == 'concurrent'
assert relation(erase_c(removed.clock), erase_c(added.clock)) == 'after'
print('before erasure:', relation(removed.clock, added.clock))
print('after erasure:', relation(erase_c(removed.clock), erase_c(added.clock)))

After C is erased from both clocks, removal appears after addition: (1, 1, 0) dominates (1, 0, 0). That is false for the original history. The information establishing C’s independent write has been removed, so the comparison can no longer preserve its original meaning.

View full-size image ↗

The report is an actual browser capture of an authored page populated with executed Python output and the checked projection values. Its vectors and item sets are model results. They are not observations from a deployed data store. The author checks also compared 729 small vector pairs against explicit prefix sets and generated 1,500 write/observe histories, comparing their write pairs against independently retained causal histories.

Try a causal edit and a broken identity

On a fresh run, let C observe the base and then B’s removal before writing. Then decide explicitly whether C writes bread only or writes milk plus bread. Its new vector should now include B’s component, making its write a descendant of the removal. The vector confirms what C knew; the chosen value still determines whether milk returns.

For a separate failure exercise, start two new Writer instances with actor zero and let each make a different first write. Both produce (1, 0, 0). This is why the class’s local argument checks cannot replace a system-wide identity and counter-lifetime policy. Keep the experiment outside the valid three-writer run.

When reviewing a reconciliation design, ask two concrete questions: what observations make one version descend from another, and what value rule resolves the branches that remain incomparable? Correct vector arithmetic answers the first only when its history assumptions hold. The second needs its own specification, especially for deletion.