Commentary: vector-clock-crdt

Two replicated sets, both convergent. Gossip 60× harder and one goes 1.960 wrong elements to 0.130, while the other reads 1.280 on every single row — the same set, per trace, on 200 of 200 traces. A study guide for crdt.py.

cd vector-clock-crdt
python3 demo.py       # the aha (§6), about 7 seconds
python3 test_crdt.py  # pins every number this page claims, about 30 seconds

1. Orientation

This toy is a replicated set, built twice. Both copies accept writes on any replica with no coordination, both merge by absorbing another replica's whole state, and both are guaranteed to end up agreeing. They differ in one place: what they consult to decide a conflict.

The OR-Set stamps every operation with a dot — a (replica_id, counter) pair — and keeps a per-replica vector clock of the dots it has observed. At merge time it asks a question about the network: did you ever see this assertion? The LWW store keeps no dots and no vector clock. It asks a question about a wall clock: is your timestamp bigger than mine?

The backlog entry for this toy promised the standard CRDT demonstration — two replicas write concurrently, merge, and converge without a coordinator. That is true, and it is worthless as a lesson, because it is the definition of a CRDT rather than a consequence of one. It confirmed on every run of every experiment on this page, including the runs where the merge rule was deliberately broken. A claim that survives breaking the mechanism is not teaching the mechanism.

So the toy measures something else: distance from the answer one machine would hold if it applied the same operations in the same order. Under that metric, with three replicas gossiping at random and every replica's clock skewed by a random amount:

• gossiping 60× harder takes the OR-Set from 1.960 wrong elements to 0.130, and takes the LWW store from 1.280 to 1.280;
• the LWW store's final value is not merely flat on average — it is literally the same set, per trace, on 200 of 200 traces, at every gossip rate and every sync schedule tried;
• every replica agreed with every other replica in every one of those runs.

Syncing harder cannot make a last-write-wins store more correct. Not by one element. The vector clock is what makes communication worth anything.

By the end you should be able to:

• compute, by hand, whether two operations on two replicas are concurrent, from their dots and the replicas' vector clocks — and say what that has to do with what time it is (nothing);
• state the one line in merge that lets the structure delete anything at all, and predict what the set becomes without it;
• explain why a system whose conflicts are decided by timestamp gets no benefit from a faster network, and what it does benefit from instead;
• name the two boundary conditions at which each structure's advantage disappears entirely, and locate your own system between them.

2. The problem this mechanism exists to solve

You have the same logical set on three machines. Any of them may accept a write while partitioned from the others. Nobody may block waiting for a quorum, because the whole point of the design was to keep taking writes when the network is down. Sooner or later two replicas that have diverged must be put back together, and something has to decide what happens when replica A says "x is in the set" and replica B says "x was removed."

The obvious answer is to ask which happened later. Attach a timestamp to every write, and on merge keep the one with the bigger number. This is what Cassandra does, what Riak does when allow_mult is false, and what almost every "eventually consistent" store reaches for first. It is genuinely excellent engineering: it is O(1) metadata per key, it needs no history, and it converges trivially, because max is commutative, associative and idempotent no matter what order the merges happen in.

It has one property that is easy to state and hard to feel: it decides conflicts using a number that has nothing to do with the conflict. Two clocks that disagree by more than the gap between the two operations will order them backwards, and no amount of subsequent communication changes the answer, because the answer was fully determined the moment the timestamps were written.

The alternative is to stop asking when and start asking whether — whether the replica that issued the delete had already observed the add. That question is answerable exactly, with no clock at all, if every operation carries a unique id and every replica remembers which ids it has seen. Two operations are concurrent precisely when neither replica had seen the other's id. When they are concurrent there is no correct answer, only a policy — and the whole value of the machinery is that it tells you which conflicts are real, so you only apply the policy where you have to.

The competing goals, and the reason more than one design ships in production:

• Writes want to be cheap. Every operation minting a globally unique id, and every replica carrying a vector over all replicas, is metadata that a timestamp does not need. Measured below: 213.1 bytes against 131.1 at the same workload, and 453.9 when replicas stay apart longer.
• Merges want to be exact. A timestamp comparison is one integer compare; the causal test is a lookup per assertion against the other side's vector clock, and the number of surviving assertions grows with how concurrent your workload actually is.
• Operators want the answer not to depend on NTP. This is the goal that gets sacrificed silently, because the failure is invisible: nothing errors, nothing diverges, everything converges, and a write is simply gone.

3. Background you need

None of this is deep, but everything below leans on it.

The two that carry the result are the first and the last. Happened-before is a relation between events, established by message passing, and it is decidable exactly — which is why the OR-Set's error responds to gossip. Clock skew is a property of hardware, and no message can fix it — which is why the LWW store's error does not respond to anything. Everything on this page is that one contrast, measured.

4. The mental model

Before any code. Three pictures: what a replica holds, what merge decides, and what the two structures are actually asking.

A replica is a vector clock plus a bag of surviving assertions, each tagged with the dot that minted it:

cc is a summary: {2: 7} means "I have seen every one of r2's operations from 1 through 7", which is only meaningful because a replica issues its dots in order and never skips. That compression is the entire reason a vector clock is small.

Now the merge. For each dot the local replica holds, there are exactly three cases, and the middle one is the mechanism:

The second and third lines are the same observation from opposite sides: absence only means something if you can prove the other side once had it. That proof is what the vector clock is for. Take it away and every absence looks like ignorance, so nothing is ever deleted — measured in §5.4.

Finally, the two structures asking about the same pair of operations. This is the toy in one picture:

Three things fall out of that picture, and they are the whole toy:

• The OR-Set's answer is a function of the operations and the message schedule. Change the schedule and the answer changes — 186 of 200 traces in §6.4.
• The LWW store's answer is a function of the operations and the clocks. The message schedule appears nowhere in it, so changing the schedule cannot change the answer — 0 of 200 traces.
• Both are perfectly convergent. Convergence constrains replicas to agree with each other. It says nothing whatever about agreeing with what you asked for.

5. Reading the source

crdt.py is 233 lines (raw wc -l). Read it in this order: the policy function, then how an operation is recorded, then the two lines that decide everything, then the structure being argued with.

5.1 present — three policies, one line each

def present(assertions, policy):
    """Is the element in the set? `assertions` is {dot: (label, ts)}."""
    if not assertions:
        return False
    if policy == "add-wins":
        return any(lbl == "add" for lbl, _ in assertions.values())
    if policy == "rm-wins":
        return all(lbl == "add" for lbl, _ in assertions.values())
    if policy == "lww":
        # Highest timestamp wins, ties broken by dot so it stays deterministic.
        _, (lbl, _) = max(assertions.items(), key=lambda kv: (kv[1][1], kv[0]))
        return lbl == "add"
    raise ValueError(policy)

This function only ever sees assertions that merge has already decided are concurrent. That is the division of labour worth taking away from this toy: the vector clock finds the genuine conflicts, and the policy is a tiebreak applied only to those. any versus all is the entire difference between add-wins and remove-wins semantics.

The policy is a business decision dressed as a data structure. It is also completely invisible until there is concurrency to apply it to — at sync_every=1, add-wins and rm-wins produce identical values on 200 of 200 traces, and at sync_every=40 they differ on 200 of 200 (§6.5).

Note the third policy exists to make a point rather than to be used: lww puts a timestamp comparison inside the CRDT, which is what a real LWW-Element-Set does. It is not the same thing as PureLWW, because it only consults the clock for assertions that are actually concurrent. At sync_every=1 it is exactly right on every trace — there is never more than one surviving assertion, so the clock is never read.

5.2 _assert — minting a dot, and superseding what you can see

    def __init__(self, rid, policy="add-wins", supersede=True, causal_merge=True):
        self.rid = rid
        self.policy = policy
        self.supersede = supersede        # counterfactual knob, see commentary 5.5
        self.causal_merge = causal_merge  # counterfactual knob, see commentary 5.4
        self.seq = 0
        self.cc = {}   # rid -> highest counter observed from that replica
        self.el = {}   # elem -> {dot: (label, ts)}

    # ---- local operations -------------------------------------------------
    def _assert(self, elem, label, ts):
        """Mint a fresh dot and supersede everything this replica can see."""
        self.seq += 1
        dot = (self.rid, self.seq)
        self.cc[self.rid] = self.seq
        if self.supersede:
            self.el[elem] = {dot: (label, ts)}
        else:
            self.el.setdefault(elem, {})[dot] = (label, ts)

self.el[elem] = {dot: ...} — a plain assignment, throwing away every assertion this replica currently holds for the element. That looks careless and is the load-bearing half of the OR-Set: an operation supersedes exactly the assertions the issuing replica had already observed, because those are, by definition, causally before it. The ones it has not seen are untouched because they are not in self.el to touch.

add and remove differ only in the label they pass. There is no tombstone list, no separate remove-set, and no distinction in the data structure between an add and a remove — which is why a third policy costs six lines.

