Sparkles

Appearance

Deterministic simulation testing ​

Deterministic simulation testing (DST) is the discipline of running the real program, unmodified, inside a single-threaded discrete-event simulator that owns every source of nondeterminism (scheduler, clock, random numbers, network, disk, process death) so that a random fault schedule drawn from one seed can be replayed byte-for-byte; it is the mature answer to "test a durable program by crashing it at every point", and the three systems below are its canonical practitioners.

FieldValue
Principal sourcesFoundationDB's simulator (Sim2 + Flow + BUGGIFY) and the SIGMOD 2021 paper; TigerBeetle's VOPR; Antithesis's deterministic hypervisor
AuthorsZhou, Miller, Sears, Xu, Tschannen, Leach, Shraer, Atherton, Rosenthal, Namasivayam, Beamon, Dong, Wilson, Grieser, Muppana, Collins, Liu, Su, Scherer, Moore, Yadav (paper); Apple / FoundationDB contributors (simulator); TigerBeetle, Inc. (VOPR); Antithesis (docs, blog)
Venue / yearSIGMOD 2021 (paper); apple/foundationdb at 10a002f6bc47996fb378da0fb2d93df5e0187e32 (September 9, 2026); tigerbeetle/tigerbeetle at 47aeb2212a255273dda508288412e537d11e4b7c (August 31, 2026); Antithesis docs read September 11, 2026 and the March 20, 2024 hypervisor post
DOI or URL10.1145/3448016.3457559 · author PDF · FoundationDB testing docs · TigerBeetle safety docs · How Antithesis works · Will Wilson, "Testing Distributed Systems w/ Deterministic Simulation"
Categorytheory
Grounds3 (determinism: what a runtime must own for a run to be replayable) and 8 (testing: the fault model, the oracles, seed reproduction, time compression). Touches 6 (concurrency: the scheduler as the only interleaving source). Silent on 1, 2, 4, 5, 7.

Last reviewed: September 12, 2026.

What it establishes ​

DST establishes that a program whose every nondeterministic input flows through one seam can be tested against a fault model far harsher than production, with every failure reproducible from a seed. The FoundationDB paper states the thesis in one sentence: "the real database software is run, together with randomized synthetic workloads and fault injection, in a deterministic discrete-event simulation. The harsh simulated environment quickly provokes bugs (including but not limited to distributed systems bugs) in the database, and determinism guarantees that every bug found this way can be reproduced, diagnosed, and fixed" (paper, §4). The prerequisite is architectural, not a test-harness detail: "All database code is deterministic; accordingly multithreaded concurrency is avoided (instead, one database node is deployed per core)" (§4, "Deterministic simulator"). TigerBeetle says the same in its docs: "In the simulator, all non-deterministic parts of the system are stubbed out. This includes the clock, network, and disk operations" (docs/internals/vopr.md).

The definitions that recur across the three systems:

  • Seed. One integer from which every random choice in a run derives: the cluster shape, the workload, the fault schedule, the scheduling jitter. Replaying the seed on the same binary replays the run.
  • Fault schedule. The sequence of injected faults (kills, reboots, partitions, clogs, disk corruption, delays) as a function of the seed. It is drawn, not enumerated.
  • Oracle. What decides a run failed: in-code assertions, a workload's check phase, a cluster-wide state checker, a liveness deadline.
  • Time compression. Virtual time jumps to the next scheduled event when nothing is runnable, so an hour of simulated time costs seconds of CPU. "Discrete-event simulation can run arbitrarily faster than real-time if CPU utilization within the simulation is low, as the simulator can fast-forward clock to the next event" (paper, §4, "Latency to bug discovery").
  • Crash at any point. A process may be killed between any two scheduled tasks; what its writes look like after the kill is itself a fault-model decision (FoundationDB's AsyncFileNonDurable, TigerBeetle's crash_fault_probability).

FoundationDB: Sim2, Flow and BUGGIFY ​

