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.
Type de document :
Communication dans un congrès
25th ACM-SIAM Symposium on Discrete Algorithms (SODA), Jan 2014, Portland, OR, United States. pp.801 - 815, 2014, 〈10.1137/1.9781611973402.59〉
Liste complète des métadonnées

Littérature citée [26 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01097140
Contributeur : George Giakkoupis <>
Soumis le : vendredi 19 décembre 2014 - 00:18:21
Dernière modification le : jeudi 15 novembre 2018 - 11:57:36
Document(s) archivé(s) le : lundi 23 mars 2015 - 17:30:56

Fichier

soda14_vtight.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

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, 2014, 〈10.1137/1.9781611973402.59〉. 〈hal-01097140〉

Partager

Métriques

Consultations de la notice

421

Téléchargements de fichiers

106