New for: D3
throughout a graph and the conductance of the graph---a standard measure
of a graph's expansion properties.
We show that for any n-node graph with conductance phi, the classical
PUSH-PULL algorithm distributes a rumor to all nodes of the graph in
O((1/phi)log n) rounds with high probability.
This bound is tight in the sense that there exist graphs where at least
that many rounds are needed.