A note on the clone: at the pinned commit FoundationDB has finished migrating from its actor compiler to standard C++ coroutines, so the files the literature calls sim2.actor.cpp and SimulatedCluster.actor.cpp are fdbrpc/sim2.cpp and fdbserver/SimulatedCluster.cpp. flow/README.md now opens with "Flow provides asynchronous communication and cooperative scheduling using standard C++ coroutines. … Coroutine code lives in ordinary .cpp and .h files." The 2021 paper describes the earlier state ("Flow [4], a novel syntactic extension to C++ adding async/await-like concurrency primitives"); the simulator's design is unchanged by the migration.

How determinism is obtained ​

Everything runs on one OS thread inside one process, interleaved only by the simulator's task queue. Sim2::runLoop is the whole scheduler (fdbrpc/sim2.cpp, runLoop): while not stopped, if the queue can sleep it advances self->time to the next timer (plus a tiny random jitter), then drains every ready task in priority order. Ready tasks live in a std::priority_queue keyed by priority, timers in one keyed by at (flow/include/flow/TaskQueue.h, OrderedTask, DelayedTask); with a single thread and a single insertion order the pop order is a pure function of the run so far.

Randomness is a single seeded generator. flow/include/flow/DeterministicRandom.h wraps boost::random::mt19937_64 with the comment "Use boost::random::mt19937_64 to get consistent output across different compilers and therefore across different C++ standard library implementations", and flow/include/flow/IRandom.h warns at the accessor: "This generator is only deterministic if given a seed using setThreadLocalDeterministicRandomSeed". The seed comes from -s on the fdbserver command line (fdbserver/fdbserver.cpp, OPT_RANDOMSEED) and is otherwise drawn from platform::getRandomSeed() and printed ("Random seed is …").

The clock is a plain field. Sim2::now() returns time; timer() may run "up to 0.1 seconds ahead of now()" by a random increment, so code that confuses the two clocks is punished (fdbrpc/sim2.cpp, class Sim2). delay(seconds, …) enqueues a timer at now() + seconds, and with probability 0.25 first stretches seconds by MAX_BUGGIFIED_DELAY * pow(random01(), 1000.0), a heavy-tailed jitter that occasionally makes a short sleep very long.

The network is Sim2Conn plus SimClogging: per-connection delivery delays, clogPairFor(from, to, t) to hold a link, buggify() calls in Sim2Conn::write that truncate a send to a random slice of at most 1000 bytes, and rollRandomClose, which with probability 0.00001 per call fails the connection outright, all skipped when the connection is marked stable. The disk is AsyncFileNonDurable, "an async file implementation which wraps another async file and will randomly destroy sectors that it is writing when killed. This is used to simulate a power failure which prevents all written data from being persisted to disk" (fdbrpc/include/fdbrpc/AsyncFileNonDurable.h). Even deleteFile is half-durable: with probability 0.5 a non-mustBeDurable delete is logged as Sim2DeleteFileImplNonDurable and never happens.

The fault model ​

Kills are typed. fdbrpc/include/fdbrpc/SimulatorKillType.h enumerates KillInstantly, InjectFaults, FailDisk, RebootAndDelete, RebootProcessAndDelete, RebootProcessAndSwitch, Reboot, RebootProcess, None. Sim2::killProcess_internal marks the process failed, or arms per-process fault injection (fault_injection_p1 = 0.1, fault_injection_p2 = random01()), or sets failedDisk; each branch is wrapped in a CODE_PROBE so the harness can count how many runs reached it (fdbrpc/sim2.cpp). The workload that drives kills is MachineAttrition (fdbserver/workloads/MachineAttrition.cpp), with knobs reboot, killDc, killMachine, killDatahall, killProcess, killZone, killSelf, killAll.

