Notesdistributed🌱 seedling
Byzantine Fault
Also: Byzantine Failure · Byzantine Generals Problem · Byzantine Fault Tolerance · BFT · System Model · Crash-Recovery · Partial Synchrony
A fault where a node behaves arbitrarily, including sending false or contradictory messages. Tolerating f such nodes needs at least 3f + 1 nodes, so most data-centre systems assume nodes are honest and only crash.
Also in: The Trouble with Distributed Systems › System models
Why it exists
Crash-tolerant protocols assume a node either follows the protocol or stops. Nodes that can lie (bugs, corrupted memory, attackers, untrusted parties) break that assumption.
How it works
- System models name what can go wrong. Timing: synchronous (bounded delay, pauses, drift), partially synchronous (usually bounded, occasionally not), asynchronous (no timing assumptions). Nodes: crash-stop, crash-recovery, Byzantine.
- Most practical algorithms (Raft, Paxos) assume partial synchrony and crash-recovery, without Byzantine nodes.
- Safety properties (nothing bad happens) must hold even when timing assumptions fail; liveness (something good eventually happens) may wait until the network behaves.
- BFT protocols need 3f + 1 nodes and extra message rounds, and they don't help if every node runs the same buggy code.
- Cheap partial defences: checksums on network and disk data, validating all client input, several NTP servers so one liar is outvoted.
Trade-offs
| Fault model | Gains | Costs |
|---|---|---|
| crash-recovery | simple, fast, 2f + 1 nodes | trusts every node's honesty |
| Byzantine | tolerates lying nodes | 3f + 1 nodes, heavy messaging, rarely worth it inside one organization |
In practice
- Needed where parties don't trust each other (blockchains, cross-organization systems) or hardware is unreliable (aerospace: radiation flips bits).
- Cloudflare, 2020: titled "A Byzantine failure in the real world", later noted to be an omission fault: a half-failed switch dropped messages, nobody lied.
Pitfalls
- Calling every confusing failure "Byzantine". Disagreement caused by lost messages is an omission fault, which crash-tolerant protocols should handle.
- Assuming BFT protects against a bug present on every replica.
Connections
- Part of
- Distributed Systems
- Learn first
- Partial Failure
- Related
- Consensus
Recall
These cards are also in your review deck, scheduled with spaced repetition.