Byzantine fault tolerance (BFT) means a distributed system keeps reaching correct agreement even when some nodes are faulty or malicious; solutions include Lamport's oral-message and signed-message algorithms, PBFT and its modern variants, Proof of Work (Nakamoto consensus), Proof of Stake protocols, and federated BFT.
- Oral Messages algorithm OM(m) (Lamport et al., 1982): generals recursively relay the orders they received and decide by majority vote. Works if \(n \ge 3m + 1\) for \(m\) traitors; message count grows exponentially, so it is mainly theoretical.
- Signed Messages algorithm SM(m): messages carry unforgeable digital signatures, so a traitor cannot alter what others said. Works for any number of traitors (needs \(n \ge m + 2\)).
- Practical BFT (PBFT) (Castro and Liskov, 1999): a primary and backups run pre-prepare, prepare and commit phases with \(2f + 1\) quorums; tolerates \(f\) faults among \(3f + 1\) nodes; view change replaces a faulty primary. Gives fast finality but \(O(n^2)\) messages, so it suits small permissioned networks.
- Improved BFT protocols: Tendermint (Cosmos), Istanbul BFT (Quorum), HotStuff (linear messages; used in Diem/Libra), Delegated BFT (NEO), Zyzzyva and SBFT reduce messages or latency.
- Proof of Work (Nakamoto consensus): nodes accept the longest (most-work) chain. Attackers need more than 50% of the hash power to rewrite history, so it tolerates Byzantine nodes in an open network with probabilistic finality.
- Proof of Stake and BFT-style PoS: validators risk their stake; misbehaviour is punished by slashing (e.g. Ethereum's Casper FFG finality gadget tolerates less than one-third faulty stake).
- Federated BFT: each node chooses a set of trusted nodes (quorum slices) and agreement spreads through overlapping quorums (Stellar Consensus Protocol, Ripple).
Common idea: limit the power of faulty nodes (through quorums of more than two-thirds, signatures, computing cost or staked money) so honest nodes always form the deciding majority.