Simple and optimal randomized fault-tolerant rumor spreading

DOI10.1007/s00446-014-0238-zzbMath1357.68014arXiv1209.6158MaRDI QIDQ287985

Shay Moran, Shlomo Moran, Carola Doerr, Benjamin Doerr

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

robustness; distributed computing; randomized algorithms; rumor spreading

Mathematics Subject Classification ID

68M14: Distributed systems

68M15: Reliability, testing and fault tolerance of networks and computer systems

68W20: Randomized algorithms

68W15: Distributed algorithms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Adaptive broadcasting with faulty nodes
• Initial failures in distributed computations
• The shortest-path problem for graphs with random arc-lengths
• Ramanujan graphs
• 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
• Fast Distributed Algorithms for Computing Separable Functions
• On Spreading a Rumor
• Global computation in a poorly connected world
• Probability and Computing
• Concentration of Measure for the Analysis of Randomized Algorithms