Agreement in the Presence of Failures

Agreement problems in general, and Consensus in particular, share fundamental characteristics that have been the subject of extensive research and comparative literature. This work utilizes knowledge theory (epistemic logic) to formally characterize these problems within fault-prone distributed environments. Specifically, we provide a logical characterization of a large class of All-or-Nothing (AoN) agreement problems, including Consensus, Reliable Broadcast, and Atomic Commitment.
This characterization is built upon the notion of dynamic common knowledge (DCK), a concept recently introduced by Gonczarowski and Moses, which we adapt here for fault-prone distributed systems. By doing so, we offer a new, model-independent approach to the design, analysis, and optimization of agreement protocols. To demonstrate the power and practical utility of this knowledge-theoretic framework, we apply it to two distinct scenarios: optimizing a Consensus protocol in a synchronous crash-failure model, and streamlining Bracha’s reliable broadcast protocol in an asynchronous system with Byzantine failures.
At the core of this work is the mathematical formalization establishing that DCK is both a necessary and sufficient condition for solving All-or-Nothing agreement. In essence, DCK provides a way to capture the required “state of agreement” among non-faulty processes without forcing them to reach their decisions at the exact same instant. We prove that any protocol satisfying the AoN condition inherently generates this dynamic knowledge. Conversely, we establish a sufficiency theorem: if a system guarantees that a set of facts satisfies Validity (the value is allowed), Exclusivity (no conflicting values are decided), and Epistemic Sufficiency (the fact ensures its own DCK), these facts are entirely sufficient to construct a working agreement protocol.
Ultimately, this logical characterization transcends specific network models or failure assumptions, offering a unifying lens through which to view distributed agreement. By demonstrating that attaining DCK is the fundamental epistemic engine driving these protocols, our framework not only demystifies the structure of classical solutions but provides a rigorous, systematic blueprint for designing leaner and more efficient distributed algorithms in the future.

M.Sc. student under the supervision of Prof. Yoram Moses.