Rumor spreading in random evolving graphs1. Issue 2 (30th March 2015)

• Record Type: Journal Article
• Authors: Clementi, Andrea; Crescenzi, Pierluigi; Doerr, Carola; Fraigniaud, Pierre; Pasquale, Francesco; Silvestri, Riccardo
• Is Part Of: Random structures & algorithms. Volume 48:Issue 2(2016)
• Page Start: 290
• Page End: 312
• Publication Date: 2015-03-30
• Subjects: rumor spreading -- Push protocol -- dynamic random graphs -- Markov chains; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20586
• Languages: English
• ISSNs: 1042-9832

Abstract

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