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.

Recall

These cards are also in your review deck, scheduled with spaced repetition.