Rumor spreading in random evolving graphs
Andrea E. F. Clementi, Pierluigi Crescenzi, Carola Doerr, Pierre Fraigniaud, Francesco Pasquale, Riccardo Silvestri · Random Structures and Algorithms · 2015
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