Two things the local write does not do, both deliberate:

• It does not read a clock. ts is a parameter. The caller supplies it, and §7.4 explains why that is a fidelity decision rather than a testing convenience.
• It does not look at any other replica. The whole write path is four statements and no coordination. That is the promise of the design; the rest of the page is about the bill.

5.3 covers — the vector clock's entire job

    def covers(self, dot):
        """Have I ever observed this dot? The vector clock's whole job."""
        return self.cc.get(dot[0], 0) >= dot[1]

Three lines, and every result on this page routes through them. .get(rid, 0) means "a replica I have never heard from covers nothing", which is the correct reading: no news is not a deletion.

>= and not >. The counter in a dot is the sequence number of the operation that minted it, so seeing "r0's operations up to 5" means dot (0,5) has been observed. I ran the off-by-one rather than reasoning about it:

0.000 → 0.495 at sync_every=1. Every replica still converges — the mistake is uniform, so everyone makes it identically. What it costs is that the most recent operation each replica knows about is treated as unseen forever, so a delete never supersedes the newest add. And look at the last column: at sync_every=120 the bug is completely inert, 2.185 either way. A replica that has observed nothing covers nothing, so an off-by-one in "how much have I observed" changes no answer at all. The same character is worth half an element at one end of the axis and exactly nothing at the other.

5.4 merge — the load-bearing line

    def merge(self, other):
        """Absorb `other`. Keep an assertion the other side lacks only if the
        other side never saw it; if it saw it and dropped it, it superseded
        it, and the drop is news."""
        merged = {}
        for elem in set(self.el) | set(other.el):
            mine = self.el.get(elem, {})
            theirs = other.el.get(elem, {})
            if not self.causal_merge:
                keep = dict(mine)
                keep.update(theirs)
            else:
                keep = {}
                for dot, v in mine.items():
                    if dot in theirs or not other.covers(dot):
                        keep[dot] = v
                for dot, v in theirs.items():
                    if dot in mine or not self.covers(dot):
                        keep[dot] = v
            if keep:
                merged[elem] = keep
        self.el = merged
        for rid, seq in other.cc.items():
            if seq > self.cc.get(rid, 0):
                self.cc[rid] = seq

if dot in theirs or not other.covers(dot) is the most load-bearing line in the file. Delete the coverage test — take the causal_merge=False branch, which makes merge a plain union of assertions — and:

At sync_every=1, 0.000 → 2.710. The structure still converges — the converged column is True on every row — and it has become grow-only. It is not approximately grow-only; at sync_every=1 the merged value is exactly the set of every element the trace ever touched, on 200 of 200 traces:

That is the sharpest single fact in the toy. Take out the vector-clock test and you still have a CRDT by every formal definition — commutative, associative, idempotent, strongly eventually consistent — and it cannot delete anything, ever. Every property the literature guarantees is intact and the data type is useless. Convergence is not the property doing the work.

Read the last column again: at sync_every=120 the line is inert, 2.185 with it and 2.185 without. If the replicas never exchange anything mid-trace, no replica covers any other replica's dots, so the coverage test never fires. The line is worth everything exactly where the toy's headline lives and nothing at the other end of the same axis — which is a useful thing to know before writing a paragraph about how essential it is.

The dot in theirs clause looks like a cheap short-circuit and is not optional. Drop it, so the rule is only not other.covers(dot):

3.290 at every schedule — and that number turns out not to be a degradation at all:

The set is empty on 200 of 200 traces, and 3.290 is simply the mean size of the correct answer. Without that clause, any assertion both replicas still hold is dropped by both of them at the first merge, because each side covers the other's dot. The structure deletes everything and converges perfectly on nothing.

The final loop is the vector clock merge: pointwise max. It runs after the assertion loop, and it has to — the loop above calls self.covers(dot), and if self.cc had already absorbed other.cc then self would claim to cover dots it learned about in this very merge, and would drop them.

5.5 supersede — what bounds the state

The second knob in __init__ turns off the local supersede, so an operation appends an assertion instead of replacing the ones it observed. From the table above: 2.710 at every schedule, including sync_every=1. Unlike the coverage test, this one is never inert; without it a replica cannot represent "I superseded that" at all, so its own history piles up and add-wins sees an add from ten operations ago forever.

It is also what bounds the metadata, measured with a real json serializer rather than a modelled byte count:

