Byzantine Fault Tolerance

Byzantine fault tolerance (BFT) is the property of a distributed system that allows it to continue operating correctly even when some of its components fail in arbitrary and potentially malicious ways — including sending contradictory information to different parts of the system. The name derives from the Byzantine Generals Problem, formalized by Lamport, Shostak, and Pease in 1982: a group of generals surrounding a city must agree on a coordinated attack or retreat, but some generals may be traitors who send different messages to different recipients. The problem asks: how many loyal generals are needed to guarantee correct coordination in the presence of f traitors?

The answer is that correct coordination requires at least 3f + 1 generals: a majority so overwhelming that traitors cannot prevent consensus. For a distributed computing system, this translates to a requirement that fewer than one-third of nodes be faulty for consensus to be achievable. Achieving BFT requires O(n²) message complexity — every node must communicate with every other node — which imposes a hard coordination cost that scales quadratically with system size.

This quadratic cost makes BFT expensive in practice and explains why most distributed systems (including the internet) do not implement full BFT but instead assume that failures are random (crash faults) rather than adversarial. The practical relevance increased dramatically with blockchain systems, which must achieve consensus among mutually untrusting participants without a central authority — exactly the Byzantine setting. Bitcoin's proof-of-work protocol is a probabilistic BFT mechanism; more recent systems use deterministic BFT protocols (PBFT, HotStuff) that offer stronger guarantees at higher coordination cost.

The deeper issue Byzantine fault tolerance raises for any distributed cognitive system — including AI systems that rely on distributed computation — is that adversarial inputs are not an edge case but a structural feature of any open system. A system that cannot tolerate Byzantine faults is not robust; it is merely untested.