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 metadatas

https://hal.inria.fr/hal-01942162
Contributor : George Giakkoupis <>
Submitted on : Monday, December 3, 2018 - 12:29:06 AM
Last modification on : Friday, September 13, 2019 - 9:51:33 AM
Long-term archiving on : Monday, March 4, 2019 - 12:41:02 PM

File

jacm2018RSconductance.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

84

Files downloads

326