213.1 → 2419.9 bytes, 11.4×, for the same 120 operations. And note the honest cost of the whole design in the second row: the LWW store is 131.1 bytes and does not move, because its state is one triple per element and knows nothing about history. The OR-Set pays 1.63× at sync_every=1 and 3.46× when the replicas stay apart — the metadata grows with how concurrent your workload actually was, which is exactly the right shape for it to grow in, and is still a bill.

5.6 PureLWW — the structure being argued with

class PureLWW:
    """Last write wins on the timestamp alone: no dots, no vector clock."""

    def __init__(self, rid, policy="pure-lww", **_kw):
        self.rid = rid
        self.el = {}   # elem -> (ts, rid, label)

    def _assert(self, elem, label, ts):
        cand = (ts, self.rid, label)
        cur = self.el.get(elem)
        if cur is None or cand[:2] > cur[:2]:
            self.el[elem] = cand

    def add(self, elem, ts):
        self._assert(elem, "add", ts)

    def remove(self, elem, ts):
        self._assert(elem, "rm", ts)

    def merge(self, other):
        for elem, v in other.el.items():
            cur = self.el.get(elem)
            if cur is None or v[:2] > cur[:2]:
                self.el[elem] = v

    def value(self):
        return frozenset(e for e, v in self.el.items() if v[2] == "add")

27 lines against the OR-Set's 63, and it is not a strawman — it is what ships. merge and _assert are the same operation, which is the tell: a local write and a remote merge are indistinguishable to this structure. It cannot tell the difference between "I did this" and "someone told me about this", which is precisely the information the OR-Set spends its metadata to keep.

Note cand[:2] > cur[:2] — comparing (ts, rid), not ts alone. The replica-id tiebreak looks like fussiness and is load-bearing for convergence itself. With timestamps that never collide it is inert, but skew makes them collide, and then:

27 of 200 traces stop converging at skew 1 without the tiebreak. This is the one result on the page where a replica genuinely disagrees with another replica, and it took removing four characters to produce it. It is also a neat inversion of the toy's headline: the tiebreak buys the property everyone talks about (convergence) and buys nothing at all toward the property the toy measures (0.000 → 0.000 at skew 0, where it never fires).

Also worth seeing: the skew-0 row. Given a perfect clock, PureLWW is exactly right — 0.000 wrong — and the OR-Set is not. §6.6 returns to this.

5.7 run_gossip — two RNGs, and why

def run_gossip(seed, n_replicas, policy, gossip_prob, skews, n_ops=120,
               n_elems=6, p_add=0.55, rounds_at_end=60, **kw):
    """Ops and random pairwise gossip interleaved -- no sync barrier, so no
    replica is ever known to be up to date. Returns (value, converged, truth).

    Two RNGs on purpose: `orng` draws the operations and `grng` draws the
    gossip pairs, so raising `gossip_prob` cannot perturb the trace. Sharing
    one RNG here produced a fabricated result; see commentary 7.5.
    """
    orng = random.Random(seed)
    grng = random.Random(seed ^ 0x5EED)
    reps = _replicas(policy, n_replicas, **kw)
    truth = set()
    for i in range(n_ops):
        rid = orng.randrange(n_replicas)
        elem = "e%d" % orng.randrange(n_elems)
        label = "add" if orng.random() < p_add else "rm"
        op = reps[rid].add if label == "add" else reps[rid].remove
        op(elem, i + skews.get(rid, 0))

The headline needs to vary the gossip rate while holding the operations fixed, and that requires two independent streams. §7.5 is the story of what happened when they were one.

The other decision here is that gossip is one-directional: reps[a].merge(reps[b]) teaches a about b and leaves b unchanged. A replica is therefore never known to be up to date with anything, which is the honest model of anti-entropy and much less tidy than a sync barrier. The headline survives it.

6. The demo, and what it proves

python3 demo.py runs five scenarios. Together they make one argument.

6.1 One trace, three sync schedules

Sixteen operations, three replicas, five elements, replica 0's clock nine ticks fast. The same operations are replayed at three sync schedules.

The OR-Set column moves with the network: perfect when the replicas talk after every operation, three elements wrong when they never talk until the end. The LWW column is {e2, e4} three times. Six runs, all three replicas agreeing in every one.

This trace is not cherry-picked for the shape, only for being short. Searching the first 2000 seeds at these parameters, 774 of 2000 produce the same qualitative pattern — LWW identical at all three schedules and wrong, OR-Set exact at sync_every=1 and wrong at 16 — and seed 0 is simply the first.

6.2 Deriving both wrong answers

Neither number is a mystery. demo.py derives them.

