Rumor Spreading in Random Evolving Graphs

Clementi, Andrea E F; Crescenzi, Pierluigi; Doerr, Carola; Fraigniaud, Pierre; Isopi, Marco; Panconesi, Alessandro; Pasquale, Francesco; Silvestri, Riccardo
In this paper, we aim at analyzing the classical information spreading push protocol in dynamic networks. We consider the edge-Markovian evolving graph model which captures natural temporal dependencies between the structure of the network at time t, and the one at time t + 1. Precisely, a non-edge appears with probability p, while an existing edge dies with probability q. In order to fit with real-world traces, we mostly concentrate our study on the case where p=$\Omega$(1n) and q is constant. We prove that, in this realistic scenario, the push protocol does perform well, completing information spreading in O(logn) time steps, w.h.p., even when the network is, w.h.p., disconnected at every time step (e.g., when pâ‰Șlognn ). The bound is tight. We also address other ranges of parameters p and q (e.g., p + q = 1 with arbitrary p and q, and p=$\Theta$(1n) with arbitrary q). Although they do not precisely fit with the measures performed on real-world traces, they can be of independent interest for other settings. The results in these cases confirm the positive impact of dynamism.
Research areas:
Type of Publication:
In Proceedings
Book title:
ESA Lecture Notes in Computer Science 8125
Hits: 4031

We use cookies to improve our website and your experience when using it. Cookies used for the essential operation of this site have already been set. To find out more about the cookies we use and how to delete them, see our privacy policy.

  I accept cookies from this site.
EU Cookie Directive Module Information