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

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

Samuel Bernard ¹ Stéphane Devismes ² 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

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

Domain :

Computer Science [cs] / Networking and Internet Architecture [cs.NI]

Computer Science [cs] / Data Structures and Algorithms [cs.DS]

Computer Science [cs] / Computational Complexity [cs.CC]

Complete list of metadatas

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 : Thursday, March 21, 2019 - 1:07:52 PM
Long-term archiving on : Saturday, November 26, 2016 - 8:51:17 AM

unidir_algotel.pdf

Files produced by the author(s)

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

File

Identifiers

Collections

Citation

Export

Metrics

973

286

Contact

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

File

Identifiers

Collections

Citation

Export

Share

Metrics

973

286

Contact