Skip to Main content Skip to Navigation
Conference papers

Tight Bounds for Rumor Spreading with Vertex Expansion

George Giakkoupis 1 
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : We establish a bound for the classic PUSH-PULL rumor spreading protocol on general graphs, in terms of the vertex expansion of the graph. We show that O(log^2 (n) / α) rounds suffice with high probability to spread a rumor from any single node to all n nodes, in any graph with vertex expansion at least α. This bound matches a known lower bound, and settles the natural question on the relationship between rumor spreading and vertex expansion asked by Chierichetti, Lattanzi, and Panconesi (SODA 2010). Further, some of the arguments used in the proof may be of independent interest, as they give new insights, for example, on how to choose a small set of nodes in which to plant the rumor initially, to guarantee fast rumor spreading.
Document type :
Conference papers
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download
Contributor : George Giakkoupis Connect in order to contact the contributor
Submitted on : Friday, December 19, 2014 - 12:18:21 AM
Last modification on : Thursday, January 20, 2022 - 4:20:01 PM
Long-term archiving on: : Monday, March 23, 2015 - 5:30:56 PM


Files produced by the author(s)



George Giakkoupis. Tight Bounds for Rumor Spreading with Vertex Expansion. 25th ACM-SIAM Symposium on Discrete Algorithms (SODA), Jan 2014, Portland, OR, United States. pp.801 - 815, ⟨10.1137/1.9781611973402.59⟩. ⟨hal-01097140⟩



Record views


Files downloads