Randomized Rumor Spreading in Dynamic Graphs

Abstract : We consider the well-studied rumor spreading model in which nodes contact a random neighbor in each round in order to push or pull the rumor. Unlike most previous works which focus on static topologies, we look at a dynamic graph model where an adversary is allowed to rewire the connections between vertices before each round, giving rise to a sequence of graphs, G1, G2, . . . Our first result is a bound on the rumor spreading time in terms of the conductance of those graphs. We show that if the degree of each node does not change much during the protocol (that is, by at most a constant factor), then the spread completes within t rounds for some t such that the sum of conductances of the graphs G1 up to Gt is O(log n). This result holds even against an adaptive adversary whose decisions in a round may depend on the set of informed vertices before the round, and implies the known tight bound with conductance for static graphs. Next we show that for the alternative expansion measure of vertex expansion, the situation is different. An adaptive adversary can delay the spread of rumor significantly even if graphs are regular and have high expansion, unlike in the static graph case where high expansion is known to guarantee fast rumor spreading. However, if the adversary is oblivious, i.e., the graph sequence is decided before the protocol begins, then we show that a bound close to the one for the static case holds for any sequence of regular graphs.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01097142
Contributor : George Giakkoupis <>
Submitted on : Friday, December 19, 2014 - 12:46:49 AM
Last modification on : Thursday, November 15, 2018 - 11:57:36 AM
Document(s) archivé(s) le : Monday, March 23, 2015 - 5:31:14 PM

File

icalp14_dynamic.pdf
Files produced by the author(s)

Identifiers

Citation

George Giakkoupis, Thomas Sauerwald, Alexandre Stauffer. Randomized Rumor Spreading in Dynamic Graphs. 41st International Colloquium on Automata, Languages and Programming (ICALP), Jul 2014, Copenhagen, Denmark. pp.495 - 507, ⟨10.1007/978-3-662-43951-7_42⟩. ⟨hal-01097142⟩

Share

Metrics

Record views

522

Files downloads

694