System Models: Synchronous and Asynchronous Networks, Crash-Stop, Crash-Recovery and Byzantine Failures

Version note: The code in this post was built and run with C# 14 and .NET 10.

Guess First

Bookstore's OrderService sends an OrderPlaced message to Inventory for every order. Between them sits a bad network that loses one message in five. To make sure no message is lost, the team adopts a simple rule: resend until an ack arrives. The ack comes back over the same network, so it is also lost one time in five.

After 1000 orders, how many distinct orders does Inventory see? And how many times in total does it try to decrement stock? By the end of this post you will have the real answer to both questions, and you will see why "exactly once" is not one of the options.

Why Do We Need a Model?

In the previous post we experienced uncertainty in an HTTP (Hypertext Transfer Protocol) call: a timeout arrived and we could not tell what happened to the request. When you want to build an algorithm on top of that, the first job is to state which kinds of misbehavior it tolerates. Does the network "sometimes lose messages", or can it "alter them"? When a node crashes, does it "never come back", or does it "come back with its disk intact"? Do messages "arrive within 100 milliseconds at the latest", or is "when they arrive unknown"?

The sum of these assumptions is called a system model. The distributed algorithms literature ties every result to a model: Raft assumes "crash-recovery nodes, fair-loss links, a partially synchronous network"; Byzantine fault tolerant protocols assume nodes may lie and pay for it with more nodes and more messages. If you read a system's guarantee without knowing its model, you cannot know under which conditions that guarantee stops holding. Kleppmann's lecture notes build the model along three axes: the network, node behavior and timing. This post follows the same order.

The Network: Reliable, Fair-Loss and Arbitrary Links

There are three models for the link between two nodes. A reliable link assumes every message sent arrives, exactly once; messages may be reordered but not lost. A fair-loss link assumes messages may be lost, duplicated and reordered, but if you keep retrying forever one will eventually get through. On an arbitrary link an active adversary in the middle can read, modify or forge messages.

A real network is close to fair-loss. TCP (Transmission Control Protocol) offers something like a reliable link within a single connection by retransmitting and reordering packets, but that guarantee ends the moment the connection drops, and the application has to resend the request that was cut off. We turn an arbitrary link into a fair-loss one with TLS (Transport Layer Security): encryption and integrity checks make tampering detectable, but they cannot stop the attacker from dropping packets.

Let us simulate a fair-loss link with a Channel<T>. Every message is dropped with a fixed probability:

using System.Threading.Channels;

namespace Bookstore.Simulation;

public record Message(int Id, string Body);

// A fair-loss link: each message is dropped with a fixed probability
public sealed class LossyLink(double dropRate, int seed)
{
    private readonly Channel<Message> _channel = Channel.CreateUnbounded<Message>();
    private readonly Random _random = new(seed);

    public int Dropped { get; private set; }

    public ChannelReader<Message> Reader => _channel.Reader;

    public void Send(Message message)
    {
        if (_random.NextDouble() < dropRate)
        {
            Dropped++;
            return;
        }
        _channel.Writer.TryWrite(message);
    }

    public void Close() => _channel.Writer.Complete();
}

The first experiment is at-most-once: send each order once and never retry. The second is at-least-once: resend until an ack arrives, and let the ack come back over a lossy link too. The randomness uses a fixed seed, so the run is reproducible:

using Bookstore.Simulation;

// 1) At-most-once: send once, never retry
LossyLink link = new(dropRate: 0.2, seed: 42);
for (int i = 1; i <= 1000; i++)
{
    link.Send(new Message(i, $"OrderPlaced {i}"));
}
link.Close();
int received = 0;
await foreach (Message _ in link.Reader.ReadAllAsync())
{
    received++;
}
Console.WriteLine($"at-most-once : sent=1000 received={received} lost={link.Dropped}");

// 2) At-least-once: retry until the ack arrives; the ack travels on a lossy link too
LossyLink requests = new(dropRate: 0.2, seed: 7);
LossyLink acks = new(dropRate: 0.2, seed: 8);
Dictionary<int, int> deliveries = [];
for (int i = 1; i <= 1000; i++)
{
    bool acked = false;
    while (!acked)
    {
        requests.Send(new Message(i, $"OrderPlaced {i}"));
        if (requests.Reader.TryRead(out Message? delivered))
        {
            deliveries[delivered.Id] = deliveries.GetValueOrDefault(delivered.Id) + 1;
            acks.Send(new Message(delivered.Id, "ack"));
        }
        acked = acks.Reader.TryRead(out _);
    }
}
int duplicates = deliveries.Values.Sum(count => count - 1);
Console.WriteLine($"at-least-once: distinct={deliveries.Count} duplicates={duplicates} " +
                  $"lost requests={requests.Dropped} lost acks={acks.Dropped}");

at-most-once : sent=1000 received=774 lost=226
at-least-once: distinct=1000 duplicates=271 lost requests=354 lost acks=271

