Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

This is an old revision of the document!


2.33.1 Consensus dans les réseaux multiagents (24h, 3ECTS)

Responsable : Olivier Bournez, Professeur, École polytechnique.

Équipe pédagogique :

Édition 2019-2020 :

Le cours est donné par Bernadette Charron-Bost le vendredi de 12h45 à 15h45 au Batiment Sophie Germain (P7), salle 1014. La première séance a lieu le 13 septembre.

Langue : français ou en anglais selon la demande ; documentation en anglais.

Objectif

Dans tous les problèmes de consensus, chaque agent d'un réseau multiagent a une valeur de départ et produit une suite de valeurs. Les agents doivent finir par adopter une valeur de sortie commune qui doit être une des valeurs initiales ou une fonction des valeurs initiales, auquel cas on parle de consensus contraint. Ces problèmes interviennent dans un grand nombre d'applications comme la réplication des bases de données, la synchronisation des agents dans les systèmes naturels, les déplacements dans les systèmes d'agents autonomes ou, plus récemment, dans les technologies blockchain.

Le consensus décisionnel est un problème d'accord fondamental où chaque agent a conscience d'avoir atteint la valeur de consensus, contrairement au consensus stabilisant ou au consensus asymptotique où il est seulement requis que les agents convergent vers la même valeur. L'objectif de ce cours est d'étudier la résolubilité et la complexité de ces différents problèmes de consensus selon les propriétés du graphe de communication, le modèle d'agents (par exemple, agents anonymes ou avec identifiants) ou encore le type des défaillances possibles.

Plan du cours

Modèle de calcul et spécifications

  • Modèle de calcul et rounds synchronisés ; le modèle Heard-Of.
  • Graphes dynamiques ; systèmes d'influence
  • Spécifications du consensus : consensus décisionnel, consensus stabilisant et consensus asymptotique. Spécifications contraintes.

Résultat d'impossibilité de Santoro et Widmayer.

Algorithmes de consensus décisionnel

  • Algorithme à temps de décision borné
  • Algorithmes de type DLS
  • Algorithmes randomisés

Consensus décisionnel et agents byzantins

  • Résultat d'impossibilité de Shostak, Pease et Lamport
  • Algorithme EIGByz

Consensus stabilisant

  • Connectivité nécessaire
  • Algorithme MinMax

Consensus asymptotique

  • Algorithmes de moyenne et matrices de Markov
  • Théorème de Cao, Morse et Anderson
  • Théorème de Moreau ; applications aux systèmes naturels

Consensus asymptotique contraint

  • Résultat d'impossibilité de Hendrickx et Tsitsiklis
  • Calcul asymptotique de la moyenne

Pré-requis

Notions de base en algèbre linéaire, théorie des graphes et en algorithmique distribuée.

Notes de cours et exercices

Messages :

  • Le premier cours a lieu le vendredi 13 septembre.

Bibliographie

  • Dimitri P. Bertsekas and John N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, 1997.
  • Bernard Chazelle. Natural Algorithms and Influence Systems. Communications of the ACM, vol. 55(12), december 2012.
  • Nancy A. Lynch. Distributed Algorithms. Morgan Kaufmann, 1996.
  • Luc Moreau. Stability of Multiagent Systems With Time-Dependent Communication Links, IEEE Transactions on Automatic Control, Vol. 50(2), february 2005.
  • Shlomo Sternberg. Dynamical Systems. Dover Publications. 2010.

Cours reliés

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA