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.
Type de document :
Communication dans un congrès
41st International Colloquium on Automata, Languages and Programming (ICALP), Jul 2014, Copenhagen, Denmark. pp.495 - 507, 2014, 〈10.1007/978-3-662-43951-7_42〉
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01097142
Contributeur : George Giakkoupis <>
Soumis le : vendredi 19 décembre 2014 - 00:46:49
Dernière modification le : jeudi 15 novembre 2018 - 11:57:36
Document(s) archivé(s) le : lundi 23 mars 2015 - 17:31:14

Fichier

icalp14_dynamic.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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, 2014, 〈10.1007/978-3-662-43951-7_42〉. 〈hal-01097142〉

Partager

Métriques

Consultations de la notice

458

Téléchargements de fichiers

621