Le domaine "Algorithmique et Complexité" (ALCO) vise à étudier et résoudre efficacement, via une approche algorithmique, des problèmes fondamentaux des systèmes distribués (e.g., élection de leader, construction d'arbres couvrants, diffusion d'informations, routage, exploration, rassemblement d'entités mobiles, etc.), que ces systèmes soient statiques ou dynamiques (comme Internet, réseaux Ad Hoc, IoT, etc.).
ALCO s'articule autour de deux thématiques principales :
- l'Algorithmique Mobile et
- la Tolérance aux fautes.
L'objectif général est d'approfondir la compréhension des systèmes distribués en développant des solutions algorithmiques innovantes et efficaces, mais également en identifiant les limites de faisabilité. Les recherches portent notamment sur l'impact de la qualité des communications, la conception d'algorithmes tolérants aux fautes et économes en énergie, ainsi que la gestion des temps de réponse dans des environnements dynamiques.
Le thème "algorithmique mobile" s'intéresse à l'élaboration et à l'analyse d'algorithmes exécutés par des entités autonomes capables de se déplacer dans un environnement, souvent modélisé sous la forme d'un graphe ou d'un plan. Ces entités, également appelées agents mobiles ou robots, interagissent localement avec leur environnement et éventuellement entre elles, dans le but de résoudre collectivement des tâches globales. Nos recherches menées dans ce domaine s'attachent en particulier à comprendre les capacités computationnelles de ces systèmes (i.e., déterminer ce qui faisable ou infaisable d'un point de vue fondamental), ainsi qu'à concevoir des solutions correctes, efficaces et robustes malgré des contraintes fortes (e.g., une autonomie limitée en énergie, l'absence de communication, présence de comportements byzantins,etc.). Nous concentrons nos travaux sur des tâches de base telles que la formation de motifs, l'élection d'un leader, le rassemblement, la dispersion, etc. Basiques en apparence, ces tâches s'avèrent être en réalité des briques de base ainsi que des prérequis incontournables afin de réaliser des missions plus complexes. Ainsi, loin d'être une perte de généralité, cette attention particulière sur problèmes élémentaires, mais néanmoins fondamentaux, contribue à une meilleure compréhension de ce qui peut être réalisé ou non par une cohorte d'agent mobiles.
Le thème "Tolérance aux fautes" est principalement centré sur l'autostabilisation. L'autostabilisation est une propriété générale permettant aux algorithmes la réalisant de tolérer les fautes transitoires. En effet, un algorithme autostabilisant retrouve de lui-même (c'est-à-dire, sans intervention extérieure) un comportement correct en temps fini après de telles fautes. Cette propriété se déclinent en de nombreuses variantes, soit plus faible, soit plus forte. Nous nous intéressons plus particulière à la notion de stabilisation instantanée introduite en 1997 par des membres du MIS (Vincent Villain et Franck Petit notamment). L'essentiel du travail sur ce thème est de définir des propriétés de tolérances aux pannes
pertinentes, souvent dérivées de l'autostabilisation, et à concevoir des algorithmes ayant ces propriétés. Ces algorithmes doivent être démontrés corrects et efficaces dans des modèles les plus proches possibles du réel. L'efficacité est à la fois démontrée par des bornes analytiques (pour déterminer la complexité dans le pire des cas) et évaluée empiriquement par simulation (pour estimer le cas moyen). Un dernier aspect important est l'élaboration de conditions nécessaires et
de bornes inférieures de complexité.
