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
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.
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 : Wednesday, August 2, 2017 - 10:07:07 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

615

Document downloads

202