Rumor Spreading in Random Evolving Graphs
Résumé
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.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...