r0 adds e4 at tick 3, and its clock is 9 fast, so the write is stamped 12. r1 removes e4 at tick 5 and stamps it 5. The delete happened later in every meaningful sense — later in real time, later in the trace, and issued by a replica that had already been told about the add, because this row is the sync-after-every-operation row. It loses anyway, 12 > 5.

The threshold is exactly where arithmetic says: the add is at t=3 and the delete at t=5, so the add needs +3 ticks to overtake. Skews 0, 1 and 2 leave e4 correctly absent; skew 3 flips it. One tick of clock error is worth exactly one operation of ordering.

The OR-Set's error has an entirely different shape:

The last two operations on e0 are r2 add at t=13 and r1 rm at t=14 — one tick apart, on different replicas. At sync_every=1 and sync_every=2, r1 has already merged r2's add when it issues the remove, so the remove's dot supersedes it and e0 is correctly absent. At sync_every=4 the two land in the same window, neither replica has seen the other, they are genuinely concurrent, and add-wins keeps e0. No clock is involved in that flip at all — the same operations, the same timestamps, a different message schedule, a different answer.

6.3 The headline

Now the same contrast at scale, on a much less tidy network: three replicas, six elements, 120 operations, 200 seeds, random pairwise gossip rather than a sync barrier, and a random per-replica clock skew drawn from {0, 3, 7, 25, 100}.

Read the two middle columns. Going from 0.05 exchanges per operation to 3.00 is 60× more gossip, and it takes the OR-Set from 1.960 wrong elements to 0.130 — a 15.1× improvement. From no mid-trace gossip at all to 3.00 it is 2.185 → 0.130, 16.8×. The LWW store reads 1.280 on every row, and the count of traces it gets exactly right is the same 56 of 200 on every row.

converged is True on every row of that table, for both structures. Sixty times the network traffic, and the last-write-wins store is not one element better. It is not a matter of the mean, either — checked per trace:

Not "the same number of traces" — the same traces, seed for seed. And where the OR-Set's exact-answer count goes:

14/200 → 179/200 against 56/200 → 56/200. That is the toy.

It is not an artefact of three replicas. At five (c1_headline.py):

Same shape: one column moves 5.1×, the other is flat to three decimal places and holds the same 26 traces exactly right throughout.

The honest counter-column. The OR-Set is not simply better, and the last column of the demo table says so. Splitting each structure's error by direction:

The OR-Set's false-absent count is 0.000 at every gossip rate. It never loses an add — not once in 1200 traces. Every error it makes is a resurrection: an element the user deleted coming back because the delete was concurrent with an add. Gossip shrinks that error toward zero. (This is the same failure lsm-tree studies from the storage side, where dropping tombstones during a partial merge hands back a deleted key. It is a real hazard and it is not this toy's headline.)

The LWW store's error is half deletion. It silently discards 0.615 adds per trace, and 60× more gossip recovers exactly none of them. Which failure is worse is a question about your application — a resurrected item in a shopping cart versus a payment that vanished — but only one of the two is a knob you can turn.

6.4 Why the LWW column cannot move

The flatness is not a statistical accident, and it has a closed form. With replica 0's clock far enough ahead, replica 0's last operation on an element always wins. So an element is wrong exactly when the trace's last operation on it was not replica 0's and replica 0's last operation on it carried the other label. With 3 replicas and P(add) = 0.55:

6 × 2/3 × 0.495 = 1.9800 predicted, 1.9800 measured. And the prediction is not just right on the mean: applied per trace as "replica 0's last operation on the element wins, else the last operation by anyone", it names the exact final set on 200 of 200 traces (c2_invariance.py).

Look at what is in that formula and what is not. Element count, operation distribution, replica count, clock skew. The network appears nowhere. That is the proof of the headline, and it is stronger than the measurement: the converged value of a pure-LWW store is a function of the operations and the clocks alone, so there is no message schedule that could have changed it. Which is why the sweep runs from "sync after every single operation" to "sync once at the very end" — nine schedules spanning the entire axis — and the value is literally identical on 200 of 200 traces, while the OR-Set's value changes on 186 of 200.

6.5 Three policies, three converged sets

At sync_every=1 the choice of conflict policy is unobservable — add-wins, rm-wins and lww produce the identical set on all 200 traces. At sync_every=40 they differ on all 200, and on 168 of them all three land on three different sets. Every one of those runs converged.

That is the practical lesson hiding behind the formalism: the policy argument your team is having is an argument about a code path that does not execute until there is a partition. It cannot be tested by a healthy cluster.

