Show simple item record

dc.contributor.authorHAMID, Brahim
dc.date2007-06-14
dc.date.accessioned2021-01-13T14:02:50Z
dc.date.available2021-01-13T14:02:50Z
dc.identifier.urihttps://oskar-bordeaux.fr/handle/20.500.12278/25092
dc.description.abstractCe 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.
dc.description.abstractEnThis thesis describes theoretical and practical contributions to study fault-tolerance in distributed computing systems, and to investigate the impact of graph structures to deal with fault-tolerance. Specifically, we deal with process failures and we consider transient (or temporary) and crash (or permanent) failures. Our purpose is to study such systems in the context of locality in the sense that the only permitted actions are those using local information. That is, we deal with local detection and correction of the not "legal" (or abnormal) configurations resulting from the arbitrary state. We use both local computations and message passing models. We build on two main techniques in fault-tolerance research : Failure detection and self-stabilization. By combining these techniques and having failure locality purpose in mind, we construct a novel framework to transform an intolerant algorithm to a fault-tolerant one taking benefit of the proofs of the the first one. On the other hand, we augment the Visidia software to simulate failures and then fault-tolerance. The transient failures are simulated simply through views allowing to change the states of the nodes. To deal with crash failures, first we integrate the failure detector module to Visidia with an interface to measure its performances in order to reach expected behaviors. Second, through views, the user may stop the work of some node to simulate the crash. At the end, we use graph theory to help fault-tolerance following two aspects. We present a new formalization of the vertex connectivity using the notion of succorer sons. Then we propose a local distributed algorithm to test the 2-connectivity of graphs using a constructive approach in the two used models. These results illuminate how to build a bridge between these models. Second, extending the notion of succorer sons, we studied the maintenance of a forest of spanning trees in spite of crash failures.
dc.formatapplication/pdf
dc.languagefr
dc.rightsfree
dc.subjectInformatique
dc.subjectSystèmes distribués
dc.subjectdétecteur de pannes
dc.subjecttolérance aux pannes
dc.subjectsystème de réécriture de graphes
dc.subjectlocalité
dc.subjectmaintenance
dc.subjectsystème à passage de messages
dc.subjectréseaux
dc.subjectauto-stabilisation
dc.subjectconnexité
dc.titleTechniques de tolérance aux pannes distribuée pour les calculs locaux
dc.typeThèses de doctorat
bordeaux.hal.laboratoriesThèses Bordeaux 1 Ori-Oai*
bordeaux.institutionUniversité de Bordeaux
bordeaux.COinSctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.title=Techniques%20de%20tol%C3%A9rance%20aux%20pannes%20distribu%C3%A9e%20pour%20les%20calculs%20locaux&rft.atitle=Techniques%20de%20tol%C3%A9rance%20aux%20pannes%20distribu%C3%A9e%20pour%20les%20calculs%20locaux&rft.au=HAMID,%20Brahim&rft.genre=unknown


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record