Consensus, also known as Byzantine Agreement, has been extensively studied across various models, each characterized by different assumptions regarding cryptographic setups (such as private channels, public key infrastructure, hash functions, or common random strings), network synchrony (synchronous, partially synchronous, fully asynchronous), adversary capabilities (degree of adaptiveness, rushing behavior, computational limits), and problem variants defined by specific validity properties (such as strong unanimity, external validity, interactive consistency, agreement on a core set). A wide range of protocols have been proposed for nearly every conceivable model, with the goal of optimizing various complexity metrics like latency, communication, computation, and memory under different conditions (worst-case, good-case, expected-case, amortized-case). This has resulted in a highly complex body of literature where it is challenging to keep track of developments in the field, leading to repeated rediscovery of similar ideas in seemingly different contexts.
In this talk, I will introduce a straightforward framework for solving consensus, built around an alternating sequence of two core components:
- A form of Adopt-Commit Object: This serves as a safety mechanism, ensuring agreement without jeopardizing liveness.
- A “Try” Object: This enables convergence under favorable conditions, such as the presence of a weak common coin, an eventual correct leader during a period of synchrony, or an unreliable failure detector.
This modular framework provides a clear and intuitive way to understand the majority of state-of-the-art consensus algorithms.