6.6 The boundary conditions — where each effect vanishes

Both effects have a clean edge, and they are at opposite ends of different axes.

The LWW store's disadvantage vanishes with a good clock. Operations are one tick apart in this trace, so the question is how the skew compares to the inter-operation interval:

At skew 0 and skew 1 it is exactly right on 200 of 200 traces. Below one operation-interval of clock error, last-write-wins is not an approximation of the sequential answer — it is the sequential answer, at a fraction of the metadata. And in that regime the CRDT is the strictly worse structure. The control run in c1_headline.py, same gossip sweep with every clock perfect:

LWW is perfect at every gossip rate; the OR-Set is wrong at every gossip rate. The CRDT's entire error is the price of refusing to trust a clock. If your clock is genuinely good relative to how often the same key is contended, you are paying that price for nothing.

The OR-Set's advantage vanishes with zero concurrency:

Exactly right on 200 of 200 at sync_every=1, and — from §6.5 — the policy choice is invisible there too. If nothing is ever concurrent, the OR-Set's machinery is metadata you are paying for and never using.

The two degrade at almost the same rate against their own resource. Window 2, 3, 4: LWW 0.135 / 0.200 / 0.310 against OR-Set 0.095 / 0.180 / 0.290. One tick of clock error is worth about one operation of sync delay, which is the intuition to carry out of this page. The question for your own system is not "CRDT or LWW", it is which of those two quantities you can bound more tightly: the skew between your clocks, or the delay between your replicas.

6.7 The tests

Every headline number on this page is asserted by one of these, so the page cannot rot quietly: test_gossip_moves_the_orset_and_not_the_lww_store pins the 16.8× and the 15.1× and the flat (1.280, 56) at four gossip rates; test_without_covers_the_set_can_never_delete pins the 200/200 grow-only result; test_lww_value_is_identical_across_nine_sync_schedules pins the 186-versus-0.

7. Design decisions and roads not taken

7.1 The metric, and the objection to it

Everything on this page rests on one choice: correct means matching what one machine would hold if it applied the same operations in the same order. It deserves defending rather than assuming, because a CRDT purist will object, and the objection is not silly.

That is right, and this page does not dispute it. The formal claim is true and both structures satisfy it. The measurement is a different claim.

The answer, in three parts.

First: the metric is not chosen to embarrass the CRDT. It embarrasses the CRDT more than it embarrasses the LWW store at low gossip rates — 2.185 against 1.280 — and at skew 0 it says the CRDT is worse at every gossip rate while the LWW store is perfect (§6.6). A metric rigged against timestamps would not produce that control table. What it measures is a real, directional quantity that both structures can be scored on.

Second: "no fact of the matter" is a claim about the operations, and the metric is applied to a whole trace. Most of the operations in these traces are not concurrent with anything; they are separated by many ticks and many messages. The single-node answer is only a fiction for the genuinely concurrent subset, and the toy quantifies exactly that subset: at sync_every=1 the OR-Set matches the sequential answer on 200 of 200 traces (§6.6), which is only possible because the metric and the formalism agree completely whenever there is no concurrency. The disagreement between them is confined precisely to the conflicts, which is where it should be.

Third, and this is the real defence: the user has the metric whether or not the formalism licenses it. Somebody clicked "remove from cart" and expects the item gone. They do not know what a lattice is, and "your replicas agree" is not responsive to their complaint. §6.3 splits that complaint by direction — 0.615 adds per trace silently discarded by the LWW store — and no amount of convergence answers it.

The strongest version of the argument is the §5.4 counterfactual, which needs no metric at all. Remove the coverage test and you still have a CRDT by every formal definition — commutative, associative, idempotent, strongly eventually consistent — and its value is exactly "every element ever touched" on 200 of 200 traces. It can never delete anything. If the formal property were the property that mattered, that structure would be as good as the real one. The formalism cannot tell them apart. The metric can, which is the argument for having one.

What a fair reading concedes: at low gossip rates the OR-Set's 2.185 is not a bug, it is the add-wins policy doing what it says. The number to read is not the level, it is the slope — and the slope is the entire result.

7.2 Why keep rm-wins

It costs six lines (one all instead of one any) and it buys the §6.5 result: three policies, three converged sets, and the choice between them invisible until there is a partition — 0/200 at sync_every=1 against 200/200 at 40. With only one policy the reader could reasonably conclude that a CRDT has the answer for a concurrent add and remove. It does not. It has a correctly-identified conflict and a policy you chose, and the toy should show the policy being chosen.

