Optimal Eventual Byzantine Agreement Protocols with Omission Failures

DOI10.1145/3583668.3594573arXiv2305.06271MaRDI QIDQ6202257FDOQ6202257

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)

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).

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)

Cites Work

• Title not available (Why is that?)
• Knowledge and common knowledge in a distributed environment
• Programming simultaneous actions using common knowledge
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• A characterization of eventual Byzantine agreement

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)