Simple and optimal randomized fault-tolerant rumor spreading
From MaRDI portal
Publication:287985
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
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