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.

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

Domaine :

Informatique [cs] / Réseaux et télécommunications [cs.NI]

Informatique [cs] / Algorithme et structure de données [cs.DS]

Informatique [cs] / Complexité [cs.CC]

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 31 août 2018 - 09:25:54
Document(s) archivé(s) le : samedi 26 novembre 2016 - 08:51:17

unidir_algotel.pdf

Fichiers produits par l'(les) auteur(s)

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

Fichier

Identifiants

Collections

Citation

Exporter

Métriques

825

217

Contact

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

Fichier

Identifiants

Collections

Citation

Exporter

Partager

Métriques

825

217

Contact