Bit-complexité des protocoles de gossip - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

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

Dates et versions

inria-00474538 , version 1 (22-04-2010)

Identifiants

  • HAL Id : inria-00474538 , version 1

Citer

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. ⟨inria-00474538⟩
54 Consultations
84 Téléchargements

Partager

Gmail Facebook X LinkedIn More