Sur le Coloriage Auto-stabilisant dans les Réseaux Unidirectionnels Anonymes

Samuel Bernard 1 Stéphane Devismes 2 Katy Paroux 3, 4 Maria Gradinariu Potop-Butucaru 5, 6 Sébastien Tixeuil 7, 1
1 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
2 VERIMAG - IMAG - VERIMAG
3 LMB - Laboratoire de Mathématiques de Besançon (UMR 6623)
4 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
Inria Rennes – Bretagne Atlantique , IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
5 LIP6 - Laboratoire d'Informatique de Paris 6
6 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
7 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Résumé : Nous considérons des réseaux unidirectionnels anonymes. Nous démontrons que contrairement aux réseaux bidirectionnels, l'auto-stabilisation de tâches locales peut y être aussi difficile que l'auto-stabilisation de tâches globales. Pour ce faire, nous prenons comme exemple le problème du coloriage des nœuds d'un réseau. Plus précisément, nous démontrons que le coloriage auto-stabilisant est intrinsèquement aussi difficile à résoudre de manière déterministe qu'une tâche globale. Nous proposons ensuite une approche probabiliste pour retrouver une complexité locale.
Type de document :
Communication dans un congrès
Chaintreau, Augustin and Magnien, Clemence. 11èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2009), Jun 2009, Carry-Le-Rouet, France. 2009
Liste complète des métadonnées

Littérature citée [3 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00384649
Contributeur : Samuel Bernard <>
Soumis le : vendredi 15 mai 2009 - 17:56:35
Dernière modification le : vendredi 6 juillet 2018 - 15:18:04
Document(s) archivé(s) le : samedi 26 novembre 2016 - 08:51:17

Fichier

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

Identifiants

  • HAL Id : inria-00384649, version 2

Collections

IMAG | INRIA | UNIV-FCOMTE | IRISA | ALGOTEL2009 | UMR6623 | LIP6 | UPMC | UMR8623 | UGA | IRISA-D2 | UNIV-LILLE3 | UR1-UFR-ISTIC | UNIV-RENNES | VERIMAG

Citation

Samuel Bernard, Stéphane Devismes, Katy Paroux, Maria Gradinariu Potop-Butucaru, Sébastien Tixeuil. Sur le Coloriage Auto-stabilisant dans les Réseaux Unidirectionnels Anonymes. Chaintreau, Augustin and Magnien, Clemence. 11èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2009), Jun 2009, Carry-Le-Rouet, France. 2009. 〈inria-00384649v2〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

766

Téléchargements de fichiers

214

Contact


archive-ouverte@inria.fr