A unit test cannot establish convergence, convergence is about every possible ordering of messages. You only ever write the orderings you thought of.
In coschema, my side project, a real-time collaborative diagram editor in Angular, I test it with a deterministic simulator. It runs the real server logic and the real client over a hostile network, heals the network and compares every document byte for byte.
Randomized runs are evidence, not formal proof, hence the word “test” and not “prove”. The evidence is still strong though and one design decision made it possible: the shared document is allowed to be an invalid graph.
What the simulator runs
The simulator does not mock the sync layer. Instead it wires up the real server logic and real client code in a single process with 2 to 8 clients and puts a fake network in the middle.
The network treats messages differently, it can delay them, reorder them, duplicate or drop them altogether. It can also cut a client off entirely and bring it back later.
Everything random comes from one seeded generator. There is no wall clock or real socket. Given the same seed the same run occurs again, step for step.
The network itself is small. This is a sketch of the idea not the repository code:
class FlakyNetwork {
private queue: Packet[] = [];
private now = 0;
constructor(private rng: Rng, private faults: Faults) {}
send(packet: Packet): void {
if (this.rng.chance(this.faults.drop)) return;
const copies = this.rng.chance(this.faults.duplicate) ? 2 : 1;
for (let i = 0; i < copies; i++) {
const at = this.now + this.rng.int(this.faults.maxDelay);
this.queue.push({ ...packet, at });
}
}
tick(): Packet[] {
this.now++;
const due = this.queue.filter((p) => p.at <= this.now);
this.queue = this.queue.filter((p) => p.at > this.now);
return due.sort((a, b) => a.at - b.at);
}
}
Reordering needs no special feature. Two packets get different random delays, so the later one can arrive first.
Heal, then compare bytes
A random run has two phases. First the clients make edits while the network misbehaves: moving nodes, editing labels, connecting edges, deleting nodes, going offline and coming back.
Then the faults stop. Cut-off clients reconnect, the network runs until nothing is in flight, and every document is encoded and compared.
function runScenario(seed: number): void {
const rng = createRng(seed);
const server = new RealServer();
const net = new FlakyNetwork(rng, chaosFaults);
const clients = Array.from(
{ length: rng.between(2, 8) },
() => new RealClient(server, net)
);
for (const step of randomSteps(rng, clients)) step();
net.heal();
clients.forEach((c) => c.reconnect());
net.drain();
const reference = server.encodeState();
for (const client of clients) {
if (!bytesEqual(client.encodeState(), reference)) {
throw new Error(`diverged, seed ${seed}`);
}
}
}
I compare bytes on purpose. Comparing the rendered diagram can hide a difference that only shows up later, when the next edit touches the part that was already different. The encoded state leaves nothing to interpret.
A failing run prints its seed, and that seed replays exactly. A divergence that would otherwise arrive as a flaky bug report from a customer becomes a command I can run in a debugger.
Why the invalid graph made this possible
A diagram graph can become invalid without anyone doing anything wrong. One person connects an edge to a node while another person deletes that node. Both operations are legal on their own machines but merged results in an edge pointing at nothing.
The obvious fix is to repair it, whoever encounters the dangling edge should delete it. I decided against that in ADR 0007. The shared document is allowed to be in this invalid state while a derived read-only view hides it.
function visibleEdges(doc: DiagramDoc): Edge[] {
return doc.edges.filter(
(edge) => doc.nodes.has(edge.from) && doc.nodes.has(edge.to)
);
}
No client repairs anything. Merging stays a pure merge, so the simulator only has to answer one question: did every replica receive the same set of updates and merge them to the same state?
The y-protocols layer underneath is built for exactly that. My code adds no writes upon it that depend upon what a client happened to see.
What repair would have cost the test
Suppose every client also repaired dangling edges as it saw them. Now a merge triggers an edit, and that edit gets broadcast.
Two clients see the same dangling edge at the same moment and both delete it. Or one repairs it while a third client still offline reconnects an edge to a new node with the same role. The state after healing clearly depends upon who did what repair, and in what order.
That is a repair storm, and one that hurts production as well as the test. Such a run would not go quiet following healing, there would be ongoing traffic from repairs. There would be no clean moment for the byte comparison to happen, and failure is likewise hard to pin on network or repair logic.
With validity decided at read time there’s nothing to pin. If the documents end up differing after healing it’s because the transport or merge operation was wrong. That’s a short list of suspects.
The same idea surfaces within the undo design. Each client features its own undo manager limited to local changes, a drag is one undo step. Undoing my move does not likewise revert some later label edit performed by another client, because the undo stack never reaches into remote history (ADR 0008).
What ordinary unit tests miss
I still write unit tests for each piece, the derived view, the undo steps, the encoding. They are fast and they point at the exact line.
A unit test encodes the author's story of what happens. Client A sends, client B receives, B sends back. I wrote that story so I wrote the code to survive it.
The simulator tells stories I would not write. An update comes twice and the second copy follows a later edit. A client gets cut off mid-batch. A dropped message only gets repaired when a different client reconnects.
It also tests the seams. The bugs I expect in a sync system live between server and client, what one side assumes about the other. Both are the real code so the assumptions get tested against each other not against a mock I wrote to agree with me.
The limit is coverage. A simulator finds the bugs its fault model can express, and a seed that passes says nothing about seeds I did not run. If the fault model misses a kind of failure, the simulator remains silent. So finding a new kind of failure in the wild means the first job is teaching the network to produce it.
The repository is at https://github.com/adiyy2001/coschema if you want to read the real version of any of this. The decision is written up in ADR 0012.
Make convergence a property of the merge
To test convergence, first make it a property of the merge and nothing else. Every reactive write a client makes after a merge is one more thing your test has to explain.
Then build the test around a seed. Use one generator, no wall clock, the real code on both sides, a hostile network, a heal step and a byte comparison at the end. Print the seed when it fails.
Allowing the invalid state in the document looked like a concession when I made the decision. It turned out to be what made the whole system checkable.
Top comments (2)
Convergence is the property byte equality can prove, but it can't tell you the replicas converged to the right thing. A merge that dropped every concurrent edit would pass every seed. Worth adding one intention check beside the byte comparison: track in the harness which nodes were added and never deleted by any client, and assert they are in the healed document (and that anything deleted by someone and never re-added is gone). That catches "converged to a lossy state", which the bytes can't.
On "passing seeds are evidence": with zero failures in N independent seeds, the 95% upper bound on the per-run failure rate is about 3/N (rule of three), so 1,000 seeds only rules out a divergence that hits more than ~0.3% of runs. Rare interleavings with 2 to 8 clients and several fault types can sit below that, so it's worth logging how often each fault actually fired together in a run (duplicate arriving after a later edit, cut-off mid-batch) and biasing the generator toward the combinations that fired least.
Do you shrink a failing seed (fewer clients, fewer steps) before debugging it, or replay it as is?
That’s a good score. Byte equality between replicas means they are equal but not necessarily the right equal. There are more invariants in the harness than there are in the post. For example, the update log written must replay to the hub state, the store must match the derived graph, presence must converge, etc. All of these are still some form of all agree. None of these, however, use intent. So a merge that silently drops some updates from other clients would be fine.
I’ll incorporate your oracle idea. Nodes added by a client and not deleted by any client should survive the heal. Nodes deleted and never re-added should not exist after the heal. For edges there is one more constraint. Because of design (ADR 0007) edges to deleted nodes will still exist in the document but be hidden. So the edge constraint should be applied to the derived graph. The edge should not be deleted and both of its endpoints should exist.
I also agree on the rule of three. The run stats track how many times each type of failure (duplicates, drops, partitions, reconnects) happens but not how many times specific failures co-occur in a particular run. So it is currently not possible to know if “a duplicate lands after a later edit” happened 5 times or 5,000 times. I think it would be more useful to track co-occurrences per run and bias the generator towards the rare co-occurrences with the remaining 1,000 seeds rather than just more runs.
For shrinking: both. In the property test fast-check is used and on failure the test is shrunk by reducing the number of clients and number of steps. A replay command is printed on failure. In the seed sweep (pnpm sim --seeds N) failing seeds are replayed as-is with --verbose. I start with the failure from shrinking because it is much more debuggable