|
Problèmes de Consensus : du calcul distribué à la théorie du contrôle| old_uid | 19683 |
|---|
| title | Problèmes de Consensus : du calcul distribué à la théorie du contrôle |
|---|
| start_date | 2021/11/10 |
|---|
| schedule | 17h |
|---|
| online | no |
|---|
| location_info | salle Henri Cartan |
|---|
| summary | Les problèmes de consensus apparaissent dans un grand nombre de systèmes multi-agents, qu'ils soient naturels ou artificiels : les agents doivent, par exemple, se coordonner afin de se synchroniser ou encore adopter un même état mémoire.
Dans tout problème de consensus, les agents possèdent chacun une variable de sortie et doivent finir par s'accorder sur une valeur commune pour toutes ces variables. Au delà de cette clause commune d'accord, les problèmes de consensus diffèrent essentiellement de par la propriété de stabilité exigée pour les variables de sortie. Ainsi peut-on demander à chaque agent de prendre une décision irrévocable (ce qui correspond au cas où les variables de sortie sont à écriture unique). On peut affaiblir cette condition en autorisant les agents à modifier leur décision un nombre fini de fois. Ou encore leur permettre de changer d'avis infiniment souvent, auquel cas les variables de sortie doivent simplement converger vers une valeur de sortie limite commune. On parle ainsi de consensus irrévocable, de consensus stabilisant ou de consensus asymptotique.
J'examinerai sous quelle forme ces différents problèmes de consensus apparaissent selon le type d'applications considérées : alors que le consensus irrévocable est requis dans les techniques de réplication pour la tolérance aux fautes, seul un consensus asymptotique est nécessaire pour nombre de problèmes en contrôle distribué, en optimisation distribuée ou encore pour la modélisation de phénomènes naturels de synchronisation (e.g., nuées d'oiseaux, scintillement de lucioles). Quant au consensus de Nakamoto au cœur de la technologie blockchain, sa clause de stabilité se situe entre celle du consensus irrévocable et celle du consensus stabilisant dans la hiérarchie décrite plus haut.
Dans une seconde partie, je présenterai les résultats majeurs de calculabilité et de complexité pour ces différents problèmes de consensus : le théorème d'impossibilité de Fischer, Lynch et Paterson (FLP) pour les systèmes asynchrones, le théorème dit des ``généraux byzantins'' de Shostak, Pease et Lamport et le résultat spectaculaire de Moreau, prouvant la supériorité des interactions symétriques. J'esquisserai les techniques très variées mises en œuvre pour établir ces différents résultats et expliquerai comment mon travail se situe et s'articule autour de ces résultats centraux. |
|---|
| responsibles | <not specified> |
|---|
| |
|