At-most-once lost 226 of the 1000 orders. At-least-once lost none, but Inventory processed 271 orders twice, and that number is exactly the number of lost acks. This is no coincidence: when the request arrives but the ack is lost, the sender cannot tell this apart from the request never arriving, so it resends. Every lost ack is a duplicate. Adding retries to a fair-loss link turns it into a reliable link only in the "nothing is lost" sense; for "nothing is duplicated" the receiver has to deduplicate.

The Two Generals and Why Exactly-Once Is Impossible

The classic name for this dilemma is the Two Generals problem (it first appeared in a 1975 paper by Akkoyunlu, Ekanadham and Huber, and Jim Gray named it in 1978). Two armies can take a city only if they attack at the same time; the generals can communicate only through messengers who cross enemy territory and may be captured. The first general says "we attack at dawn". The second sends a messenger to confirm receipt, but cannot attack without knowing that messenger arrived, so the first general must send an "I got your confirmation" messenger, and so on forever. No finite number of messages gives both sides certainty, because if the last message is lost, its sender cannot change its behavior.

The payment scenario has the same structure: the online shop and the payment provider want to agree that "the order is done". The practical consequence is that message delivery has three options: at-most-once (I may lose, but never duplicate), at-least-once (I may duplicate, but never lose), and exactly-once, which no network can provide on its own. What brokers market as "exactly-once" is really at-least-once delivery plus idempotent processing or deduplication on the receiving side; the accurate name is "effectively once". The Messaging and Event-Driven Architecture series works through this distinction with real brokers in "Delivery Guarantees: At-Most-Once, At-Least-Once, and the Truth About "Exactly-Once""; what you see here is its theoretical basis.

The Byzantine Generals: When a Node Lies

In the Two Generals problem the generals are honest and the trouble is the messengers. In the 1982 paper "The Byzantine Generals Problem" by Lamport, Shostak and Pease, some generals may be traitors: they can send different messages to different generals and forge orders. The paper's result is that tolerating f traitors requires at least 3f + 1 generals (with unsigned messages). So four nodes to survive one traitor, seven for two.

Most systems running in a company's own data center do not use this model; they assume nodes are not malicious. Byzantine fault tolerance is needed in blockchains, where parties who do not trust each other keep a shared ledger, and in aerospace, where one faulty sensor can bring down an aircraft. Still, the "nodes do not lie" assumption should be a conscious one: a failing disk or a bit flip in memory also produces wrong data. That is why checksums and input validation exist in non-Byzantine systems too; their target is accidents, not malice.

Node Failure Models: Crash-Stop, Crash-Recovery, Byzantine

In the crash-stop model, a node that crashes stays down forever; it never sends or receives another message. In the crash-recovery model a node crashes and comes back some time later; everything in memory is gone and only what it wrote to stable storage (disk) remains. In the Byzantine model a node behaves arbitrarily.

A service running on .NET fits the crash-recovery model in practice. When Kubernetes kills and restarts a pod, the process's in-memory ConcurrentDictionary, static fields and MemoryCache are gone; whatever was committed to the database remains. The distinction is critical at the algorithm level: in Raft a node does not answer before its vote and the highest term it has seen are on disk, because voting a second time in the same term after a restart could lead to two leaders. And "on disk" requires a call that bypasses the operating system cache, such as FileStream.Flush(flushToDisk: true); calling only Write means the data may still be waiting in the operating system's page cache.

Timing: Synchronous, Partially Synchronous, Asynchronous

In the synchronous model there is a known upper bound on message delay and on how fast processes run: "every message arrives within 10 milliseconds". Algorithms are easy to write under this assumption, because a node that has not answered in 10 milliseconds has definitely crashed. In the asynchronous model there is no upper bound at all; messages arrive, but there is no telling when, and processes can pause for arbitrary lengths of time. In this model a slow node and a crashed node are indistinguishable.

Real systems sit in between. The partially synchronous model defined by Dwork, Lynch and Stockmeyer in 1988 captures this: the system behaves synchronously most of the time but sometimes slips into asynchrony for unbounded periods. Switch queues fill up, a virtual machine gets no CPU (Central Processing Unit) time because of another tenant, the garbage collector (GC) does a stop-the-world pause, the operating system swaps memory out. All of these are temporary, but nobody knows for how long. That is why tying an algorithm's safety guarantee to a synchronous assumption is dangerous; a sound design keeps safety under the asynchronous model and relies on timing only for liveness (for making progress). We will come back to this distinction shortly.

Failure Detectors and Choosing Timeouts

The only practical way to learn that a node has crashed is to hear nothing from it for a while. A timeout-based failure detector expects regular heartbeats from each node and suspects a node when no heartbeat arrives within a set time. Under the asynchronous model such a detector cannot be perfect: a timeout that is too short declares live but slow nodes dead (false positives), one that is too long notices a truly crashed node late. To see this, let us generate one hour of simulated traffic. The node sends a heartbeat every 100 milliseconds and never crashes; network delay is usually a few milliseconds but sometimes longer, and occasionally the sender goes into a GC pause of 0.3 to 4 seconds:

namespace Bookstore.Simulation;

