Au sein du LaBRI, mes activités de recherche portent sur des thèmes des équipes ``Combinatoire et Algorithmique'' et ``Méthodes Formelles''. Ce qui constitue pour moi une mobilité thématique. Mes travaux ont pour objectif la conception et la mise en oeuvre d'un environnement unifié permettant de simuler, visualiser et prouver formellement des algorithmes et transformations d'algorithmes distribués.

De nos jours, avec l'expansion des objets communicants, les systèmes distribués trouvent toute leur place dans notre quotidien. Ils sont présents dans les systèmes embarqués (automobile intelligente, aéronautique), les réseaux de capteurs (médecine, domotique) ou encore les bases de données réparties. Cette omniprésence de ces systèmes accroît l'intérêt des algorithmes distribués dans la conception d'applications. Un système distribué est un ensemble d'entités autonomes qui coopèrent dans le but de résoudre un problème donné. Généralement, ce système est modélisé par un graphe dans lequel les noeuds et les arêtes représentent, respectivement, les unités de traitement et les canaux de communication.

Les travaux que je réalise dans le cadre de ce projet portent sur la détection de la terminaison globale d'un algorithme et le calcul de l'état global d'un système distribué.


Détection de la terminaison globale d'un algorithme

Un système distribué permettant de résoudre un problème grâce à la coopération de plusieurs entités (noeuds), il est important de pouvoir connaître le moment où une solution au problème est trouvée. Il s'agit de la terminaison de l'algorithme. Lorsqu'un noeud arrive à son état final, on dit que l'exécution de l'algorithme est localement terminée ; un algorithme a terminé lorsque tous les noeuds du réseau ont atteint leur état final et qu'il n'y a plus de message en transit. Je me suis intéressé aux solutions permettant de détecter de manière distribuée que tous les calculs sont terminés dans un graphe anonyme (les identifiants des sommets ne sont pas tous distincts). Pour ce type de graphe, j'ai utilisé l'algorithme de Szymanski, Shy et Prywes (SSP) pour observer le déroulement de l'algorithme ``principal''. La réflexion sur la détection de la terminaison a été prolongée dans le but de permettre à chaque noeud de savoir que tous les noeuds du réseau ont détecté la terminaison globale. En outre, l'algorithme de SSP a l'avantage de s'appliquer sur toute topologie de graphe.


Calcul de l'état global d'un système distribué

La robustesse et la stabilité sont des propriétés généralement recherchées dans les systèmes distribués. Cependant, les matériels tout comme les logiciels qui composent ces systèmes ne sont pas infaillibles. À défaut de garantir cette infaillibilité, le calcul de l'état global d'un système distribué peut permettre d'analyser les propriétés de l'exécution d'un algorithme. Cette tâche revient à calculer et à coordonner le calcul des états locaux de chaque noeud du réseau. En d'autres termes, calculer une image (snapshot) du réseau.

Le calcul du snapshot a plusieurs applications parmi lesquelles le calcul des points de reprise (après une panne), la détection de l'interblocage, le débogage des algorithmes, etc. Je me suis intéressé au calcul du snapshot (en utilisant l'algorithme de Chandy-Lamport) dans un système anonyme avec, potentiellement, plusieurs noeuds initiateurs.



Pour valider ces travaux, j'ai mis en oeuvre ces différents algorithmes dans ViSiDiA qui est une plate-forme de simulation et de visualisation d'algorithmes distribués développée au LaBRI.