BUGGIFY is the in-code half of the fault model. flow/include/flow/Buggify.h defines buggify(probability) as: enabled globally, and this (file, line) section was activated for this run (a per-section coin with P_GENERAL_BUGGIFIED_SECTION_ACTIVATED = 0.25, memoized in a map and traced), and a fresh random01() < probability (default P_GENERAL_BUGGIFIED_SECTION_FIRES = 0.25). The paper explains the intent: "At many places in its code-base, the simulation is given the opportunity to inject some unusual (but not contract-breaking) behavior such as unnecessarily returning an error from an operation that usually succeeds, injecting a delay in an operation that is usually fast, choosing an unusual value for a tuning parameter, etc." (paper, §4, "Fault injection"). The two-level coin is swarm testing: each run enables "a different random subset of buggification points", so that runs differ in which rare paths are hot, not only in when.

A test is a TOML file composing workloads. tests/fast/CycleTest.toml stacks Cycle (2500 transactions/s for 10 s) with RandomClogging, Rollback and two Attrition workloads (machinesToKill = 10, machinesToLeave = 3, reboot = true), then a second, unclogged phase. Restart tests are pairs: ConfigureTestRestart-1.toml ends with a SaveAndKill workload writing simfdb/restartInfo.ini, and ConfigureTestRestart-2.toml resumes the same cluster from disk with runSetup=false, which is how an upgrade across binaries is simulated: crash, then come back with different code.

What is checked ​

The paper lists the oracles: workloads "have assertions built in to verify the contracts and properties of the database (for example, by checking invariants in their data that can only be maintained through transaction atomicity and isolation)"; code-level assertions check what is "verified 'locally'"; and recoverability "can be checked by returning the modeled hardware environment … to a state in which recovery should be possible and verifying that the cluster eventually recovers" (paper, §4, "Test oracles"). Concretely, every workload has a check phase: CycleWorkload::check reads the whole ring in one transaction and cycleCheckData emits a SevError TestFailure trace if the ring is broken (fdbserver/workloads/Cycle.cpp). The run's exit code is derived from the count of SevError events logged (fdbserver/fdbserver.cpp, CountEventsLoggedAt(SevError)).

Reproduction ​

A failing run is -s <seed> -b on plus the test file. Two runs of the same seed must also agree on the unseed: at the end of a simulation fdbserver draws one more random number and prints "Unseed: N" (fdbserver/fdbserver.cpp). If a change introduces nondeterminism anywhere, the unseed diverges between runs of the same seed and the harness flags it before any bug is hunted. The paper's §6.2 records why this matters: "Adding additional logging, for instance, generally does not affect the deterministic ordering of events, so an exact reproduction is guaranteed."

Time compression and scale ​

The docs report "about a 10-1 factor of real-to-simulated time" and "roughly one trillion CPU-hours of simulation" (FoundationDB testing docs). The same page names the fault pattern that found the most bugs, swizzle-clogging: "you first pick a random subset of nodes in the cluster. Then, you 'clog' (stop) each of their network connections one by one over a few seconds. Finally, you unclog them in a random order, again one by one, until they are all up."

TigerBeetle: the VOPR ​

TigerBeetle's simulator, the Viewstamped Operation Replicator, is src/vopr.zig over the test cluster in src/testing/cluster.zig. Its docs make the reproducibility contract explicit: "Because our simulator is deterministic based on a seed number and the Git commit, we can perfectly reproduce any bugs discovered in testing for easy local debugging. Crucially, VOPR can speed up time arbitrarily. One minute of VOPR time is equivalent to days of real-world testing" (docs/internals/vopr.md).

How determinism is obtained ​

There is no scheduler to seed because there are no tasks: the whole cluster is ticked. Simulator.tick calls cluster.tick(), then tick_requests, tick_upgrade, tick_crash, tick_pause in fixed order (src/vopr.zig); Cluster.tick interleaves storage and network steps "to allow for faster-than-a-tick IO" (src/testing/cluster.zig). Every replica's I/O is an in-memory double that completes on a later tick. The clock is src/testing/time.zig, whose TimeSim has a resolution per tick and an OffsetType of linear, periodic, step or non_ideal, so replicas drift relative to each other by a seeded formula. The network is src/testing/packet_simulator.zig with one_way_delay_mean, packet_loss_probability, packet_replay_probability, partition_mode and partition_symmetry. The disk is src/testing/storage.zig, "In-memory storage, with simulated faults and latency", with read_fault_probability, write_fault_probability, write_misdirect_probability and crash_fault_probability.

