Protocole de bavardage

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.

• 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].