Présentation du thème Algorithmique Distribuée de l'équipe Combinatoire et Algorithmique

Le développement des réseaux et l'utilisation de plus en plus massive de terminaux peu fiables avec de faibles connectivités nécessitent des recherches sur la conception d'Algorithmes Distribués fiables, passant à l'échelle et dont le comportement puisse être prouvé formellement.

• Etude de la fiabilité et de la caractérisation des algorithmes distribués : l'objectif est de prouver à l'aide d'assistant de preuve (tel Coq) que la spécification formelle des algorithmes est valide. Le modèle théorique sous-jacent est celui des calculs locaux développé au LaBRI depuis plusieurs années.
• Algorithmique tolérant les perturbations : un système distribué est sujet à de fréquentes perturbations dues aux pannes franches ou transitoires, à la versatilité et la mobilité des entités. Nous nous intéressons à la conception d'algorithmes efficaces et tolérants les perturbations en utilisant diverses techniques (wait-freedom, obstruction-freedom, self-stabilization, failure detector ... ).
• Modélisation des réseaux distribués à grande échelle et de leur dynamisme : on a observé depuis quelques années que les réseaux (physiques et virtuels) réels présentent des propriétés topologiques qualitatives (petit monde, ...) très importantes pour la conception des algorithmes. En revanche, on manque de modèles pertinents (c'est à dire dont à la fois les paramètres peuvent être instanciés facilement, ce qui conduit à des algorithmes polynomiaux pour les problèmes classiques et qui modélisent bien le réseau). Cette remarque est plus particulièrement valide dans le cas de la modélisation du dynamisme des ressources.
• Données massives distribuées : ce thème porte sur la conception de réseaux virtuels pair à pair et d'algorithmes de routage, l'exécution de requêtes (exploration perpétuelle, cartographie, rendez-vous, ...) par agents mobiles, la diffusion et le calcul distribué sur de grands réseaux dynamiques. Les solutions envisagées doivent être légères en mémoire, rapides et garantir des performances - d'un point de vue théorique - de niveau comparable au cadre centralisé.
• Calculs locaux : l'objectif est de fournir des outils permettant de coder, d'étudier et d'enseigner différents aspects de l'algorithmique distribuée. On s'intéresse plus particulièrement à certains problèmes comme : l'élection, le nommage, le calcul d'un arbre recouvrant, la détection de la terminaison, la synchronisation, le consensus ou bien la reconnaissance de certaines propriétés du réseau. Ces études sont faites d'une part en fonction des règles de calcul autorisées sur le réseau et d'autre part de la connaissance initiale ou de la configuration initiale du réseau.
• Algorithmes distribués probabilistes : la non existence d'algorithmes distribués déterministes pour résoudre certains problèmes nous conduit à proposer et à étudier des algorithmes distribués probabilistes dont l'expression est souvent simple mais l'analyse difficile. On recherche en particulier des solutions optimales du point de vue de la complexité en bits : nombre de bits échangés entre 2 sommets quelconques.