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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [36 references]  Display  Hide  Download

https://hal.inria.fr/hal-01390133
Contributor : Marie-France Sagot <>
Submitted on : Monday, November 14, 2016 - 11:37:00 AM
Last modification on : Wednesday, August 21, 2019 - 9:02:02 PM
Long-term archiving on : Wednesday, March 15, 2017 - 4:04:32 AM

File

rsa2016.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

398

Files downloads

242