Équipe pédagogique :

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

LE COURS DU JEUDI 6 OCTOBRE EST ANNULE.

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

Le cadre de ce cours est celui d'un réseau synchrone d'agents, reliés par un graphe de communication, qui ont chacun une valeur de départ et une variable de sortie. Dans tous les problèmes de consensus, ces variables de sortie doivent converger vers une valeur commune. On distingue trois grands types de consensus, à savoir le consensus irrévocable, le consensus stabilisant et le consensus asymptotique, selon que la convergence a lieu en temps borné, en temps fini ou asymptotiquement. Ces différents problèmes de consensus 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.

Lorsque la valeur limite doit être égale à une certaine fonction f des valeurs initiales, on parle de consensus f-contraint. La fonction f est dite calculable (en temps borné, en temps fini ou asymptotiquement) dans un réseau multi-agents selon que le consensus f-contraint correspondant est réalisable dans ce réseau. Un exemple fondamental de fonction f, qui intervient à la fois en optimisation et en contrôle distribué, est celui de la moyenne des valeurs initiales.

L'objectif de ce cours est d'étudier précisément la résolubilité et la complexité de ces différents problèmes de consensus suivant le modèle de communication, le modèle d'agents (eg., agents anonymes ou avec identifiants) ou encore selon les connaissances dont les agents disposent (eg., la taille du réseau). En particulier, on déterminera les classes de fonctions calculables dans ces différents types de réseaux multi-agents grâce à la notion de fibration de graphe (théorie de l'homotopie) développée par Boldi et Vigna dans les années 2000.

Modèle de calcul et spécifications

• Modèle de calcul et rounds synchrones
• Modèles de communication
• Spécifications du consensus : consensus irrévocable, consensus stabilisant et consensus asymptotique. Spécifications contraintes.

Consensus irrévocable

• Résultat d'impossibilité de Santoro et Widmayer
• Algorithmes de consensus irrévocable

Consensus stabilisant

• Algorithme MinMax
• Résultats d'impossibilité de Boldi et Vigna pour le consensus f-contraint : théorie de l'homotopie et fibrations de graphes
• Consensus f-contraint pour un graphe statique : base minimale et algorithme universel de Boldi et Vigna

Consensus asymptotique

• Algorithmes de moyennes pondérées et matrices stochastiques ; théorèmes de convergence de Cao, Morse et Anderson et de Moreau
• Consensus f-contraint pour un graphe dynamique : algorithme de Metropolis pour les graphes bidirectionnels et algorithme universel PushSum

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

}

Notes de cours :

1. Computing model : 2-33-1-nc-model.pdf
2. Irrevocable consensus : 2-33-1-nc-irrevcons.pdf
3. Graph fibrations : 2-33-1-nc-fibration.pdf
4. The Perron-Frobenius theorem : 2-33-1-nc-perronfrobenius.pdf
5. Asymptotic consensus : 2-33-1-nc-asymptcons.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. Computing model : 2-33-1-exosmodel.pdf
2. Irrevocable consensus : 2-33-1-exosirrevocablecons.pdf
3. Stochastic matrices : 2-33-1-nc-perronfrobenius.pdf
4. Asymptotic consensus : 2-33-1-exos-averaging.pdf

Examen :

exam22.pdf

• I have just posted a list of exercises on averaging algorithms and asymptotic consensus.
• The next course on Thursday November 10th is cancelled.
• You can read the course notes on asymptotic consensus, and study the last section (Section 5, Theorems 9 and 12) in advance.

• Dimitri P. Bertsekas and John N. Tsitsiklis. Parallel and Distributed Computation: Numerical Methods. Prentice-Hall, 1997.
• Paolo Boldi and Sebastiano Vigna. Computing Vector Functions on Anonymous Networks. SIROCCO 1997: 201-214.
• Paolo Boldi and Sebastiano Vigna. Fibrations of graphs. Discret. Math, vol. 243(1-3): 21-66, February 2002.
• Paolo Boldi and Sebastiano Vigna. Universal dynamic synchronous self-stabilization. Distributed Comput., vol. 15(3): 137-153, March 2002.
• 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