Skip to Main content Skip to Navigation
Journal articles

Rumor Spreading and Conductance

Abstract : In this article, we study the completion time of the PUSH-PULL variant of rumor spreading, also known as randomized broadcast. We show that if a network has n nodes and conductance φ then, with high probability, PUSH-PULL will deliver the message to all nodes in the graph within O(log n/φ) many communication rounds. This bound is best possible. We also give an alternative proof that the completion time of PUSH-PULL is bounded by a polynomial in log n/φ, based on graph sparsification. Although the resulting asymptotic bound is not optimal, this proof shows an interesting and, at the outset, unexpected connection between rumor spreading and graph sparsification. Finally, we show that if the degrees of the two endpoints of each edge in the network differ by at most a constant factor, then both PUSH and PULL alone attain the optimal completion time of O(log n/φ), with high probability.
Document type :
Journal articles
Complete list of metadata
Contributor : George Giakkoupis Connect in order to contact the contributor
Submitted on : Monday, December 3, 2018 - 12:29:06 AM
Last modification on : Tuesday, October 19, 2021 - 11:04:41 AM
Long-term archiving on: : Monday, March 4, 2019 - 12:41:02 PM


Files produced by the author(s)



Flavio Chierichetti, George Giakkoupis, Silvio Lattanzi, Alessandro Panconesi. Rumor Spreading and Conductance. Journal of the ACM (JACM), Association for Computing Machinery, 2018, 65 (4), pp.17:1-17:21. ⟨10.1145/3173043⟩. ⟨hal-01942162⟩



Record views


Files downloads