Protocole de bavardage

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.

Types

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.

Exemple

Soit le graphe 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 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.

Applications

Vie privée

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.

Moniteur système

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

Implémentations dans des logiciels

Notes et références
  1. Alan Demers, Dan Greene, Carl Hauser, Wes Irish, John Larson, Scott Shenker, Howard Sturgis, Dan Swinehart et Doug Terry, Epidemic Algorithms for Replicated Database Maintenance (Proceedings of the Sixth Annual ACM Symposium on Principles of Distributed Computing (Trad:Actes du sixième symposium annuel de l'ACM sur les principes de l'informatique distribuée)), New York, NY, USA, ACM, coll. « PODC '87 », , 1–12 p. (ISBN 978-0-89791-239-6, DOI 10.1145/41840.41841)
  2. Márk Jelasity, « Gossip », dans Self-organising Software, Springer Berlin Heidelberg, (ISBN 978-3-642-17347-9, DOI 10.1007/978-3-642-17348-6_7, lire en ligne), p. 139–162
  3. George Giakkoupis, « Tight bounds for rumor spreading in graphs of a given conductance », 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011), Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, leibniz International Proceedings in Informatics (LIPIcs), vol. 9,‎ , p. 57–68 (ISBN 978-3-939897-25-5, DOI 10.4230/LIPIcs.STACS.2011.57, lire en ligne, consulté le )
  4. Pierre Dellenbach, Aurélien Bellet et Jan Ramon, « Hiding in the Crowd: A Massively Distributed Algorithm for Private Averaging with Malicious Adversaries », arXiv:1803.09984 [cs, stat],‎ (lire en ligne, consulté le )
  5. Benjamin Nguyen, L’anonymisation : Théorie et Pratique, (lire en ligne)
  6. (en) Robbert Van Renesse, Kenneth P. Birman et Werner Vogels, « Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining », ACM Transactions on Computer Systems (TOCS), vol. 21, no 2,‎ , p. 164–206 (ISSN 0734-2071 et 1557-7333, DOI 10.1145/762483.762485, lire en ligne, consulté le )
  7. « Documentation », sur cassandra.apache.org (consulté le )
  8. « AWS Service Health Dashboard - Amazon S3 Availability Event: July 20, 2008 », sur status.aws.amazon.com (consulté le )

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

Liens externes
  • Portail de l’informatique
  • Portail des télécommunications
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.