The seed is parsed from --seed or drawn from std.crypto.random; stdx.PRNG.from_seed(seed) (src/stdx/prng.zig) then generates every option: options_swarm draws cluster shape, packet_loss_probability = ratio(prng.int_inclusive(u8, 30), 100), partition probabilities and stabilities, storage latencies and fault ratios, and separate sub-seeds for the cluster, network and storage doubles (src/vopr.zig, options_swarm). When no seed is given the binary refuses Debug builds ("no seed provided: the simulator must be run with -OReleaseSafe"), because unseeded runs are for throughput, seeded ones for debugging.

The fault model ​

A crash is one tick's coin toss. tick_crash_up takes replica_crash_probability (ratio(2, 10_000_000) per tick in swarm mode), multiplies it by ten if the replica has writes in flight, and on success calls cluster.replica_crash (src/vopr.zig). That function is short and is the whole "what does a crash mean" model (src/testing/cluster.zig, replica_crash):

zig
// Reset the storage before the replica so that pending writes can (partially) finish.
cluster.storages[replica_index].reset();

cluster.replicas[replica_index].deinit(cluster.allocator);
cluster.network.process_disable(.{ .replica = replica_index });
cluster.replica_health[replica_index] = .down;

Storage.reset walks the pending writes and, with crash_fault_probability (drawn from 80 to 100 percent in swarm mode), corrupts one random sector each write targeted (src/testing/storage.zig, reset). The storage doc comment bounds this per zone so the cluster can always repair: "One read/write fault is permitted per area … An additional fault is permitted at the target of a pending write during a crash." Restarts follow a replica_restart_probability; there are also pause/unpause, reformat and release-upgrade faults, all ticked from the same seed.

What is checked ​

Three layers. First, the thousands of assertions in production code, which stay on in release builds (docs/internals/vopr.md: "it is far better to stop operating than to continue operating in an incorrect state"). Second, the cluster-wide StateChecker (src/testing/cluster/state_checker.zig): on every commit it records the prepare header and its checksum in a global commits list, and check_state demands that a replica's commit_min moves by exactly one, that the new header's parent is the previous checksum, and that any state not yet in the history is justified by a live client's in-flight request, otherwise error.ReplicaTransitionedToInvalidState. Its comment states the invariant: "the cluster as a whole may not transition to the same state more than once, and once transitioned may not regress." Storage, journal, grid and manifest checkers sit beside it under src/testing/cluster/. Third, liveness: after the safety phase the simulator picks a random core of replicas, calls transition_to_liveness_mode (restart the core's crashed replicas, heal partitions among them, disable their storage faults, zero every crash and restart probability), and then requires convergence within ticks_max_convergence; if pending() still names a reason and cluster_recoverable says the core should have been able to recover, the run fails with "no state convergence" and "you can reproduce this failure with seed=…" (src/vopr.zig).

Reproduction and the style rule ​

The output format itself is designed for replay reading: docs/internals/testing.md documents the per-replica event column (! crash, ^ recover, commit, $ sync, [/] checkpoint). The house style makes the division of labour explicit (docs/TIGER_STYLE.md): "a fuzzer can prove only the presence of bugs, not their absence. Therefore: Build a precise mental model of the code first, encode your understanding in the form of assertions, … and use VOPR as the final line of defense, to find bugs in your and reviewer's understanding of code." The same file ties determinism to memory hygiene: a buffer bleed "may cause deterministic guarantees as required by TigerBeetle to be violated."

Beyond random search, two sibling harnesses matter here. src/vsr/replica_test.zig scripts "specific cases that are hard or slow to replicate through random simulation" on the same cluster double. src/testing/exhaustigen.zig is "An utility for exhaustive generation of arbitrary data": a loop that re-runs a body while a generator g enumerates every choice the body asked for through g.index(pool), so a test that asks "crash here or not?" at each site enumerates all crash placements instead of sampling them.

