Auto-Stabilisation et Confinement de Fautes Malicieuses : Optimalité du Protocole min+1 - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2011

Auto-Stabilisation et Confinement de Fautes Malicieuses : Optimalité du Protocole min+1

Résumé

A self-stabilizing is naturally resilient to transients faults (that is, faults of finite duration). Recently, a new class of protocol appears. These protocols are self-stabilizing and are moreover resilient to a limited number of permanent faults. In this article, we interest in self-stabilizing protocols that tolerate very hard permanent faults: Byzantine faults. We introduce two new scheme of Byzantine containment in self-stabilizing systems. We show that, for the problem of BFS spanning tree construction, the well known self-stabilizing protocol min+1 provides without significant modification the best Byzantine containment with respect to these new schemes.
Un protocole auto-stabilisant est par nature tolérant aux fautes transitoires (i.e. de durée finie). Ces dernières années ont vu apparaître une nouvelle classe de protocoles qui, en plus d'être auto-stabilisants, tolèrent un nombre limité de fautes permanentes. Dans cet article, nous nous intéressons aux protocoles auto-stabilisants tolérant des fautes permanentes très sévères : les fautes Byzantines. Nous introduisons deux nouveaux concepts de confinement de fautes Byzantines dans les systèmes auto-stabilisants. Nous montrons que, pour le problème de la construction d'arbre couvrant en largeur, le protocole auto-stabilisant connu sous le nom de min+1 offre sans aucune modification fondamentale le meilleur confinement de fautes Byzantines possible au sens de ces nouveaux concepts.
Fichier principal
Vignette du fichier
Algotel11.pdf (55.58 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00587517 , version 1 (20-04-2011)

Identifiants

  • HAL Id : inria-00587517 , version 1
  • ARXIV : 1104.4022

Citer

Swan Dubois, Toshimitsu Masuzawa, Sébastien Tixeuil. Auto-Stabilisation et Confinement de Fautes Malicieuses : Optimalité du Protocole min+1. 13es Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), May 2011, Cap Estérel, France. ⟨inria-00587517⟩
112 Consultations
101 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More