Table of Contents

2.33.1 Calculabilité dans les réseaux multiagents (24h, 3ECTS)

Équipe pédagogique :

É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

Consensus irrévocable

Consensus stabilisant

Consensus asymptotique

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 :

  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 :

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

Messages :

Bibliographie

Cours reliés