Randomized Rumor Spreading in Dynamic Graphs - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2014

Randomized Rumor Spreading in Dynamic Graphs

Résumé

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.
Fichier principal
Vignette du fichier
icalp14_dynamic.pdf (332.54 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-01097142 , version 1 (19-12-2014)

Identifiants

Citer

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⟩
398 Consultations
956 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More