Antithesis ​

Antithesis moves the determinism boundary from the program to the machine. Its docs: "The Antithesis environment is fully deterministic. This makes every bug we find perfectly reproducible", and the exploration model is a tree: "Each event potentially starts a new timeline. In one universe, the network partitioned at time=t, and in many others, it didn't" (How Antithesis works). The mechanism is a hypervisor, described in its March 20, 2024 engineering post (Antithesis blog): "Everything in the hypervisor's guest environment sees a single linear history"; "Every attempt to access a time source from inside the guest – reading TSC, reading HPET, etc. – returns a virtual time value computed by the hypervisor"; "Each instance of the deterministic hypervisor runs on just one physical CPU core"; and "The points in execution history where the guest ingests input from the Antithesis platform become possible branch points for future execution", so "The external view of the exploration of a system is an input tree."

The fault catalogue is the same as FoundationDB's and TigerBeetle's, applied to unmodified containers (Controlling faults): network latency, partitions, clogs; node pause, node kill/stop, throttling; forward and backward clock skips; thread pausing (with instrumentation); CPU modulation. "By default, faults are injected throughout the test timeline, interleaved randomly with your workload." What this buys over an in-process simulator is that third-party code, the kernel and the filesystem are inside the deterministic box, exactly the limitation the FoundationDB paper concedes ("It is also unable to test third-party libraries or dependencies, or even first-party code not implemented in Flow", paper, §4, "Limitations"). What it costs is that the program cannot be made faster than the guest CPU: time compression comes from fast-forwarding an idle guest, not from skipping a scheduler queue.

Relevance to durable execution ​

3. Determinism enforcement ​

All three systems enforce determinism by the runtime, and all three discovered that the runtime can only enforce what it owns. FoundationDB owns the scheduler, the RNG, both clocks, the network and the disk, and pays for it by forbidding threads and third-party I/O libraries; TigerBeetle owns them by having no scheduler at all (a tick loop) and a Storage/Network/TimeSim triple that the production code never bypasses; Antithesis owns them by virtualizing the CPU. None enforces determinism by discipline alone, and FoundationDB adds a mechanical detector for discipline failures: the unseed check, which turns "someone read the wall clock" into a diff between two runs of one seed. For durable execution this is the sharpest lesson in the catalog: replay-based engines (see ./burckhardt-durable-functions-semantics.md, whose bisimulation theorem assumes deterministic replay as a lemma) need exactly the property DST tests for, and DST is the only technique here that checks it rather than assuming it. A workflow that is deterministic between journaled steps is, by construction, one that can run under a Sim2-style executor; if it cannot, replay will eventually diverge in production too.

6. Concurrency under replay ​

DST's answer is that the scheduler is the single source of interleavings, so concurrency is replayable iff the ready queue's pop order is a function of the seed. FoundationDB's TaskQueue orders by priority and arrival; TigerBeetle has no tasks, only ticks. A durable engine that lets concurrent steps race for the journal has to make the same choice: either serialize completion order through one seeded queue in tests, or accept that a journal can only replay the interleaving it recorded.

8. Testing ​

The three answers to "how is a durable program tested" share a shape that the catalog's other subjects lack:

  • Faults are drawn from a seed, not listed. A crash is a per-tick coin (replica_crash_probability), a kill is a workload parameter (machinesToKill), a rare branch is buggify(); the tester writes distributions and the harness explores. Both FoundationDB and TigerBeetle tune those distributions on purpose ("carefully tuned to avoid driving the system into a small state-space caused by an excessive fault rate", paper, §4).
  • A crash has a disk model. Neither system treats "kill" as "the last write is either fully there or fully absent": AsyncFileNonDurable shreds sectors of in-flight writes, Storage.reset corrupts one sector per pending write. An append-only journal under DST would see torn tail records, not just missing ones.
  • Oracles are layered. Local assertions, workload check, a global state checker, and a liveness phase that heals the fault-free core and demands convergence. TigerBeetle's liveness mode is the direct analogue of "resume after the crash and require completion".
  • The seed is the bug report. "you can reproduce this failure with seed=…"; -s <seed> -b on; the Antithesis input tree. Every failing run is a two-integer artifact (seed, commit).
  • Coverage of the fault space is measured, via CODE_PROBE counts per run, so a fault that never fires is visible as a number.

