Rumor Spreading in Random Evolving Graphs - Archive ouverte HAL Access content directly
Journal Articles Random Structures and Algorithms Year : 2016

Rumor Spreading in Random Evolving Graphs

(1) , (2, 3) , (4) , (1) , (1) , (1)
1
2
3
4

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.
Fichier principal
Vignette du fichier
rsa2016.pdf (308.13 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01390133 , version 1 (14-11-2016)

Identifiers

Cite

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

Altmetric

Share

Gmail Facebook Twitter LinkedIn More