Fallacies of Distributed Computing: Crash, Omission, Byzantine

Messages start to vanish, arrive late or arrive twice, and code that never expected this makes confident wrong decisions. On one laptop, a function call either returns or throws an error. Across a network, a request can simply get no answer.

The fallacies of distributed computing name the beliefs behind those wrong decisions. Failure models then say exactly which failures your design must survive. This guide covers both, on one running example.

Picture a common setup. A crop-spraying service flies a fleet of drones over vineyards and onion fields. Each drone is controlled from a ground station, a van with a laptop and a radio link. The setup is made up, but the problems are real.

The vans talk to a mission server in a data centre over 4G, which is patchy out in the fields. Each drone carries a 16-litre spray tank. In testing, everything sat on one office network and worked. Then the first busy week brought two bad days.

1. 1

   Monday: the silent drone

   Drone D-17 stops sending updates over a vineyard. The mission server marks it as crashed and sends drone D-22 to finish the same rows.

2. 2

   Monday, ten minutes later

   D-17 was never down. Only its radio link had dropped, and it kept spraying. Both drones sprayed the same rows, so the vines got a double dose.

3. 3

   Thursday: the confident liar

   Drone D-05 reports a full tank all morning. Its level sensor is faulty. The tank is empty, so it flies the whole field spraying nothing.

Neither day was a bug in the usual sense. The code simply assumed that the network and the drones would behave. Monday is a lost-message problem, and Thursday is a wrong-message problem. They need very different fixes.

The fallacies of distributed computing are eight assumptions that programmers new to networked systems tend to make, and all eight are false. The list came from engineers at Sun Microsystems in the 1990s.

A distributed system is a set of programs on different machines that work together by sending messages over a network. The drones, ground stations and mission server form one.

L. Peter Deutsch, a Sun Fellow, put together a list of seven in 1994, building on four that others had already named. Around 1997, James Gosling, who created Java, added the eighth. Here they are, each with the way it hit the fleet.

• The network is reliable. Out in the fields, radio and 4G links drop for seconds at a time. D-17's radio link dropped, so its updates simply stopped arriving.
• Latency is zero. Latency is the time a message takes to travel. A command can take tens of milliseconds on a good link and several seconds on a weak one.
• Bandwidth is infinite. Bandwidth is how much data a link can carry per second. Live video from every drone would choke a weak rural link.
• The network is secure. Anyone near a field could try to send fake commands to a drone.
• Topology doesn't change. Topology is the shape of the network. A ground station van moves, so its mobile tower and route change during the day.
• There is one administrator. The mobile operator, the data centre and the spraying service each control a different part of the path.
• Transport cost is zero. Every message costs data, battery and money, especially on a mobile plan.
• The network is homogeneous. Homogeneous means all the same. Drones use radio, vans use 4G, and the server sits on a wired data centre network.

The diagram shows the fleet's system. Follow a command from the mission server to a drone, and count how many separate links it crosses. Each link is a place where one of the fallacies can bite.

A failure model is a written list of the ways you assume each part of your system can fail. It turns the vague fallacies into precise promises that your design must survive.

A node is any single machine or program in the system. Each drone, each ground station and the mission server is a node.

Think of a 20-litre drinking-water can delivered to your building every morning. The delivery boy can fail in three very different ways. He can stop coming. He can come but skip some floors. Or he can leave the wrong can, say a dirty one with a fresh seal.

Each failure needs a different defence. If he stops coming, you notice the missing can and call another supplier. If he skips floors, some people think he came and others think he did not. A wrong can is the worst, because nothing looks missing.

Where the picture breaks: in a building, a neighbour can walk upstairs and look. In a network, every check is itself a message that can be lost, so you can never simply go and see.

Computer science names these same shapes. A classic classification, which papers credit to Flaviu Cristian's 1991 work, sorts failures into classes that fit inside each other, from mildest to worst.

• Crash failure: the node stops and sends nothing more. The delivery boy who stops coming.
• Omission failure: the node keeps running, but some messages it should send or receive are lost. The delivery boy who skips floors.
• Timing failure: the right message arrives, but outside the time it was needed. Late-only timing failures are also called performance failures.
• Byzantine failure, also called arbitrary failure: the node may do anything, including send wrong or conflicting messages. The delivery boy who leaves the wrong can.

The classes are nested. A crash is an omission where every response after the crash is missing. An omission is a timing failure where the message is infinitely late. Byzantine covers all of them.

