Rumor Spreading in Random Evolving Graphs

Abstract : We analyze randomized broadcast in dynamic networks modeled as edge-Markovian evolving graphs. We prove that, for the practically relevant case in which the birth rate p = \Omega (1 / n), and the dead rate q is constant, randomized broadcast completes w.h.p. in O(log n) time steps. Our result provides the first formal argument demonstrating the robustness of the “push” protocol against network changes.
Type de document :
Article dans une revue
Random Structures and Algorithms, Wiley, 2016, 48 (2), pp.290-312. 〈10.1002/rsa.20586〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01390133
Contributeur : Marie-France Sagot <>
Soumis le : lundi 14 novembre 2016 - 11:37:00
Dernière modification le : mercredi 11 avril 2018 - 01:57:23
Document(s) archivé(s) le : mercredi 15 mars 2017 - 04:04:32

Fichier

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

Identifiants

Collections

Citation

Andrea Clementi, Pierluigi Crescenzi, Carola Doerr, Pierre Fraigniaud, Francesco Pasquale, et al.. Rumor Spreading in Random Evolving Graphs. Random Structures and Algorithms, Wiley, 2016, 48 (2), pp.290-312. 〈10.1002/rsa.20586〉. 〈hal-01390133〉

Partager

Métriques

Consultations de la notice

302

Téléchargements de fichiers

99