Bit-complexité des protocoles de gossip

Nous etudions le probleme du \emph{gossip} (i.e., diffusion de rumeurs) dans le modele des appels aleatoires. Considerons $n$ noeuds communiquant en parallele par etape. A chaque etape, un ensemble (potentiellement vide) de \emph{rumeurs} est genere a chaque noeud, la meme rumeur pouvant etre generee simultanement par plusieurs noeuds. L'objectif est de diffuser ces rumeurs a tous les noeuds. Pour ce faire, a chaque etape, chaque noeud appelle un autre noeud choisi uniformement aleatoirement parmi l'ensemble de tous les noeuds, et un noeud ne peut alors communiquer qu'avec le noeud qu'il a appele, et les noeuds qui l'ont potentiellement appele. Dans ce modele, Karp et ses co-auteurs~\cite{Karp2000} ont montre qu'aucun algorithme de gossip ne peut etre a la fois optimal en temps (i.e., s'executer en $O(\log n)$ etapes) et en volume de communication (i.e., s'executer en transmettant au plus $O(n)$ messages). En particulier, ils ont montre que tout algorithme de gossip n'utilisant pas les IDs des noeuds et diffusant toute rumeur en $O(\log n)$ etapes doit echanger $\Omega(n\log\log n)$ messages par rumeur. Karp et ses co-auteurs ont egalement montre que ce compromis peut etre atteint. Dans cet article, nous etudions le volume de communication estime en nombre de bits echanges plutot 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)$ etapes doit echanger $\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)$ etapes, en echangeant $O(n(b+\log\log n\log b))$ bits pour une rumeur de $b$ bits. Ces resultats demontrent que contrairement a ce qu'il peut sembler lorsque l'on mesure le volume de communication en nombre de messages, il est possible d'etre a la fois optimal en temps (i.e., s'executer en $O(\log n)$ etapes) et en volume de communication (i.e., s'executer en transmettant au plus $O(nb)$ bits), sauf pour des rumeurs extremement petites, de taille $b\ll\log\log n \log\log\log n$ bits.