Rumor spreading and conductance
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 themessage to all nodes in the graph within O(logn/φ) 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 logn/φ, based on graph sparsification.