Somtochi Onyekwere: Separate Protocol Logic from I/O for Deterministic Tests

I work on distributed systems and networking software at Fly.io. This talk is about structuring distributed protocols so that we can test them deterministically and gain confidence that they work before deployment.

Distributed systems are difficult to test because many nodes coordinate over a network. Messages can be delayed, reordered or lost; timers can fire, and nodes can be unavailable. A protocol must preserve its assumptions even when these failures occur.

A large integration test is expensive to run and difficult to reproduce. A cluster with thousands of nodes involves many processes, and a subsequent run may encounter events in a different order. Both scale and nondeterminism make failures hard to investigate.

While changing the broadcast protocol in Corrosion, an open-source SQLite replication system used at Fly.io, we noticed that the protocol described in a paper was relatively simple. We wanted to preserve that small core while making it easy to vary conditions, reproduce failures and reuse the implementation.

Protocol code often mixes its logic with thread creation, message sends and timers. If the implementation sleeps internally, a test may need to sleep too, introducing flakiness. We wanted to move those effects out of the protocol and leave a clear boundary where tests could substitute their own environment.

Our model treats the protocol as a state machine. It receives events, such as a message, a peer coming online or a fired timer, and indicates what actions should follow. It does not itself own sockets or a clock; the caller decides how to send messages and schedule timers.

The example is Plumtree, a gossip protocol for broadcasting through a cluster. A node sends full messages to eager peers, which forward them onward. Lazy peers receive message identifiers and can request a missing payload, providing a fallback path.

In Corrosion, an input such as a broadcast request goes to the Plumtree state. The protocol can ask the caller to send messages or deliver a payload to the application. The caller also supplies time, so effects are outside the core logic.

One possible interface would return a list of requested actions. We instead used a trait, or interface, implemented by the caller. It exposes effects such as sending to a node or peers, delivering a payload, notifying the application and scheduling a timer.

When the protocol requests a timer, the caller handles scheduling. Once it fires, the caller passes a timer-fired event back to the protocol. The same separation applies to messages: the application provides the runtime and can choose how the effects are performed.

For example, Corrosion buffers messages briefly to batch them efficiently. Another user of the library can choose a different implementation. The integration layer is small: provide the interface and the protocol uses that environment.

This boundary is especially useful in tests because the test runtime can differ from production. Production can use threads and sockets; a local simulation instead records and queues events. No real network or thread per simulated node is required.

Our test used a binary heap ordered by event time. A loop removes the earliest event, applies it to the appropriate protocol state, and queues the messages, timers or deliveries produced in response. A map holds the state for each simulated node, allowing roughly 2,000 nodes to run on one system.

At the start, the test chooses nodes to broadcast at different times and queues those events. Processing one broadcast can generate more sends, timer requests and application deliveries. The loop keeps applying resulting events until the queue is exhausted.

Time is virtual. Instead of waiting for a real timer, the simulator jumps to the time of the next event and tells the protocol that the timer has fired. This makes a long sequence of scheduled behavior fast to execute and repeat.

Failures are events too. The test can take a node down, drop messages addressed to it, notify other nodes and bring it back later. That lets us examine how the protocol responds to conditions we explicitly choose.

We also changed Plumtree to fit Corrosion, so we needed to test the consequences. The paper’s membership approach differed from ours, where nodes knew the full membership. We could vary peer selection, including whether to prefer nearby nodes, and measure how that affected broadcast delivery time.

The resulting deterministic test let us exercise and replay protocol behavior before launch. It was not a multiverse debugger, but it gave us a useful local simulation and a systematic way to mock external effects.

There is an important limitation: testing the protocol core does not prove the integration is correct. If a caller blocks while sending, it might fail to pass incoming messages to the protocol promptly. The surrounding integration still needs its own tests.

This approach is often called Sans I/O. It does not eliminate complexity; it makes the boundary and responsibility explicit. Depending on the protocol, separating requested actions from effects can make the library easier to reason about and reuse.

We also inject randomness from the application. Production uses operating-system randomness, while a seeded source makes tests reproducible. Callers must supply the environment and understand how to pass events, so the design adds integration work, but for our case the testing benefits are worth it.