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

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cours:c-2-33-1 [2016/11/24 16:42]
charron-bost [Notes de cours et exercices]
cours:c-2-33-1 [2019/09/11 18:44] (current)
charron-bost [Notes de cours et exercices]
Line 1: Line 1:
  
-==== 2.33.1 Coordination dans les réseaux multi-agents (24h, 3ECTS) =====+==== 2.33.1 Consensus dans les réseaux multiagents (24h, 3ECTS) =====
  
 Responsable : Olivier Bournez, Professeur, École polytechnique. Responsable : Olivier Bournez, Professeur, École polytechnique.
Line 11: Line 11:
  
  
-===== Édition 2016-2017 :  =====+===== Édition 2019-2020 :  =====
  
-Le cours est donné par Bernadette Charron-Bost le lundi de 8h45 à 11h45 au Batiment Sophie Germain (P7), salle 2035. La première séance a lieu le 19 septembre.+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.
  
  
Line 21: Line 21:
 ===== Objectif ===== ===== Objectif =====
  
-Les phénomènes de coordination et de synchronisation dans un grand nombre de systèmes physiques ou biologiques (synchronisation d'oscillateurs couplésvol groupé d'oiseaux, synchronisation de lucioles ou encore diffusion de rumeurs) sont modélisés par des algorithmes de consensus. Du fait de leur grande robustesse et adaptabilité, ces algorithmes naturels peuvent être avantageusement utilisés pour la conception de systèmes multi-agents artificiels (fusion de données dans un réseau de capteurs, protocoles de répartition dynamique de charge, contrôle de groupes de robots ou encore rendez-vous spatiaux). +Dans tous les problèmes de consensuschaque 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 contraintCes 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.
- +
-L'objectif de ce cours est d'étudier la calculabilité et la complexité du ** problème du consensus ** dans un système d'agents qui interagissent à travers un réseau dynamique. Nous étudierons plus particulièrement le cas des ** systèmes d'influence ** où le graphe de communication (ou d'influence) est une fonction de l'état du système et qui permettent de modéliser certains comportement collectifs en dynamique d'opinion ou en biologie.+
  
 +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  ===== ===== Plan du cours  =====
  
-Consensus dans les réseaux multi-agents  +Modèle de calcul et spécifications
-     * Problème du consensus et algorithmes de moyenne +
-     * Analyse matricielle et chaines de Markov +
-     * Consensus dans les modèles de réseaux dynamiques +
-     * Consensus dans le cas d'interactions bidirectionnelles +
  
-Propriétés et applications  +     * Modèle de calcul et rounds synchronisés ; le modèle// Heard-Of//. 
-     * Complexité en temps et vitesse de convergence +     * Graphes dynamiques ; systèmes d'influence 
-     * Robustesse des algorithmes de moyenne ; consensus quantifié +     * Spécifications du consensus : consensus décisionnel, consensus stabilisant et consensus asymptotique. Spécifications contraintes. 
-     * Asynchronisme des interactions +      
-     * Applications+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
    
-Systèmes d'influence  +Consensus décisionnel et agents byzantins 
-     * Définition ; cas des systèmes diffusifs + 
-     * Modèle de Hegselmann-Krause en dynamique d'opinions +     * Résultat d'impossibilité de //Shostak, Pease et Lamport// 
-     * Modèle de Cucker-Smale-Vicsek pour l'étude du flocking+     * 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 ===== ===== Pré-requis =====
  
Line 52: Line 68:
  
 **Notes de cours :** **Notes de cours :**
 +
   - Sur le théorème de Perron-Frobenius : {{:cours:upload:chapter1.pdf|}}   - Sur le théorème de Perron-Frobenius : {{:cours:upload:chapter1.pdf|}}
   - Sur le théorème de Moreau : {{:cours:upload:chapter2.pdf|}}   - Sur le théorème de Moreau : {{:cours:upload:chapter2.pdf|}}
Line 59: Line 76:
  
 **Articles :** **Articles :**
 +  * [[https://link.springer.com/content/pdf/10.1007/BFb0028994.pdf|Nicola Santoro and Peter Widmayer, Time is not a Healer, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS 89)]]. 
 +  * [[https://groups.csail.mit.edu/tds/papers/Lynch/jacm85.pdf|Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson, Impossibility of Distributed Consensus with One Faulty Process, Journal of the ACM, vol. 32(2), April 1985.]]
   * Bernard Chazelle, Natural Algorithms and Influence Systems, CACM, vol. 55(12).   * Bernard Chazelle, Natural Algorithms and Influence Systems, CACM, vol. 55(12).
  
-  * [[http://www.ent.mrt.ac.lk/iml/paperbase/TAC%20Collection/TAC/2005/february/4.pdf|Luc Moreau, Stability of Multiagent Systems With Time-Dependent Communication Links, IEEE Transactions on Automatic Control, Vol. 50(2), february 2005]]+  * [[http://www.ent.mrt.ac.lk/iml/paperbase/TAC%20Collection/TAC/2005/february/4.pdf|Luc Moreau, Stability of Multiagent Systems With Time-Dependent Communication Links, IEEE Transactions on Automatic Control, Vol. 50(2), February 2005]]
  
 **Feuilles d'exercices et devoir :** **Feuilles d'exercices et devoir :**
-  -  {{:cours:upload:surete.pdf|}} +  - {{:cours:upload:model.pdf|}} 
-  - {{:cours:upload:dm16.pdf|}} + 
  
      
 ===== Messages : ===== ===== Messages : =====
  
-  * Le premier cours a lieu le lundi 19 septembre.  +  * Le premier cours a lieu le vendredi 13 septembre.  
-  * Devoir à rendre le 17 novembre (fichier dm16.pdf). +  
-  * Pas de cours le lundi 31 octobre. +
  
  
 
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