
doi: 10.1145/3173043
handle: 11573/1168838
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.
[INFO] Computer Science [cs], Distributed algorithms; Gossip algorithms; Graph conductance; Graph sparsification; Randomized algorithms; Randomized broadcast; Software; Control and Systems Engineering; Information Systems; Hardware and Architecture; Artificial Intelligence
[INFO] Computer Science [cs], Distributed algorithms; Gossip algorithms; Graph conductance; Graph sparsification; Randomized algorithms; Randomized broadcast; Software; Control and Systems Engineering; Information Systems; Hardware and Architecture; Artificial Intelligence
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 12 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