Here is that nesting as a ladder. Read it from left to right. Each step allows every failure on the step before it, plus more, so each step needs stronger defences.

A crash failure is when a node stops working and sends nothing more, without sending anything wrong first. It is the mildest failure model.

A drone whose battery dies mid-air has crashed, in both senses of the word. A mission server whose process is killed has crashed too.

There are two flavours. In crash-stop, a failed node never comes back. In crash-recovery, it restarts later and must rebuild what it knew from disk, because its memory was wiped.

Raft, a widely used consensus protocol, assumes crash-recovery. A consensus protocol lets several servers agree on one sequence of changes. The Raft paper says servers fail by stopping, and may later recover from stable storage and rejoin.

Crash-recovery is the realistic flavour for the fleet. A ground station laptop reboots after an update. When it comes back, it must reload the latest mission plan from the server, because rows may have been sprayed while it was off.

An omission failure is when a node keeps running but some messages it should send or receive never arrive. The node is alive, and the network or the node quietly drops part of its work.

This is exactly Monday's problem. D-17 was flying and spraying. Its heartbeats, short "I am alive" messages sent every second, were dropped by the radio link. The mission server saw silence and decided D-17 had crashed.

Omissions can be one-sided, and that makes them nasty. A drone may still hear commands while its replies are lost. Then the drone and the server hold different views of the world, and both act on them.

Back to the water can. When the delivery boy skips the fourth floor, the people on the ground floor say he came today. The people on the fourth floor say he never came. Both are telling the truth about what they saw.

A timing failure is a message that arrives, but after the deadline that made it useful. A "stop spraying" command that reaches D-17 three seconds late still lets it spray an extra row.

Cristian and Fetzer's timed asynchronous model, a well-known model of real networks, allows messages only two kinds of failure. A message is dropped, or it is delivered late. It is never delivered early.

Here is the hard part. From outside, a crashed node, a node whose messages are lost and a very slow node all look the same: silence. The engineer sections below show how to act on silence safely.

A Byzantine failure is when a node keeps running but sends wrong, made-up or conflicting information. The node may be buggy, broken or taken over by an attacker, and it may tell different nodes different things.

The name comes from a 1982 paper by Leslie Lamport, Robert Shostak and Marshall Pease. It pictures generals of the Byzantine army who must agree on a battle plan by messenger. Some generals may be traitors who try to confuse the loyal ones.

The paper's best-known result is a hard limit. With only oral messages, meaning plain messages a traitor can change when passing them on, agreement is possible only if more than two-thirds of the generals are loyal.

So tolerating f traitors needs at least 3f plus 1 generals. Compare that with crashes. A majority system like Raft needs 2f plus 1 nodes, so 5 nodes survive 2 crashes. To survive 2 Byzantine nodes, you need at least 7.

Thursday's drone D-05 is the delivery boy leaving the wrong can. Its faulty level sensor reported a full tank while it sprayed nothing. Every message looked normal, came on time and had the right format.

A real outage that looked Byzantine

On 2 November 2020, a network switch at Cloudflare failed only partly. Some of its control protocols, which switches use to coordinate with each other, kept running. But it did not forward all data packets, so it looked partly healthy.

Cloudflare runs etcd, a key-value store that uses Raft. A key-value store is a database that looks values up by name. One etcd member could reach one peer but not the leader.

The leader is the one server that coordinates all writes.

The cut-off member kept starting leader elections that ended in ties. The post says Raft elections block all writes until resolved, so the cluster stayed read-only until the switch recovered.

Safety and availability are different promises. The Raft paper promises never to return a wrong result under faults like this one. Staying writable is a separate promise, and this cluster lost it.

The knock-on effects hurt the availability of Cloudflare's API and dashboard for 6 hours and 33 minutes. The post's title calls it a Byzantine failure.

Its postscript says the failure is better described as an omission fault. Such faults can be tolerated without Byzantine fault tolerant protocols, the heavy kind that keep working even when some nodes lie. That is the lesson: a partial network failure can look like lies when nobody is lying.

Most systems run by one organisation assume crash, omission and timing failures, and add cheap checks for corrupted data. Full Byzantine tolerance is for systems where some nodes may be broken in arbitrary ways or controlled by someone hostile.

Public blockchains face that problem, because anyone can run a node. Some reliable control systems run the same computation on several processors and take a majority vote, an approach the Byzantine generals paper discusses for reliable systems.

