Asynchronous Agreement Protocols
Stub. Living with the FLP impossibility (already covered) instead of assuming it away: asynchronous building blocks (Reliable Broadcast, its multi-leader generalization Reliable Gather, and round-complexity results for both); combining binding and randomness to eventually reach agreement; Multi-world Validated Asynchronous Byzantine Agreement; a full series on Binary Asynchronous Agreement (Ben-Or's protocol, a modernized version, Crusader/Binding Crusader Agreement, and solving Binary Byzantine Agreement efficiently from a strong common coin); reaching agreement on a core set; and Verifiable Information Dispersal.
distributed-consensus-and-paxos already covers the FLP impossibility result: no deterministic asynchronous protocol can guarantee termination against even one crash fault. This note covers how the field lives with that fact rather than avoiding asynchrony altogether — accepting probabilistic termination via randomization. Covers the two core building blocks, Reliable Broadcast (every honest party eventually delivers the same message, despite no timing guarantees) and its multi-leader generalization Reliable Gather, along with how round complexity is even measured in a timing-free model. The main technical arc is Binary Asynchronous Agreement: defining the problem, Ben-Or’s classical randomized protocol (and a modernized presentation), the Crusader Agreement and Binding Crusader Agreement primitives, and using binding crusader agreement to solve binary Byzantine agreement efficiently from a strong common coin. Also covers Multi-world Validated Asynchronous Byzantine Agreement, reaching agreement on a core set of values rather than a single one, and Verifiable Information Dispersal (reliably splitting and later reconstructing data across parties, a building block for asynchronous SMR and erasure-coded storage alike).
Outline (TODO — flesh out each)
- Reliable Broadcast
- Reliable Gather — a multi-leader generalization
- Measuring and improving round complexity in asynchrony
- Living with asynchrony — combining binding and randomness
- Multi-world Validated Asynchronous Byzantine Agreement
- Binary Asynchronous Agreement — problem definition
- Ben-Or’s protocol; a modern version
- Crusader Agreement and Binding Crusader Agreement
- Binary Byzantine Agreement from a strong common coin
- Reaching asynchronous agreement on a core set
- Verifiable Information Dispersal