Byzantine Generals Problem

Pradeep P
2 days ago
3 min read

Series: Modern System Design · Layer 3 — Reliability

Layer 3 · Post 16 of 21

← Previous: Two Generals Problem → Next: FLP Impossibility

Layer 3 — Reliability · Post 100 of 119

If some participants can send conflicting messages on purpose, crash-only leader election is not enough.

What you'll learn

Crash-fault vs Byzantine (arbitrary) faults
The classic bound: more than two-thirds honest for many BFT protocols
When you actually need BFT (blockchains, multi-party) versus Raft in the datacenter

The idea in one minute

Lamport, Shostak, Pease: generals must agree attack / retreat. Some generals (and messengers) may be traitors. A traitor can tell A "attack" and B "retreat," or impersonate, or equivocate.

Crash-stop (what Raft / typical etcd assume): a node stops. It does not send two different votes. Byzantine: a node can do anything — including looking alive and lying.

Honest 1: "commit X"
Honest 2: "commit X"
Traitor:  "commit X" to 1,  "commit Y" to 2

If you only have majority crash voting, a liar can split the honest nodes. Byzantine fault tolerance (BFT) is the family of protocols (PBFT, Tendermint, HotStuff) that still agree if enough replicas are honest.

Why it matters

Most product systems you will design are crash-fault: you own the VMs, you trust your binaries (until supply chain, but you still do not run PBFT for checkout). Raft is the right default.

You need the Byzantine vocabulary when:

You do not trust the other party (consortium chain, multi-cloud attestation, some multi-vendor settlement).
Interviewers ask why Bitcoin isn't Raft.
A buggy node acts Byzantine (split-brain primary that still writes) — fencing (Post 105) is the crash-world mitigation; BFT is the "we assume malice" mitigation.

How it works

Lamport's oral-messages bound (intuition): to tolerate f traitors, you typically need 3f + 1 replicas in classic BFT (PBFT): 4 nodes for 1 traitor, 7 for 2. Crash-only quorum is 2f + 1 (3 nodes for 1 crash). Byzantine is more replicas and more messages.

Authenticated channels (signed messages) change some of the original thought-experiment variants; they do not make 2-node BFT magically safe.

What BFT agrees on: a sequence of decisions (blocks, batches) despite f arbitrary faults. It does not make a lying client honest. If the user's app submits two spends, that is a different layer (auth, hashes, UTXO).

Cost. More rounds, more signatures, more replicas. Latency and throughput suffer. That is why databases you know use Raft, not PBFT, inside one operator's cluster.

Not Two Generals. Two Generals is loss, two parties, no traitors required. Byzantine is conflicting statements. You can have both on a real WAN.

A simple example

Three payment processors in a joint venture must agree "this $10 moved" and none fully trusts the others.

Crash-only Raft run by one of them: the operator can equivocate (two ledgers). BFT among the three (or 4 if you need f=1 with 3f+1) means one dishonest processor cannot convince the others of two different histories — as long as the protocol's f bound holds.

Your single-company Postgres HA: do not deploy 4-node BFT. Use Patroni/Raft, backups, and access control. The threat is a dead VM, not a malicious replica in the replica set (if a replica is malicious you have a compromise, which is an incident response problem, not a three-phase vote).

Common mistakes

Calling every outage Byzantine. A GC pause is not a traitor. Use crash + timeout models first.

3-node Raft as BFT. Raft is not BFT. A Byzantine leader can lie to followers within protocol limits; the usual assumption is non-Byzantine software.

BFT for a REST monolith. Wrong tool. Sign requests, isolate tenants, use audits.

Ignoring f in "we run a blockchain." If one consortium member owns 3 of 4 validators, you have a marketing whitepaper, not BFT.

How this shows up in real systems

Bitcoin / Ethereum / Tendermint / HotStuff: BFT-ish or probabilistic (PoW) agreement among untrusted miners/validators.
Hyperledger, Cosmos, some exchanges' settlement: BFT consensus modules.
Spanner / etcd / ZooKeeper / Kafka ISR: crash (or fail-stop) assumptions, not Byzantine.
Certificate authorities / CT logs: different Byzantine-adjacent trust problems.

Recap

Crash: stop. Byzantine: lie, equivocate, omit.
Crash clusters: 2f+1 and Raft. Untrusted parties: BFT, typically 3f+1, more cost.
Next: even honest crash consensus cannot always finish on a fully async network — FLP.