Rumor spreading in random evolving graphs |
| |
| Authors: | Andrea Clementi Pierluigi Crescenzi Carola Doerr Pierre Fraigniaud Francesco Pasquale Riccardo Silvestri |
| |
| Affiliation: | 1. Dipartimento di Ingegneria dell'Impresa “M. Lucertini”, Università Tor Vergata di Roma, Roma, Italy;2. Dipartimento di Ingegneria dell'Informazione, Università di Firenze, Firenze, Italy;3. Laboratoire d'Informatique de Paris 6 (LIP6), CNRS and Université Pierre et Marie Curie (Paris 6), Paris Cedex 05, France;4. Laboratoire d'Informatique Algorithmique: Fondements et Applications (LIAFA), CNRS and Université Paris Diderot (Paris 7), Paris Cedex 13, France;5. Dipartimento di Informatica, Sapienza Università di Roma, Roma, Italy |
| |
| Abstract: | ![]()
We analyze randomized broadcast in dynamic networks modeled as edge‐Markovian evolving graphs. The most realistic range of edge‐Markovian parameters yields sparse and disconnected graphs. We prove that, in this setting, the “push” protocol completes with high probability in optimal logarithmic time. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 290–312, 2016 |
| |
| Keywords: | rumor spreading Push protocol dynamic random graphs Markov chains |
|
|
