A distributed consensus implementation written from scratch, and the simulator that holds it to account: one seed reproduces an entire cluster's life — partitions, crashes, GC pauses, clock skew, packet loss — with ten safety invariants checked after every event and every client history checked for linearizability.
pure python · no dependencies · 56 tests · 13 injectable bugs · source · türkçe
The failures that matter in a replicated log need a partition to open between two specific messages, or a leader to die in the instant after it appended an entry and before it replicated it. Running a real cluster and hoping to get lucky does not find those, and on the rare occasion it does, you cannot reproduce what you saw.
So the world itself is made deterministic: one thread, a virtual clock, one seeded random stream — the approach FoundationDB, TigerBeetle and Antithesis are built on. A failing run stops being a war story and becomes a number you can replay, shrink, and put in a test suite.
A test harness that has never caught anything is an untested claim. Each row is the same implementation compiled with one deliberate protocol bug — every one of them a mistake that has shipped in a real Raft — run across four different worlds. The top row is the real code. Rates are the share of seeds in which the bug was caught.
| implementation | normal | hostile | slow | churn | 1st seed | caught by |
|---|
* figure8_commit is run without the no-op a leader appends on election: that no-op masks it · membership bugs only appear in the churn world, because only there does the configuration change
None of these were planned. Each came out of running an implementation I believed was correct across thousands of seeds — and each was fixed and then measured.
| finding | symptom | fix, measured |
|---|
Every safety invariant held over thousands of seeds. Then the liveness check began firing: on a small share of runs, no client request completed after the network healed. The trace shows two nodes taking turns unseating each other — each election carries a higher term, and a higher term forces a working leader to stand down.
Nothing there is a coding mistake; it is the algorithm as figure 2 describes it, and it is exactly why the dissertation adds pre-vote (§9.6) and leader stickiness (§4.2.3).
t=6730 node 2: candidate -> LEADER term 21 t=6757 node 0: follower -> candidate term 22 t=6770 node 2: leader -> follower term 22 t=6907 node 0: candidate -> LEADER term 22 t=6937 node 2: follower -> candidate term 23 t=6952 node 0: leader -> follower term 23 ... terms climb, nothing commits
But my first write-up of it was wrong, and the harness is what caught that. "No operation completed inside the window I chose" is not the same claim as "the cluster is down": a cluster repairing a badly diverged log can legitimately need longer than one election. So the liveness check now confirms itself — a run that looks stalled is replayed with the tail doubled, and only a cluster that is still silent is reported. With that in place, every build recovers eventually. Nothing had ever been permanently down.
The real effect is a distribution, not a yes/no — and it is worth more than the claim it replaced:
| build | runs | median | p90 | p99 | worst | over 1s |
|---|
time from the last fault healing to the cluster serving its next request · 1,000 seeds per cell · no build ever failed to recover
A follower that adopts the leader's commit index verbatim should eventually apply an
entry that gets rolled back. It never did: a conflicting append truncates the log all the
way to the end, so a divergent tail never survives long enough to be applied — one correct
mechanism masking another's bug. The cause, though, is a single comparison:
commitIndex > lastLogIndex is impossible in correct Raft. Checking that
moved detection from zero in six thousand runs to nine runs in ten.
A node that forgets its vote across a restart can vote twice in one term. Waiting for the textbook consequence means waiting for both candidates to assemble a majority — a coincidence on top of a coincidence. Watching for the double vote itself is just as sound an invariant, and finds it hundreds of seeds sooner.
When a bug survives a fuzz campaign, the instinct is to inject harder. Correlated fault bursts and leader-targeted chaos bought roughly 4× on the hardest bug here. Two new invariants — cheap, sound, four lines each — bought several orders of magnitude.
Same seeds, same faults, same world — only the read path changes. Reading through the log replicates every read like a write. ReadIndex confirms leadership with one heartbeat round and answers from the leader's own state machine. A leader lease answers with no round trip at all, for as long as the leader believes its lease holds.
A lease assumes clocks have bounded error. In this fault model a pause can also stop the clock — a suspended VM — and a leader that wakes up believes almost no time has passed:
| read path | seeds | stale reads | p50 | p99 | log/run | note |
|---|
t=1467 node 0 becomes LEADER term 2 t=1918 node 0 PAUSES — and its clock stops t=2415 node 4 becomes LEADER term 4 t=2894 node 0 wakes; by its own clock almost no time has passed, so its lease still looks valid t=3581 node 0 finally learns it was deposed
In that window the deposed leader answers reads from state that is no longer current. No internal Raft invariant can see it — the log is replicated perfectly. Only the end-to-end linearizability checker catches it.
With clock freezes disabled (--freeze 0.0) lease reads are clean in
every run. So this is not proof that leases are wrong; it is a measurement of the
assumption they rest on, and of what happens when it fails.
A campaign that never produces a snapshot install has not tested InstallSnapshot, however many seeds it burned. So every run records the interesting situations it reached:
| situation reached | runs | share |
|---|
1,600 runs across four worlds · this table has already earned its place once: "restart during election" sat at 0% because an instrumentation call had landed in the wrong place
The fuzzer reports a seed. The shrinker deletes faults and replays until only what matters is left. Then the run is drawn as a grid: who led, who was cut off, and where the committed log stopped moving.
loading…
One command turns a failure that needed twenty-one injected faults over eight seconds into a reproduction with no faults at all and 627 milliseconds — the bug was there the whole time, hiding behind ordinary message timing. The repro is a JSON file that replays identically on any machine.
UNKNOWN rather than claiming a pass