Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication

DOI10.1145/3583668.3594599arXiv2305.11644OpenAlexW4380881694WikidataQ130818618 ScholiaQ130818618MaRDI QIDQ6202273FDOQ6202273

Author name not available (Why is that?), Bogdan S. Chlebus, Author name not available (Why is that?)

Publication date: 26 March 2024

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Expander graphs and their applications
• Authenticated Algorithms for Byzantine Agreement
• Early stopping in Byzantine agreement
• Reaching Agreement in the Presence of Faults
• The Byzantine Generals Problem
• Title not available (Why is that?)
• Shifting gears: Changing algorithms on the fly to expedite Byzantine agreement
• Bounds on information exchange for Byzantine agreement
• Time-optimal message-efficient work performance in the presence of faults
• Lower Bounds for Randomized Consensus under a Weak Adversary
• Efficient gossip and robust distributed computation
• Time and Communication Efficient Consensus for Crash Failures
• Title not available (Why is that?)
• Doing-it-all with bounded work and communication
• Robust gossiping with an application to consensus
• Title not available (Why is that?)
• Randomized Consensus in Expected $O(N\log ^2 N)$ Operations Per Processor
• Simple constant-time consensus protocols in realistic failure models
• Message-optimal protocols for Byzantine Agreement
• Title not available (Why is that?)
• Fast scalable deterministic consensus for crash failures
• A tight lower bound for randomized synchronous consensus
• Efficient agreement using fault diagnosis.
• Communication-efficient randomized consensus
• Communication Complexity of Byzantine Agreement, Revisited
• Breaking the O ( n ² ) bit barrier
• Scalable Quantum Consensus for Crash Failures
• Impossibility Results for Distributed Computing
• On the Message Complexity of Indulgent Consensus
• Early-deciding consensus is expensive

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)