Lower Bounds for Byzantine Agreement

Collects the field’s impossibility results, which distributed-consensus-and-paxos‘s basic FLP/Byzantine-generals treatment only begins. Adversary-size bounds are the field’s CAP theorems: in partial synchrony, a 50-50-split perception forces a choice between safety and liveness; in synchrony with omission failures, even “lock-step” agreement needs $n > 2f$ (strengthened further to cover send-or-receive omission); permissionless settings have their own CAP-type theorems. Split-brain lower bounds cover several independent obstructions: the classical Dwork-Lynch-Stockmeyer (DLS) bound ($n>3f$ for Byzantine partial synchrony), the CJKR result (neither non-equivocation nor transferability alone suffices against minority corruption in asynchrony), a bound for stateless TEEs under a rollback adversary, and the Fischer-Lynch-Merritt (FLM) bound for no-PKI/adversary- can-simulate settings, strengthened with randomization. Message- complexity lower bounds (Dolev-Reischuk: quadratic messages are necessary, even under omission, extended to crusader broadcast and to randomized protocols against a strongly adaptive adversary) and round-complexity lower bounds (the simplest proofs that consensus needs an infinite execution against even one fault; early-stopping/early-deciding bounds; and the three-part FLP bivalency argument itself) round out the “how many resources are truly necessary” picture. Good-case latency lower bounds (why BFT needs three rounds, a full categorization of achievable latencies, the responsiveness-vs-latency tradeoff for rotating leaders, and the two extra rounds censorship resistance costs) and privacy-driven lower bounds (Ben-Or-Kelmer-Rabin for asynchronous verifiable secret sharing/MPC with perfect security; the SAP theorem, a CAP analogue for secret-key storage) are more specialized but similarly fundamental. Closes with a liveness attack on Raft under omission faults and lower bounds for strengthened validity notions.

Outline (TODO — flesh out each)

• Lower bounds on the size of the adversary — partial synchrony, synchrony + omission, permissionless CAP-type theorems
• Split-brain lower bounds — DLS, CJKR, TEE rollback, FLM (and randomized strengthening)
• Lower bounds on the number of messages — Dolev-Reischuk and extensions
• Lower bounds on round complexity and infinite executions — the FLP bivalency argument; early stopping / early deciding
• Lower bounds on good-case latency — the 3-round result, a full categorization, optimistic responsiveness, censorship resistance cost
• Lower bounds from privacy requirements — the BKR bound; the SAP theorem
• Liveness attacks — Raft under omission faults
• Lower bounds for strong validity