Date: November 30, 2026
Title: Where Knowledge Meets Agreement
Speaker: Yoram Moses, Technion, Israel Institute of Technology

Abstract: 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 essential aspects of agreement problems in a unifying and model-independent fashion. Specifically, we focus on All-or-Nothing agreement protocols (AoN), in which all non faulty processes must decide on the exact same values in any given execution. This covers a large class of central  problems, including Consensus, Reliable Broadcast and Atomic Commitment. We prove that dynamic common knowledge, a concept recently introduced by Gonczarowski and Moses, is both necessary and sufficient for deciding on a value in AoN protocols. In particular, every AoN protocol must contain a mechanism for creating and detecting dynamic common knowledge. This applies in all failure models, under all variants of synchrony/asynchrony, and all modes of communication and network topologies. The mechanism depends on the parameters of the model. We illustrate how this logical characterization can help us understand the structure of existing protocols, and can be used to facilitate the design, analysis, and optimization of agreement protocols.

This is joint work with Or David.