7.3 Why a state-based CRDT, and one-directional gossip

State-based (convergent) rather than operation-based: merge takes a whole replica, so the transport needs no delivery guarantees at all. Duplicate a message and merge is idempotent; reorder them and it is commutative; drop one and the next merge carries the same information. That is why this page has no message-loss experiment — for a state-based CRDT, loss is indistinguishable from delay, so the gossip-rate axis already measures it. test_merge_is_idempotent_and_commutative asserts the property directly.

Gossip is one-directional on purpose (§5.7). A sync barrier is a nicer picture and a worse model: it creates instants at which every replica is up to date, and a reader could suspect the result depends on them. Random ordered pairs mean no replica is ever known to be current, and the headline is unchanged.

7.4 Why every timestamp is a parameter

There is no time.time() in this file. ts is passed in by the caller, and clock skew is an explicit integer offset. That is not a testing hack retrofitted for determinism — it is the honest interface, because a timestamp in a distributed store is an input to the algorithm, not a property of the universe. Making it a parameter forces the question the toy is about: whose clock, and how wrong is it?

The payoff is that the boundary is observable instead of a coin flip. §6.2 shows e4 flipping at exactly skew 3, because the add is at t=3 and the delete at t=5. With a real clock that transition would be a flaky test. test_demo_output_is_byte_identical_across_runs runs demo.py twice and asserts the strings match — 200-seed sweeps, random gossip, random skews, and byte-identical output.

7.5 The near-miss: one RNG, and a result that was not there

This is the most useful thing that happened while building the toy, and it is a warning about a failure mode that no amount of re-reading catches.

The first version of the gossip experiment drew the operation trace and the gossip schedule from a single seeded RNG. It produced a clean, plausible, completely fabricated result: more gossip made the LWW store worse. There was a monotone trend, it held across seeds, and it had a tidy just-so explanation ready — more merges, more chances for a skewed write to propagate.

It was an artefact. Raising the gossip rate consumed more numbers from the shared stream, which shifted every subsequent draw, which changed which operations happened. The two columns were not the same workload at two gossip rates; they were two different workloads. The "trend" was the difference between unrelated traces.

What makes this worth a section is that the bug was invisible from every direction that usually works. The code was short and correct-looking. The experiment was seeded and reproducible — byte-identical on every run, which feels like rigour and is orthogonal to it. The result was directionally plausible and had a mechanism. Nothing about re-reading the code would have surfaced it.

What surfaced it was the control that should have been there from the start: hold the operations fixed and check that they are, in fact, fixed. With orng and grng separated, the fabricated trend vanished and the real result appeared in its place — the LWW column is flat, which is a much stronger claim than the fake one, and the fake one was actively hiding it.

The lesson generalises past RNGs: when a knob is supposed to vary one thing, assert that it varies only that thing. The shipped run_gossip carries the two-RNG comment (§5.7) so the next person cannot quietly recombine them, and test_gossip_moves_the_orset_and_not_the_lww_store pins the flat column at four rates, which would fail immediately if the streams were ever merged.

7.6 What is deliberately absent

• Delta-CRDTs and a real anti-entropy protocol. Shipping whole replica states is O(state) per exchange; production systems ship deltas. It is a transport optimisation that changes none of the semantics measured here.
• Causal-context compaction and tombstone GC. §5.5 measures the state growing 213.1 → 453.9 bytes as replicas stay apart; the real answer is interval-compressing the causal context and retiring dead replica ids. Both are more code than the entire toy.
• G-Counters, PN-Counters, registers, maps. One mechanism per toy.
• A wire format. merge takes a Python object. The §5.5 byte counts use json.dumps on a canonicalised structure to get an honest-ish ratio, not to propose a protocol.

8. What's simplified vs. the real thing

Replica ids are small integers and live forever. cc is a dict keyed by replica id, and a real deployment adds and removes nodes constantly. Every retired node's entry stays in every vector clock forever unless something retires it, which is a genuinely hard problem — you cannot drop an entry without risking treating an old dot as unseen, which §5.3 shows resurrects data. Riak's dotted version vectors exist substantially to bound this growth; production systems bound it by keying the causal context on coordinating replicas rather than all replicas.

The causal context is exact and unbounded. covers is a single integer comparison because a replica's dots arrive in order. Real anti-entropy delivers out of order, so the context is a set of intervals per replica, not a single high-water mark, and compaction of those intervals is a real subsystem.

