Techniques de tolérance aux pannes distribuée pour les calculs locaux

Abstract

Ce travail constitue une contribution théorique et pratique à l’étude de la tolérance aux pannes dans les systèmes distribués, et de spécifier l’impacte de la théorie des graphes dans ce domaine. Précisément, on s’intéresse aux pannes de processus et nous considérons les pannes transitoires et les pannes franches. Notre but est d’étudier ces systèmes dans le contexte de la localité : Les seuls calculs autorisés sont ceux à base d’informations locales. Ceci revient à capturer la notion de détection et de correction des configurations "illégales" qui résultent de l’état arbitraire du système. Comme modèle, on utilisera les calculs locaux et à passage de messages. Nos constructions sont basées sur les techniques les plus répondues dans ce domaine : La détection de pannes et l’auto-stabilisation. En combinant ces deux techniques et en gardant la localité comme but ultime, nous construisons un nouvel outil pour transformer un algorithme intolérant en un autre algorithme équivalent mais qui est tolérant aux pannes, dont la preuve de correction est déduite du premier. D’une autre part, nous avons augmenté la plate-forme Visidia pour simuler les pannes. Les pannes transitoires sont simplement simulées à travers des vues permettant de changer l’état des noeuds. Pour les pannes franches, en premier le détecteur de pannes est intégré dans Visidia, en plus d’une interface pour mesurer ses performances pour atteindre les comportements attendus. En second, à travers des vues, l’utilisateur peut stopper le travail d’un noeud et simuler la panne d’un processus. Pour terminer cette thèse, nous sollicitons la théorie de graphe pour aider la tolérance aux pannes selon deux aspects. Nous présentons une nouvelle formalisation du test de la connexité de graphes en utilisant la notion de fils de secours. Un algorithme distribué et local pour tester la 2-connexité est proposé dans les deux modèles. Ce résultat nous illumine à propos de la manière dont un pont peut être construit entre ces deux modèles. En second, le calcul des fils de secours est entendu pour étudier la maintenance de forêts d’arbres recouvrants en présence de pannes franches.