Hugues Mercier
ABSTRACT
We consider the problem of reliable gossip/epidemic dissemination in a network of n processes using push and pull algorithms. We generalize the random phone call model so that processes can refuse to push a rumor or answer pull requests. With this relaxation, we show that it is possible to disseminate a rumor to all processes with high probability using Theta(ln n) rounds of communication and only n+O(n / ln n) messages, both of which are optimal and achievable with push-pull and pull-only algorithms. Our algorithms are strikingly simple, address-oblivious and thus fully distributed. This contradicts a well-known result of Karp et al. stating that any address-oblivious algorithm requires Omega(n ln ln n) messages. We also develop precise estimates of the number of rounds required in the push and pull phases of our algorithms to guarantee dissemination to all processes with a certain probability. For the push phase, we focus on a practical infect upon contagion approach that balances the load evenly across all processes. As an example, our push-pull algorithm requires 17 rounds to disseminate a rumor to all processes with probability 1 - 10^-100 in a network of one million processes with a communication overhead of only 0.4%.
- Robert M Corless, Gaston H Gonnet, David EG Hare, David J Jeffrey, and Donald E Knuth. 1996. On the Lambert W function. Advances in Computational mathematics 5, 1 (1996), 329--359.Google Scholar
- Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart, and Doug Terry. 1987. Epidemic Algorithms for Replicated Database Maintenance. In Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (PODC '87). ACM, New York, NY, USA, 1--12. x0--89791--239-X https://doi.org/10.1145/41840.41841Google ScholarDigital Library
- Richard M. Karp, Christian Schindelhauer, Scott Shenker, and Berthold Vöcking. 2000. Randomized Rumor Spreading. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12--14 November 2000, Redondo Beach, California, USA. IEEE Computer Society, 565--574. x0--7695-0850--2 https://doi.org/10.1109/SFCS.2000.892324Google ScholarDigital Library
- Boris Koldehofe. 2004. Simple gossiping with balls and bins. Stud. Inform. Univ. 3, 1 (2004), 43--60.Google Scholar
Index Terms
- Brief Announcement: Optimal Address-Oblivious Epidemic Dissemination
Recommendations
Brief Announcement: An Exponential Separation Between Randomized and Deterministic Complexity in the LOCAL Model
PODC '16: Proceedings of the 2016 ACM Symposium on Principles of Distributed ComputingOver the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL model, such as maximal matching, MIS, vertex coloring, and edge-coloring. For most problems the best randomized algorithm is at least exponentially ...
Brief Announcement: Symmetry Breaking in the CONGEST Model: Time- and Message-Efficient Algorithms for Ruling Sets
PODC '17: Proceedings of the ACM Symposium on Principles of Distributed ComputingWe study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. Our work is motivated by the following central question: can we break the long-...
Brief Announcement: A Randomness-efficient Massively Parallel Algorithm for Connectivity
PODC'21: Proceedings of the 2021 ACM Symposium on Principles of Distributed ComputingWe give a randomness-efficient Massively Parallel Computation (MPC) algorithm for deciding whether an undirected graph is connected. For Connectivity on n-vertex, m-edge graphs whose components have diameter at most D = 2o(log n/ log log n), our ...
Comments