Simple and optimal randomized fault-tolerant rumor spreading

DOI10.1007/S00446-014-0238-ZzbMATH Open1357.68014arXiv1209.6158OpenAlexW2102879646MaRDI QIDQ287985FDOQ287985

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

Publication date: 23 May 2016

Published in: Distributed Computing (Search for Journal in Brave)

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

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

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

zbMATH Keywords

robustnessdistributed computingrandomized algorithmsrumor spreading

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

• Asymptotically optimal randomized rumor spreading
• Gossiping by processors prone to omission failures
• Meeting the deadline, on the complexity of fault-tolerant \textsc{Continuous Gossip}
• On fast and robust information spreading in the vertex-congest model
• Asymptotically optimal randomized rumor spreading
• Meeting the deadline: on the complexity of fault-tolerant continuous gossip
• On the Push&Pull Protocol for Rumor Spreading
• Faster Rumor Spreading: Breaking the logn Barrier

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)