Simple and optimal randomized fault-tolerant rumor spreading

DOI10.1007/S00446-014-0238-ZMaRDI QIDQ287985zbMATH OpenOpenAlexFDO

Authors Benjamin Doerr, Carola Doerr, Shay Moran, Shlomo Moran

Publication date 23 May 2016

Published in Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

distributed computingrandomized algorithmsrobustnessrumor spreading

Mathematics Subject Classification ID

Distributed systems (68M14) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Randomized algorithms (68W20)

Abstract: We revisit the classic problem of spreading a piece of information in a group of $n$ fully connected processors. By suitably adding a small dose of randomness to the protocol of Gasienic and Pelc (1996), we derive for the first time protocols that (i) use a linear number of messages, (ii) are correct even when an arbitrary number of adversarially chosen processors does not participate in the process, and (iii) with high probability have the asymptotically optimal runtime of $O(logn)$ when at least an arbitrarily small constant fraction of the processors are working. In addition, our protocols do not require that the system is synchronized nor that all processors are simultaneously woken up at time zero, they are fully based on push-operations, and they do not need an a priori estimate on the number of failed nodes. Our protocols thus overcome the typical disadvantages of the two known approaches, algorithms based on random gossip (typically needing a large number of messages due to their unorganized nature) and algorithms based on fair workload splitting (which are either not {time-efficient} or require intricate preprocessing steps plus synchronization).

Recommendations

• Asymptotically optimal randomized rumor spreading
• Asymptotically optimal randomized rumor spreading
• scientific article; zbMATH DE number 6783407
• Simple, fast and deterministic gossip and rumor spreading
• Breaking the \(\log n\) barrier on rumor spreading

Cites work

• Adaptive broadcasting with faulty nodes
• Analyzing randomized search heuristics: tools from probability theory
• Concentration of Measure for the Analysis of Randomized Algorithms
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Fast Distributed Algorithms for Computing Separable Functions
• Global computation in a poorly connected world
• scientific article; zbMATH DE number 996442 (Why is no real title available?)
• scientific article; zbMATH DE number 1301967 (Why is no real title available?)
• scientific article; zbMATH DE number 765034 (Why is no real title available?)
• Initial failures in distributed computations
• On Spreading a Rumor
• On the construction of pseudorandom permutations: Luby-Rackoff revisited
• Optimal adaptive broadcasting with a bounded fraction of faulty nodes
• Probability and Computing
• Quasi-random rumor spreading: reducing randomness can be costly
• Ramanujan graphs
• The shortest-path problem for graphs with random arc-lengths
• Tolerating a linear number of faults in networks of bounded degree

Cited in

(8)

• Asymptotically optimal randomized rumor spreading
• Faster Rumor Spreading: Breaking the logn Barrier
• Asymptotically optimal randomized rumor spreading
• Spreading Rumors Rapidly Despite an Adversary
• Meeting the deadline, on the complexity of fault-tolerant \textsc{Continuous Gossip}
• On the Push&Pull Protocol for Rumor Spreading
• Meeting the deadline: on the complexity of fault-tolerant continuous gossip
• Gossiping by processors prone to omission failures

This page was built for publication: Simple and optimal randomized fault-tolerant rumor spreading

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