Description
Date depot: 28 mars 2025
Titre: Self-Stabilizing Propagation of Information in Highly Dynamic Distributed Systems
Directeur de thèse:
Franck PETIT (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Systèmes et réseaux
Resumé: L'informatique distribuée évolue de plus en plus vers des systèmes où ses éléments (utilisateurs, liaisons, équipements, etc.) peuvent rejoindre, quitter ou se déplacer à l'intérieur du réseau à tout moment et de manières imprévisibles. La forte dynamique de ces réseaux rend extrêmement difficile la conception d'une infrastructure de communication fiable et solide.
L'auto-stabilisation est une approche reconnue de la tolérance aux pannes dans l'informatique distribuée. Elle consiste à concevoir des algorithmes distribués tolérant des fautes transitoires, c'est-à-dire des fautes qui sont assez rares, d'une durée finie, quelles que soient leur nature et leur origine.
Le sujet de la thèse vise à étudier le problème de la diffusion d’information avec retour (PIR) de manière auto-stabilisante dans les systèmes hautement dynamiques. En premier lieu, nous envisageons d'établir les conditions sous lesquelles le problème puisse être résolu ou non. Plus précisément, nous aimerions obtenir des algorithmes de PIR auto-stabilisants pour des classes données de systèmes dynamiques et si possible, montrer sous quelles conditions le problème peut ou ne peut pas être réalisé. En fonction des résultats obtenus, nous aimerions considérer deux variantes de l'auto-stabilisation : celle qui consiste à affaiblir (ou généraliser) les contraintes imposées par l'auto-stabilisation afin de réduire les impossibilités et celle qui les renforce (ou les spécialise) pour des environnements dynamiques plus spécifiques.
Résumé dans une autre langue: Distributed computing is increasingly moving towards systems where its components (users, links, equipment, etc.) can join, leave, or move inside the network at unforeseeable times. The dynamic nature of these networks makes extremely difficult to design a solid, reliable communications infrastructure.
Self-stabilization is a recognized approach to fault tolerance in distributed computing. It consists in designing distributed algorithms that tolerate transient faults, i.e., faults that are quite rare, of finite duration, whatever their nature and origin.
The aim of this thesis is to study the problem of self-stabilizing Propagation of Information with Feeback (PIF for short) in highly dynamic systems. First, we plan to establish the conditions under which the problem can be solved or not. More specifically, we would like to obtain self-stabilizing PIF algorithms for given classes of dynamic systems and, if possible, show under which conditions the problem can be solve or not. Depending on the results obtained, we would like to consider two variants of self-stabilization: the latter weakens (or, generalizes) the constraints imposed by self-stabilization in order to reduce impossibilities, the latter strengthens (or, specializes) them to git specific dynamic environments.