Cloudflare's report makes the same point from the other side. It says most general-purpose cluster management systems skip Byzantine fault tolerance. In its words, Raft-style protocols perform better and are easier to understand than Byzantine fault tolerant ones.

The fleet's choice is clear. Ground stations and the server assume crash, omission and timing failures. Drone reports get cheap checks. Nobody runs a Byzantine voting protocol, because one organisation builds and owns every drone.

You cannot tell them apart for certain, because all three look the same from outside. The best you can do is suspect a failure after a timeout, and design so that a wrong suspicion is safe.

Cristian and Fetzer put it plainly. In a time-free model, with no clocks or deadlines, a process cannot tell a crashed process from a very slow one. Real systems add timeouts to decide, and accept that the decision can be wrong.

A timeout is how long you wait before giving up on a reply. A failure detector is the part of the system that watches heartbeats and decides who looks alive. The naive detector on Monday said "dead". The fixed one never does.

In the code below, on_heartbeat runs whenever a heartbeat arrives from a drone. The status function is what the mission server asks before reassigning any rows.

import time

SUSPECT_AFTER = 3.0   # seconds of silence before we suspect a drone
last_seen = {}        # drone id -> time of its last heartbeat

def on_heartbeat(drone_id):
    last_seen[drone_id] = time.monotonic()

def status(drone_id):
    seen = last_seen.get(drone_id)
    if seen is None:
        return "unknown"
    if time.monotonic() - seen < SUSPECT_AFTER:
        return "alive"
    return "suspected"   # never "dead": it may only be out of signal

Two choices matter here. The code uses time.monotonic, a clock the Python docs say cannot go backwards and is not affected by system clock updates. So a change to the laptop's wall clock cannot make a silent drone look alive.

And the worst it ever says is "suspected", which pushes the next decision to code that knows the risk. You can check it yourself by adding these lines and running the file on Python 3.

on_heartbeat("D-17")
print(status("D-17"))   # alive
time.sleep(3.5)
print(status("D-17"))   # suspected
print(status("D-99"))   # unknown: never heard from

Expect three lines: alive, then suspected after about 3.5 seconds, then unknown. We ran it on Python 3.13; the whole run took about 3.5 seconds.

Picking SUSPECT_AFTER is a trade-off. A short timeout reacts fast but suspects healthy drones during every small signal drop. A long timeout is calmer but leaves a truly dead drone unnoticed. Measure real link gaps in the field before choosing a number.

Suspecting a drone is only half the fix. Monday's real mistake was acting on the suspicion as if it were proof. Follow the diagram below, and notice that the drone has its own rule for silence.

The key move is that the drone and the server follow matching rules. The server locks the rows instead of handing them out, and the drone stops by itself when it cannot hear the ground.

The same idea shows up in leader election and distributed locks. A node that was wrongly suspected may still believe it holds the lock. The usual fix is a fencing token, a number that grows each time the lock changes hands.

The storage then rejects any write carrying an older token than one it has already seen. So a stale owner that wakes up late cannot overwrite newer work.

You defend against wrong messages with layers of cheap checks, and use full Byzantine fault tolerance only when you truly cannot trust some nodes. Most systems need the cheap layers, not the heavy protocol.

Here every drone report is a JSON message, a common text format for data. The drone attaches a tag made with a secret key, so the server knows the report came from a real drone and was not changed on the way.

import hashlib, hmac, json

def accept(raw, tag, key, last_seq):
    expected = hmac.new(key, raw, hashlib.sha256).hexdigest()
    if not hmac.compare_digest(expected, tag):
        return None, "bad tag"           # corrupted or forged
    msg = json.loads(raw)
    if msg["seq"] <= last_seq:
        return None, "old or repeated"   # duplicate or replay
    if not 0 <= msg["tank_litres"] <= 16:
        return None, "impossible value"  # broken sensor
    return msg, "ok"

The first check uses an HMAC, a tag computed from the message and a shared secret key. Only someone with the key can make a valid tag. Python's compare_digest compares tags in a way designed to resist timing attacks, which guess a secret from how long a comparison takes.

The seq check rejects any report whose sequence number is not newer than the last one. That catches duplicates from retries and replays of recorded messages. The range check rejects tank levels that cannot exist in a 16-litre tank.

To check it, add these lines below the function and run the file. Each comment shows the output we got on Python 3.13.