// Simulated time: the node sends a heartbeat every 100 ms and never crashes
public static class FailureDetectorExperiment
{
    public static void Run()
    {
        Random random = new(2026);
        List<double> arrivals = [];
        double now = 0;
        while (now < 3_600_000) // one simulated hour
        {
            if (random.NextDouble() < 0.0005)
            {
                now += random.Next(300, 4000); // stop-the-world GC pause on the sender
            }
            double networkDelay = 2 + -8 * Math.Log(1 - random.NextDouble()); // exponential tail
            arrivals.Add(now + networkDelay);
            now += 100;
        }
        arrivals.Sort();

        Console.WriteLine("timeout(ms)  false suspicions/hour  real crash noticed after(ms)");
        foreach (int timeoutMs in new[] { 150, 250, 500, 1000, 5000 })
        {
            int suspicions = 0;
            for (int i = 1; i < arrivals.Count; i++)
            {
                if (arrivals[i] - arrivals[i - 1] > timeoutMs)
                {
                    suspicions++;
                }
            }
            Console.WriteLine($"{timeoutMs,11}  {suspicions,21}  {timeoutMs,28}");
        }
    }
}

timeout(ms)  false suspicions/hour  real crash noticed after(ms)
        150                     39                           150
        250                     20                           250
        500                     19                           500
       1000                     16                          1000
       5000                      0                          5000

For a node that never crashes, a 150-millisecond timeout raised a false alarm 39 times in an hour. In a real system every alarm means a failover, a leader election or a circuit breaker opening; the failover itself can create load and cause new timeouts. Raising the timeout to 5 seconds brought false alarms to zero, but now noticing a real crash also takes 5 seconds. It is also instructive that the number barely changes between 250 and 1000 milliseconds: every alarm in that range comes from GC pauses, and unless you pick a timeout longer than the pause, you will not filter them out.

In practice a timeout is chosen from the observed delay distribution (for example several times p99.9), and it does not have to be fixed. The phi accrual failure detector by Hayashibara and colleagues (2004), used in Akka and Cassandra, produces a suspicion level based on the historical distribution of heartbeat intervals instead of a binary "dead / alive"; the application picks the threshold according to its own costs.

Safety and Liveness

An algorithm's guarantees come in two kinds. Safety means "something bad never happens": two leaders are never elected in the same term, the same payment is never taken twice, committed data is never lost. A safety violation can be observed at a finite point in time and cannot be undone. Liveness means "something good eventually happens": a leader is eventually elected, every request is eventually answered. A liveness violation can never be shown conclusively at any finite point, because one can always say "it would have happened if you had waited a little longer". Lamport introduced the terms in 1977, and Alpern and Schneider defined them formally in 1985.

Combined with partial synchrony, this distinction gives the main rule of distributed system design: do not make safety depend on timing; liveness may. Raft prevents two leaders from committing at the same time with term numbers and majority votes, not timeouts; it uses timeouts only to decide "start a new election". However bad the network gets, Raft never commits something wrong; it may just fail to make progress. The lease-based locks we will see in the tenth post, on the other hand, tie safety directly to clocks and therefore break during a GC pause.

Common Pitfalls

Reading guarantees without a model. "This system is consistent" means nothing without an answer to "against which failures?". When you read the replication guarantees in a database's documentation, look separately for network partitions, a node losing its disk, and clock skew.

Trusting an exactly-once promise. When a library or broker says "exactly-once", check within which boundary it says so; for every side effect that leaves that boundary (the database, the e-mail service, the payment provider), idempotency is your job.

Treating memory as durable. In the crash-recovery model a process's memory does not survive into the next start. A consumer that keeps "I have processed this message" in a HashSet<Guid> processes everything again after a restart.

Picking timeouts by guesswork. Instead of copy-pasted values like "30 seconds" or "100 milliseconds", choose based on measured latency percentiles and the cost of a false positive.

Treating the failure detector's verdict as fact. "Node B is dead" is a suspicion. B may still be alive and writing; a failover that ignores this possibility leads to split brain. The fifth and tenth posts deal with two different faces of this problem.

A Small Experiment

★☆☆ Raise dropRate from 0.2 to 0.5. In at-least-once, is the number of duplicates still equal to the number of lost acks? Why?

★★☆ Add receiver-side deduplication to the at-least-once loop: let Inventory keep the Ids it has seen in a HashSet<int> and only ack repeats without processing them. Then simulate the receiver "restarting" once in the middle (the set is cleared). How many orders are processed twice?

★★★ Replace the fixed timeout in FailureDetectorExperiment with a threshold based on the mean and standard deviation of the last 100 heartbeat intervals (such as mean + 4 standard deviations). In the same simulation, how do the number of false alarms and the time to notice a real crash change?

In this post we modeled the network and the nodes, but we treated timing only as "delay". The next post looks at time itself: why machine clocks drift, how and how well NTP (Network Time Protocol) corrects them, why .NET code measures durations with a monotonic clock rather than DateTime.UtcNow, and why last-write-wins loses data because of clock skew.