Responsable : Olivier Bournez, Professeur, École polytechnique.

Équipe pédagogique :

• Olivier Bournez (Professeur à l'École polytechnique, LIX)
• Bernadette Charron-Bost (Directrice de Recherche CNRS, LIX)
• Sylvain Perifel (Maître de Conférence Université Paris 7, LIAFA)

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.

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.

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

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

Notes de cours :

1. Sur le théorème de Perron-Frobenius : chapter1.pdf
2. Sur le théorème de Moreau : chapter2.pdf
3. Sur les vitesses de convergence : vitesse.pdf

Articles :

• Nicola Santoro and Peter Widmayer, Time is not a Healer, Proceedings of the 6th Annual Symposium on Theoretical Aspects of Computer Science (STACS 89).
• 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).

• 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 :

1. model.pdf

• Le premier cours a lieu le vendredi 13 septembre.

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

• 2-8-1 Théorie non-séquentielle des systèmes distribués
• 2-17-1 Fondements sur la modélisation des réseaux
• 2-18-1 Algorithmique distribuée pour les réseaux
• 2-18-2 Algorithmique distribuée avec mémoire partagée
• 2-19 Méthodes informatiques pour la biologie systémique et synthétique
• 2-29-1 Algorithmique des graphes