Unprotocole de bavardage (enanglaisgossip protocol) ou unalgorithme de bavardage désigne unalgorithme distribué dans unréseau informatiquepair à pair pour propager l'information à tous lesagents du réseau. La formulation d'un protocole de bavardage date d'un article de de Demerset al.[1] L'un des intérêts de ces protocoles est de permettre l'auto-organisation dans les réseaux informatiques sans coordinateurs centraux, tant que lesagents sont suffisamment actifs et connectés.
On peut classer des algorithmes de bavardage en deux types[2], en fonction de leurs tâches :
diffusion de l'information, où, par exemple, des agents peuvent s'informer mutuellement de la survenance d'unévénement ;
agrégation d'informations, où, par exemple, des agents peuvent calculer une valeur collaborativement.
Comme dans la plupart des algorithmes distribués, nous pouvons également identifier qu'un algorithme de bavardage a plusieurs catégories liées à sa conception technique :
Un protocolepush fait référence au type deflux d'informations qui est créé lorsque les agents transmettent des messages à leurs voisins, qu'ils le veuillent ou non.
Un protocole pull fait référence au type de flux d'informations créé lorsque les agents demandent eux-mêmes des messages à leurs voisins.
Un protocole push-pull fait référence au cas où les deux types de flux d'informations sont disponibles.
Le moment du flux d'information :
Un protocolesynchrone se réfère au cas où chaque agent accepte d'envoyer / recevoir des informations à des moments précis.
Un protocoleasynchrone fait référence au cas où chaque agent peut envoyer / recevoir des informations à tout moment.
Une décision dans la conception technique conduit généralement à des performances meilleures ou pires, par exemple dans lavitesse de convergence ou latolérance aux pannes. De plus, certaines décisions de conception peuvent nécessiter des stratégies plus avancées pour prouver des garanties de performances.
Soit legraphe connexe d'un réseau de communication, où l'ensemble dénote les agents et l'ensemble dénote les liens entre eux. Soit, et attribuer chaque avec.
Considérons que les agents visent à calculer collectivement lamoyenne de leurs valeurs assignées.
Soit un protocole de bavardage tel que chaque agent s'engage à montrer son attribut à ses voisins et à mettre à jour demanière itérative la valeur affichée en calculant la moyenne des valeurs affichées par ses voisins.
Si chaque agent s'engage dans le protocole, après quelques itérations, la valeur affichée par chaque agent est égale à la moyenne des valeurs initiales.
Des algorithmes de bavardage peuvent permettre d'effectuer des tâches collaboratives décentralisées tout en préservant la confidentialité des données[4], comme dans unsystème de communications P2P anonyme. Une telle tâche pourrait être, par exemple de calculer la moyenne sur des valeurs individuelles, comme suggéré dans l'exemple donné, et où la confidentialité des données peut être quantifiée, comme laconfidentialité différentielle, lek-anonymat[5], ou tout autre mesure de vie privé. En gardant l'exemple de la moyenne, la valeur individuelle peut suivre un modèle qui dépend d'une statistique sensible d'un agent, et donc si la valeur réelle a été affichée, la statistique sensible peut être déduite par une attaque de reconstruction. Nous pouvons préserver la confidentialité des données en masquant la valeur individuelle sous un bruit (par exemple, unevariable aléatoire gaussienne avec une moyenne de 0). Même si tous les agents d'un réseau de communication font de même, un algorithme de bavardage particulier peut toujours réussir à réaliser la tâche avec une faible erreur. En fin de compte, on obtient un compromis entre l'erreur dans la moyenne et le niveau de confidentialité des données.
Un algorithme de bavardage peut être conçu pour permettre à chaque agent de résumer l'état d'unsystème multi-agent, par exemple lacharge système ou le nombre d'agents actifs. Cela peut être perçu comme unmoniteur système. Une telle tâche peut être réalisée par agrégation, lorsque les agents font la moyenne de leurs descripteurs d'état[6].
