L'article doit être débarrassé d'une partie de son jargon (septembre 2020).

Sa qualité peut être largement améliorée en utilisant un vocabulaire plus directement compréhensible. Discutez des points à améliorer en page de discussion.

Cet article est orphelin. Moins de trois articles lui sont liés (avril 2020).

Vous pouvez aider en ajoutant des liens vers [[Protocole de bavardage]] dans les articles relatifs au sujet.

Un protocole de bavardage (en anglais, gossip protocol) ou un algorithme de bavardage désigne un algorithme distribué dans un réseau informatique pair à pair pour propager l'information à tous les agents du réseau. La formulation d'un protocole de bavardage date d'un article de 1987 de Demers et 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 les agents 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 en collaboration une valeur.

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 :

• La direction de l'information^[3] :
  1. Un protocole push fait référence au type de flux d'informations qui est créé lorsque les agents transmettent des messages à leurs voisins, qu'ils le veuillent ou non.
  2. 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.
  3. 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 :
  1. Un protocole synchrone se réfère au cas où chaque agent accepte d'envoyer / recevoir des informations à des moments précis.
  2. Un protocole asynchrone 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 la vitesse de convergence ou la tolé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 ${\displaystyle G=(V,E)}$ le graphe connexe d'un réseau de communication, où l'ensemble ${\displaystyle V}$ dénote les agents et l'ensemble ${\displaystyle E}$ dénote les liens entre eux.
Soit ${\displaystyle \phi :V\rightarrow \mathbb {R} }$, et attribuer chaque ${\displaystyle v\in V}$ avec ${\displaystyle \phi (v)}$.

Considérons que les agents visent à calculer collectivement la moyenne de leurs valeurs assignées.

Soit un protocole de bavardage tel que chaque agent s'engage à montrer son attribut à ses voisins et à mettre à jour de maniè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 un systè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 la confidentialité différentielle, le k-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, une variable 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'un système multi-agent, par exemple la charge système ou le nombre d'agents actifs. Cela peut être perçu comme un moniteur 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].

• Apache Cassandra (un système de gestion de base de données distribuée) utilise un algorithme de bavardage dans son optimisation dans le routage, spécifiquement pour la tolérance aux pannes^[7].
• Amazon Simple Storage Service (un service de cloud computing) a signalé l'utilisation d'un algorithme de bavardage pour améliorer la tolérance aux pannes, spécifiquement pour la détection de serveurs défaillants^[8].

• (en) Fatemeh Rahimian, Gossip-based Algorithms for Information Dissemination and Graph Clustering, Stockholm, Royal Institute of Technology (thèse de doctorat), 2014, 22 p. (ISBN 978-91-7595-108-9)

• « Les protocoles réseaux de bavardage »

• Portail de l’informatique
• Portail des télécommunications