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
4 DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS
Inria Rennes – Bretagne Atlantique , IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES
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
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LIFL - Laboratoire d'Informatique Fondamentale de Lille, LRI - Laboratoire de Recherche en Informatique
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.
Document type :
Conference papers
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

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/inria-00384649
Contributor : Samuel Bernard <>
Submitted on : Friday, May 15, 2009 - 5:56:35 PM
Last modification on : Friday, August 31, 2018 - 9:25:54 AM
Document(s) archivé(s) le : Saturday, November 26, 2016 - 8:51:17 AM

File

unidir_algotel.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00384649, version 2

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〉

Share

Metrics

Record views

828

Files downloads

217