Construction auto-stabilisante d'arbre couvrant en dépit d'actions malicieuses

Résumé : Un protocole auto-stabilisant est par nature tol´erant aux fautes transitoires (i.e. de dur´ee finie). Ces dernières années ont vu apparaitre une nouvelle classe de protocoles qui, en plus d'etre 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 montrons que, pour certains problèmes n'admettant pas de solution strictement stabilisante ([NA02]), il existe toutefois des solutions tolérant des fautes byzantines si nous définissons un critère de tolérance moins contraignant. A self-stabilizing protocol provides by definition a tolerance to transient failures. Recently, a new class of self-stabilizing protocols appears. These protocols provides also a tolerance to a given number of permanent failures. In this article, we are interested in self-stabilizing protocols that deal with Byzantines failures. We prove that, for some problems which not allow strict stabilization (see [Nesterenko,Arora,2002]), there exist solutions that tolerates Byzantine faults if we define a new criteria of tolerance.
Type de document :
Communication dans un congrès
Maria Gradinariu Potop-Butucaru and Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), May 2010, Belle Dune, France. 2010
Liste complète des métadonnées

Littérature citée [4 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00477480
Contributeur : Swan Dubois <>
Soumis le : jeudi 29 avril 2010 - 11:49:50
Dernière modification le : jeudi 11 janvier 2018 - 06:26:28
Document(s) archivé(s) le : mardi 28 septembre 2010 - 13:11:25

Fichiers

DuboisMasuzawaTixeuil.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00477480, version 1
  • ARXIV : 1004.5256

Collections

Citation

Swan Dubois, Toshimitsu Masuzawa, Sébastien Tixeuil. Construction auto-stabilisante d'arbre couvrant en dépit d'actions malicieuses. Maria Gradinariu Potop-Butucaru and Hervé Rivano. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), May 2010, Belle Dune, France. 2010. 〈inria-00477480〉

Partager

Métriques

Consultations de la notice

227

Téléchargements de fichiers

114