Bit-complexité des protocoles de gossip

Résumé : Nous étudions le problème du \emph{gossip} (i.e., diffusion de rumeurs) dans le modèle des appels aléatoires. Considérons $n$ noeuds communiquant en parallèle par étape. A chaque étape, un ensemble (potentiellement vide) de \emph{rumeurs} est généré à chaque noeud, la même rumeur pouvant être générée simultanément par plusieurs noeuds. L'objectif est de diffuser ces rumeurs à tous les noeuds. Pour ce faire, à chaque étape, chaque noeud appelle un autre noeud choisi uniformément aléatoirement parmi l'ensemble de tous les noeuds, et un noeud ne peut alors communiquer qu'avec le noeud qu'il a appelé, et les noeuds qui l'ont potentiellement appelé. Dans ce modèle, Karp et ses co-auteurs~\cite{Karp2000} ont montré qu'aucun algorithme de gossip ne peut être à la fois optimal en temps (i.e., s'exécuter en $O(\log n)$ étapes) et en volume de communication (i.e., s'exécuter en transmettant au plus $O(n)$ messages). En particulier, ils ont montré que tout algorithme de gossip n'utilisant pas les IDs des noeuds et diffusant toute rumeur en $O(\log n)$ étapes doit échanger $\Omega(n\log\log n)$ messages par rumeur. Karp et ses co-auteurs ont également montré que ce compromis peut être atteint. Dans cet article, nous étudions le volume de communication estimé en nombre de bits échangés plutôt qu'en nombre de messages. Nous montrons tout d'abord que tout algorithme de gossip n'utilisant pas les IDs des noeuds et diffusant toute rumeur en $O(\log n)$ étapes doit échanger $\Omega(n (b+\log\log n))$ bits pour diffuser une rumeur de $b$ bits. Nous proposons alors un algorithme de gossip n'utilisant pas les IDs des noeuds qui diffuse toute rumeur en $O(\log n)$ étapes, en échangeant $O(n(b+\log\log n\log b))$ bits pour une rumeur de $b$ bits. Ces résultats démontrent que contrairement à ce qu'il peut sembler lorsque l'on mesure le volume de communication en nombre de messages, il est possible d'être à la fois optimal en temps (i.e., s'exécuter en $O(\log n)$ étapes) et en volume de communication (i.e., s'exécuter en transmettant au plus $O(nb)$ bits), sauf pour des rumeurs extrêmement petites, de taille $b\ll\log\log n \log\log\log n$ bits.
Type de document :
Communication dans un congrès
12èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2010), May 2010, Belle dune, France. pp.0-0, 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00474538
Contributeur : Pierre Fraigniaud <>
Soumis le : jeudi 22 avril 2010 - 11:11:00
Dernière modification le : jeudi 15 novembre 2018 - 20:26:56
Document(s) archivé(s) le : lundi 22 octobre 2012 - 15:15:08

Fichier

final-AlgoTel2010.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00474538, version 1

Collections

Citation

Pierre Fraigniaud, Giakkoupis George. Bit-complexité des protocoles de gossip. 12èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2010), May 2010, Belle dune, France. pp.0-0, 2010. 〈inria-00474538〉

Partager

Métriques

Consultations de la notice

220

Téléchargements de fichiers

88