Skip to Main content Skip to Navigation
Conference papers

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
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : George Giakkoupis Connect in order to contact the contributor
Submitted on : Friday, December 19, 2014 - 12:46:49 AM
Last modification on : Thursday, January 20, 2022 - 4:20:00 PM
Long-term archiving on: : Monday, March 23, 2015 - 5:31:14 PM


Files produced by the author(s)



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⟩



Record views


Files downloads