Rumor spreading in random evolving graphs1. Issue 2 (30th March 2015) - Clementi, Andrea; Crescenzi, Pierluigi; Doerr, Carola; Fraigniaud, Pierre; Pasquale, Francesco; Silvestri, Riccardo
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