Table of Contents
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. ObjectifDans 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 coursModèle de calcul et spécifications
Résultat d'impossibilité de Santoro et Widmayer. Algorithmes de consensus décisionnel
Consensus décisionnel et agents byzantins
Consensus stabilisant
Consensus asymptotique
Consensus asymptotique contraint
Pré-requisNotions de base en algèbre linéaire, théorie des graphes et en algorithmique distribuée. Notes de cours et exercicesNotes de cours :
Articles :
Feuilles d'exercices et devoir : Previous : devoirmaison13.pdf exam13.pdf dm16.pdf exam16.pdf Messages :
Bibliographie
Cours reliés |