Tight Bounds for Rumor Spreading with Vertex Expansion

George Giakkoupis

We establish a bound for the classic PUSH-PULL rumor spreading protocol on arbitrary graphs, in terms of the vertex expansion of the graph. We show that O(log^2(n)/α) rounds suffic…