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. ObjectifsLe 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 coursModèle de calcul et spécifications
Consensus irrévocable
Consensus stabilisant
Consensus asymptotique
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 :
Examen : Messages :
Bibliographie
Cours reliés |