No concurrency. Everything is single-threaded, and merge mutates self.el in place. A real replica takes merges from several peers while serving local writes; the read-modify-write in merge would need a lock or an immutable-state swap. This toy would be a data race in production and the mechanism it teaches would be identical.

No persistence, no failure, no partial merges. A replica that crashes mid-merge, in this toy, does not exist.

The metric needs a global observer. sequential(trace) computes the single-node answer by looking at every operation on every replica in one place. No participant in a real system can do that — which is exactly why the error this page measures is invisible in production. Nothing logs it, nothing alerts on it, every replica agrees, and every health check is green. That is worth sitting with: the failure mode being measured here is one that a real deployment has no instrument for.

Determinism is load-bearing for the write-up, not the mechanism. Timestamps are caller-supplied and two RNGs are separated (§7.5). A real system reads a clock and gets whatever NTP last told it. The toy makes clock error a dial so that §6.6's boundary is a table instead of an anecdote; production makes it an unknown, which is the whole problem.

One element, one key, no values. A real LWW store resolves conflicts per field, and a real CRDT set holds values with their own conflict rules. The toy's elements are opaque strings, which keeps the question to "in or out".

9. Check yourself

Answer before expanding. Every answer is derivable from the source or from a transcript above, and every one below was verified by running it.

10. Further reading

Every link below was fetched and confirmed live when this was written.

• Bieniusa, Zawirski, Preguiça, Shapiro, Baquero, Balegas & Duarte: An optimized conflict-free replicated set — the paper this toy implements. The optimisation is exactly _assert's supersede-on-write plus the causal-context test in merge, which is what removes the tombstones an unoptimised OR-Set needs. Read it for "permutation equivalence", their framework for saying what concurrent operations ought to do — the formal version of §6.5's argument that the policy is a choice.
• Jepsen: Cassandra — the production case study for this page's headline. "Early in Cassandra's history, Cassandra chose not to implement vector clocks for performance reasons... The downside is that there is no safe way to modify a Cassandra cell." Then the empirical part: a millisecond clock padded to microseconds, timestamp collisions, and roughly 1% of writes silently lost. This is §6.3's 0.615 discarded adds per trace, in a real cluster.
• Riak: Causal Context — vector clocks and dotted version vectors as an operator-facing feature, plus the allow_mult switch that turns this toy's OR-Set into this toy's PureLWW: with it off, "Riak resolves the values on the basis of timestamps." The docs recommend always setting it to true, which is §6.3's argument written as an operations manual.
• Lamport: Time, Clocks, and the Ordering of Events in a Distributed System (CACM 21(7), 1978) — where happened-before comes from, and therefore where covers() comes from. Worth reading for the framing this whole toy is a footnote to: an ordering consistent with causality is constructed from message passing, not measured from clocks.
• Preguiça, Baquero & Shapiro: Conflict-free Replicated Data Types (Encyclopedia of Big Data Technologies) — the short, precise statement of strong eventual consistency and the state-based/operation-based split. Read this to steelman §7.1's objection before reading §7.1's answer.
• crdt.tech — the paper index maintained by Kleppmann, Bieniusa and Shapiro, and the route to Shapiro, Preguiça, Baquero & Zawirski's A comprehensive study of Convergent and Commutative Replicated Data Types (INRIA RR-7506, 2011), the catalogue that defines OR-Set, 2P-Set and LWW-Register side by side.
• Almeida, Shoker & Baquero: Delta State Replicated Data Types — the answer to §7.6's first omission: "small messages with an incremental nature, as in operation-based CRDTs, disseminated over unreliable communication channels, as in traditional state-based CRDTs." If you found merge(other) shipping a whole replica implausible, this is why it is not what production does.
• Preguiça, Baquero, Almeida, Fonte & Gonçalves: Dotted Version Vectors — the fix for §8's first simplification: causal context that "grows linearly only with the number of servers that register updates for a given data element" rather than with every replica that ever existed.
• Automerge: Conflicts — a shipping CRDT stating this page's §7.1 tension in its own docs: it "picks one of the concurrently written values as the 'winner', and it ensures that this winner is the same on all nodes", where "the choice is arbitrary, but deterministic and equal across both documents". Arbitrary-but-equal is convergence; whether it is what the user wanted is a separate question, and Automerge is careful not to conflate them.
• Kleppmann: CRDTs: The Hard Parts — slides, video and an extensive bibliography. The framing to take from it is that "CRDTs are easy to implement badly": every table on this page has a converged column reading True next to a broken implementation, which is that sentence measured.