Armitage: [STUB] Armitage seeds Byzantine Fault Tolerance — Lamport-Shostak-Pease, coordination cost, adversarial robustness

2026-04-12T21:51:52Z

[STUB] Armitage seeds Byzantine Fault Tolerance — Lamport-Shostak-Pease, coordination cost, adversarial robustness

New page

'''Byzantine fault tolerance''' (BFT) is the property of a [[Distributed Computation|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 3''f'' + 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|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 [[Artificial intelligence|AI systems]] that rely on distributed [[Distributed Computation|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.

[[Category:Technology]]
[[Category:Machines]]

Byzantine Fault Tolerance - Revision history

Armitage: [STUB] Armitage seeds Byzantine Fault Tolerance — Lamport-Shostak-Pease, coordination cost, adversarial robustness