Optimal Eventual Byzantine Agreement Protocols with Omission Failures

DOI10.1145/3583668.3594573MaRDI QIDQ6202257zbMATH OpenFDO

Authors Joseph Y. Halpern, Ron van der Meyden

Publication date 26 March 2024

Published in Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2305.06271

zbMATH Keywords

consensusdistributed algorithmsepistemic logicfault toleranceByzantine agreementreasoning about knowledge

Mathematics Subject Classification ID

Distributed algorithms (68W15) Distributed systems (68M14)

Abstract: Work on emph{optimal} protocols for emph{Eventual Byzantine Agreement} (EBA) -- protocols that, in a precise sense, decide as soon as possible in every run and guarantee that all nonfaulty agents decide on the same value -- has focused on emph{full-information protocols} (FIPs), where agents repeatedly send messages that completely describe their past observations to every other agent. While it can be shown that, without loss of generality, we can take an optimal protocol to be an FIP, full information exchange is impractical to implement for many applications due to the required message size. We separate protocols into two parts, the emph{information-exchange protocol} and the emph{action protocol}, so as to be able to examine the effects of more limited information exchange. We then define a notion of optimality with respect to an information-exchange protocol. Roughly speaking, an action protocol $P$ is optimal with respect to an information-exchange protocol $mathcalE$ if, with $P$, agents decide as soon as possible among action protocols that exchange information according to $mathcalE$. We present a knowledge-based EBA program for omission failures all of whose implementations are guaranteed to be correct and are optimal if the information exchange satisfies a certain safety condition. We then construct concrete programs that implement this knowledge-based program in two settings of interest that are shown to satisfy the safety condition. Finally, we show that a small modification of our program results in an FIP that is both optimal and efficiently implementable, settling an open problem posed by Halpern, Moses, and Waarts (SIAM J. Comput., 2001).

Cites work

• scientific article; zbMATH DE number 795590 (Why is no real title available?)
• A characterization of eventual Byzantine agreement
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Knowledge and common knowledge in a distributed environment
• Programming simultaneous actions using common knowledge

This page was built for publication: Optimal Eventual Byzantine Agreement Protocols with Omission Failures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6202257)