Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication

DOI10.1145/3583668.3594599MaRDI QIDQ6202273zbMATH OpenOpenAlexWikidataFDO

Authors Bogdan S. Chlebus

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

zbMATH Keywords

consensuslower boundauthenticationcrash failuregossipingRamanujan graphcheckpointingByzantine fault

Mathematics Subject Classification ID

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

Abstract: We develop deterministic algorithms for the problems of consensus, gossiping and checkpointing with nodes prone to failing. Distributed systems are modeled as synchronous complete networks. Failures are represented either as crashes or authenticated Byzantine faults. The algorithmic goal is to have both linear running time and linear amount of communication for as large an upper bound $t$ on the number of faults as possible, with respect to the number of nodes~$n$. For crash failures, these bounds of optimality are $t=mathcalO(fracnlogn)$ for consensus and $t=mathcalO(fracnlo{g}^{2}n)$ for gossiping and checkpointing, while the running time for each algorithm is $Theta(t+logn)$. For the authenticated Byzantine model of failures, we show how to accomplish both linear running time and communication for $t=mathcalO(sqrtn)$. We show how to implement the algorithms in the single-port model, in which a node may choose only one other node to send/receive a message to/from in a round, such as to preserve the range of running time and communication optimality. We prove lower bounds to show the optimality of some performance bounds.

Cites work

• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 1306905 (Why is no real title available?)
• scientific article; zbMATH DE number 1849959 (Why is no real title available?)
• scientific article; zbMATH DE number 6297761 (Why is no real title available?)
• A tight lower bound for randomized synchronous consensus
• Authenticated Algorithms for Byzantine Agreement
• Bounds on information exchange for Byzantine agreement
• Breaking the \(O(n^2)\) bit barrier, scalable Byzantine agreement with an adaptive adversary
• Communication Complexity of Byzantine Agreement, Revisited
• Communication-efficient randomized consensus
• Doing-it-all with bounded work and communication
• Early stopping in Byzantine agreement
• Early-deciding consensus is expensive
• Efficient agreement using fault diagnosis.
• Efficient gossip and robust distributed computation
• Expander families and Cayley graphs. A beginner's guide
• Expander graphs and their applications
• Fast scalable deterministic consensus for crash failures
• Impossibility results for distributed computing
• Lower bounds for randomized consensus under a weak adversary
• Message-optimal protocols for Byzantine Agreement
• On the Message Complexity of Indulgent Consensus
• Randomized Consensus in Expected $O(N\log ^2 N)$ Operations Per Processor
• Reaching Agreement in the Presence of Faults
• Robust gossiping with an application to consensus
• Scalable Quantum Consensus for Crash Failures
• Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement
• Simple constant-time consensus protocols in realistic failure models
• The Byzantine Generals Problem
• Time and Communication Efficient Consensus for Crash Failures
• Time-optimal message-efficient work performance in the presence of faults

This page was built for publication: Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication

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