Auto-Stabilisation et Confinement de Fautes Malicieuses : Optimalité du Protocole min+1 - Archive ouverte HAL Access content directly
Conference Papers Year : 2011

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

(1) , (2) , (3)
1
2
3

Abstract

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
Origin : Files produced by the author(s)
Loading...

Dates and versions

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

Identifiers

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

Cite

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⟩
104 View
96 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More