9. Journal integrity and the single writer ​

This is the dimension deterministic simulation testing exists to attack, and its contribution is not a mechanism but a way of finding out whether yours works.

The disk is modelled as an adversary, not as storage. Both FoundationDB's simulator and TigerBeetle's harness inject faults at the storage layer — torn writes, misdirected writes, bit rot, and writes that report success without landing — because those are the cases a recovery argument silently assumes away. A library that has reasoned carefully about its append protocol and never tested it against a torn last record has tested the happy path of exactly the code that exists to handle the unhappy one.

Crash points are inside operations, not between them. The simulator can stop a process at any scheduling point, which includes the middle of a write sequence. That is strictly more than truncating a record after a complete entry, and it is where the interesting bugs in an intent-then-effect protocol live: after the intent is written but before it is flushed, after the flush but before the effect, after the effect but before the result.

Determinism is verified rather than assumed. FoundationDB's unseed check re-runs a seed and compares, which mechanically detects a leak of real nondeterminism into code that was supposed to be deterministic. Every system in this survey that enforces determinism "by discipline" could have this check and none does.

The single-writer question is testable the same way. A simulated partition that leaves two nodes believing they own the same shard is a scenario a seed can produce on demand, which turns a fencing argument into an experiment.

10. Operator recovery and intervention ​

A seed is the bug report, and that is the transferable idea. A failing run is reproduced exactly by its seed and commit, so a defect travels as two short strings rather than as a log. The analogue for a durable-execution layer is that a journal is a reproducer: handed the record, the library can re-derive the failure without the original environment.

Restart tests are the versioning experiment. FoundationDB's paired save-and-kill then resume-with-a-newer-binary tests are the only mechanism in this catalog that actually exercises new code against an old record, rather than reasoning about whether it would work.

Otherwise the dimension does not apply. These are test harnesses, not systems with operators; there is nothing to cancel, fork or inspect at runtime.

Implications for a durable-execution library ​

  • A capability row is already the seam a simulator needs. Substituting the clock, the process spawner and the network is most of what FoundationDB and TigerBeetle build from scratch; a library whose effects all go through swappable handlers gets the harness for free and should exploit it rather than testing against real services.
  • Crash-at-every-record is a weak fault model. It samples only the boundaries between operations. The interesting failures in an intent-then-effect protocol are inside one operation: after the intent is written, after it is flushed, after the effect, before the result. A test that cannot reach those has not tested the recovery code.
  • Model the disk as an adversary. Torn writes, misdirected writes and writes that report success without landing are the cases a recovery argument assumes away, and a simulated storage layer is how they get exercised.
  • Verify determinism mechanically. Run the same seed twice and compare the record byte for byte. Every system in this survey that relies on discipline for determinism could do this, and none does — it is the cheapest possible check on the assumption the whole model rests on.
  • Draw faults from a seed, and report the seed. A reproducible failure is two short strings rather than a log, and it makes an intermittent bug a fixable one.
  • Add a liveness phase. TigerBeetle heals every injected fault and then requires the system to finish; without that, a harness proves only that nothing was corrupted, not that anything completes.
  • Exhaustive enumeration and seeded sampling are for different scales. Enumerate every crash point within one operation; sample schedules across a long program. Using one technique for both wastes time at one end and misses cases at the other.
  • Test new code against an old record deliberately. The paired save-kill-resume pattern is the only mechanism here that exercises the versioning question rather than arguing about it.

Sources ​