key = b"demo-key"
sign = lambda raw: hmac.new(key, raw, hashlib.sha256).hexdigest()
good = b'{"seq": 8, "tank_litres": 12.5}'
print(accept(good, sign(good), key, 7))  # ({'seq': 8, 'tank_litres': 12.5}, 'ok')
print(accept(good, sign(good), key, 8))  # (None, 'old or repeated')
print(accept(good.replace(b"12.5", b"16.0"), sign(good), key, 7))  # (None, 'bad tag')
bad = b'{"seq": 9, "tank_litres": 40}'
print(accept(bad, sign(bad), key, 8))    # (None, 'impossible value')

What just happened? A fresh report passed. The same report again failed as a replay. A report altered after signing failed the tag check. A signed but impossible 40-litre reading failed the range check.

None of this catches D-05's sensor, which reported a believable 16 litres. For that, add a cross-check against a second source. Spray flow and tank level must agree: if the pump ran for 10 minutes, the tank cannot still be full.

• Checksums and tags catch messages corrupted or forged on the way.
• Sequence numbers and expiry times catch duplicate, replayed and stale messages.
• Range checks catch values that are physically impossible.
• Cross-checks between independent sources catch values that are possible but wrong.
• Byzantine fault tolerant protocols, with 3f plus 1 nodes voting, handle nodes that may lie or break in any way.

Because a traitor can tell different nodes different things, and with too few loyal nodes nobody can tell who is lying. The smallest case is three generals with one traitor, which the 1982 paper proves has no solution with oral messages.

You can watch the mechanism in a short simulation of one round of message passing. A loyal commander orders "attack". Every lieutenant passes on what it heard, the traitor flips the order, and each loyal lieutenant takes a majority vote.

from collections import Counter

def decide(values):
    # Majority vote. A tie falls back to the safe default, "retreat".
    top = Counter(values).most_common()
    if len(top) > 1 and top[0][1] == top[1][1]:
        return "retreat"
    return top[0][0]

def one_round(n, order, traitor):
    # The commander is loyal and sends `order` to lieutenants 1 to n-1.
    # Each lieutenant passes on what it heard; the traitor flips it.
    flip = "retreat" if order == "attack" else "attack"
    decisions = {}
    for i in range(1, n):
        if i == traitor:
            continue
        heard = [order]
        for j in range(1, n):
            if j != i:
                heard.append(flip if j == traitor else order)
        decisions[i] = decide(heard)
    return decisions

print(one_round(3, "attack", traitor=2))  # {1: 'retreat'}
print(one_round(4, "attack", traitor=3))  # {1: 'attack', 2: 'attack'}

Pause and predict: with three generals, lieutenant 1 hears "attack" from the commander and "retreat" from the traitor. Guess what it decides before reading on.

It hears one of each, a tie, so it falls back to retreat and disobeys a loyal commander. With four generals it hears attack twice and retreat once, so both loyal lieutenants attack.

What just happened? One extra loyal voice broke the tie. This shows the mechanism for one case only. The paper's proof covers every possible algorithm, not just this simple vote.

The paper also shows that unforgeable signatures remove the limit. That result assumes every message arrives within a known time and the generals' clocks are synchronised, so a missing message can be detected.

Real networks make no such promise. PBFT, a practical Byzantine fault tolerant protocol by Castro and Liskov from 1999, works on networks like the Internet. Its paper says 3f plus 1 replicas is the minimum there.

It stays safe without any timing promise. To keep making progress, it needs a weak one: message delays must not keep growing faster than time passes.

Name the fallacy that bites, choose a failure model, then show one concrete defence per failure. Keep the running example small and specific.

1. 1

   Name the network you have

   Say where messages travel and which links are weak. For the fleet, that is 4G and radio over farmland.

2. 2

   Pick the fallacies that bite

   Usually the network is reliable and latency is zero. Give one short example of each going wrong.

3. 3

   State the failure model

   Say which failures you design for, such as crash, omission and timing, and whether you trust nodes not to lie.

4. 4

   Show detection

   Heartbeats plus a timeout give a suspicion, not a certainty. Say how you chose the timeout.

5. 5

   Make wrong guesses safe

   Locks, fencing tokens, expiry times and a safe stop make a false suspicion harmless.

6. 6

   Handle bad data

   Add tags, sequence numbers, range checks and cross-checks. Mention 3f plus 1 voting only if nodes may be hostile.