HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/inria-00384649
Contributor : Samuel Bernard Connect in order to contact the contributor
Submitted on : Friday, May 15, 2009 - 5:56:35 PM
Last modification on : Thursday, February 3, 2022 - 10:04:04 AM
Long-term archiving on: : 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. 11èmes Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel 2009), Jun 2009, Carry-Le-Rouet, France. ⟨inria-00384649v2⟩

Share

Metrics

Record views

627

Files downloads

181