Sidebar
Table of Contents
2.33.1 Calculabilité dans les réseaux multiagents (24h, 3ECTS)
É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)
Édition 2022-2023 :
LE COURS DU JEUDI 6 OCTOBRE EST ANNULE.
Langue : français ou en anglais selon la demande ; documentation en anglais.
Objectifs
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.
Plan du cours
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
Pré-requis
Notions de base en algèbre linéaire, théorie des graphes et en algorithmique distribuée.
}
Notes de cours et exercices
Notes de cours :
- Computing model : 2-33-1-nc-model.pdf
- Irrevocable consensus : 2-33-1-nc-irrevcons.pdf
- Graph fibrations : 2-33-1-nc-fibration.pdf
- The Perron-Frobenius theorem : 2-33-1-nc-perronfrobenius.pdf
- Asymptotic consensus : 2-33-1-nc-asymptcons.pdf
Articles :
- Bernard Chazelle, Natural Algorithms and Influence Systems, CACM, vol. 55(12).
Feuilles d'exercices et devoir :
- Computing model : 2-33-1-exosmodel.pdf
- Irrevocable consensus : 2-33-1-exosirrevocablecons.pdf
- Stochastic matrices : 2-33-1-nc-perronfrobenius.pdf
- Asymptotic consensus : 2-33-1-exos-averaging.pdf
Examen :
Messages :
- 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.
Bibliographie
- 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.