View article

We show that if a connected graph with nodes has conductance φ then rumour spreading, also known as randomized broadcast, successfully broadcasts a message within ~O(φ^-1 • log n), many rounds with high probability, regardless of the source, by using the PUSH-PULL strategy. The ~O(••) notation hides a polylog φ^-1 factor. This result is almost tight since there exists graph of n nodes, and conductance φ, with diameter Ω(φ^-1 • log n). If, in addition, the network satisfies some kind of uniformity condition on the degrees, our analysis implies that both both PUSH and PULL, by themselves, successfully broadcast the message to every node in the same number of rounds.