Robust gossiping with an application to consensus

DOI10.1016/j.jcss.2006.08.001zbMath1119.68222OpenAlexW2008636585MaRDI QIDQ856404

Dariusz R. Kowalski, Bogdan S. Chlebus

Publication date: 7 December 2006

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2006.08.001

zbMATH Keywords

synchronygossipingmessage passingdistributed algorithmconsensuscrash failure

Mathematics Subject Classification ID

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

Related Items

Fault-tolerant graph realizations in the congested clique, Brief Announcement: Improved Consensus in Quantum Networks, Deterministic Fault-Tolerant Distributed Computing in Linear Time and Communication, The logic of gossiping, Meeting the deadline: on the complexity of fault-tolerant continuous gossip, Doing-it-all with bounded work and communication, Gossiping by processors prone to omission failures, New bounds on the minimum number of calls in failure‐tolerant gossiping, Communication-efficient randomized consensus

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Ramanujan graphs
• A lower bound for the time to assure interactive consistency
• On the message complexity of binary Byzantine agreement under crash failures
• Fast gossiping with short unreliable messages
• Methods and problems of communication in usual networks
• Tolerating a linear number of faults in networks of bounded degree
• Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
• Efficient gossip and robust distributed computation
• Resource discovery in distributed networks
• Telephone Problems with Failures
• Bounds on information exchange for Byzantine agreement
• Impossibility of distributed consensus with one faulty process
• A survey of gossiping and broadcasting in communication networks
• Fault Tolerance in Networks of Bounded Degree
• Reaching Agreement in the Presence of Faults
• The Byzantine Generals Problem
• Message-optimal protocols for Byzantine Agreement
• Performing Work Efficiently in the Presence of Faults
• Fully Polynomial Byzantine Agreement for n > 3t Processors in t + 1 Rounds
• Information dissemination in distributed systems with faulty units
• Spatial gossip and resource location protocols
• Probability and Computing
• Fault-tolerant broadcasting and gossiping in communication networks