| HAL-Inria | Publications, software ... of Inria's scientists |
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
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
Samuel Bernard 1
Author
Stéphane Devismes 2
Author IdHAL : stephane-devismes ORCID : https://orcid.org/0000-0002-8032-9732
Katy Paroux 3, 4
Author
Maria Gradinariu Potop-Butucaru 5, 6
Author
Sébastien Tixeuil 7, 1
Author IdHAL : tixeuil ORCID : https://orcid.org/0000-0002-0948-7172
1
NPA - Networks and Performance Analysis (France)
- LIP6 - Laboratoire d'Informatique de Paris 6 (4 Place JUSSIEU 75252 PARIS CEDEX 05 - France)
- UPMC - Université Pierre et Marie Curie - Paris 6 (4 place Jussieu - 75005 Paris - France)
- CNRS - Centre National de la Recherche Scientifique : UMR7606 (France)
2
VERIMAG - IMAG - VERIMAG (Verimag
Bâtiment IMAG
Université Grenoble Alpes
700, avenue centrale
38401 Saint Martin d’Hères
France - France)
- UJF - Université Joseph Fourier - Grenoble 1 (BP 53 - 38041 Grenoble Cedex 9 - France)
- Grenoble INP - Institut polytechnique de Grenoble - Grenoble Institute of Technology (46 avenue Félix Viallet 38031 Grenoble Cedex 1 - France)
- INPG - Institut National Polytechnique de Grenoble (46 avenue Félix Viallet 38031 Grenoble Cedex 1 - France)
- CNRS - Centre National de la Recherche Scientifique : UMR5104 (France)
3
LMB - Laboratoire de Mathématiques de Besançon (UMR 6623) (UFR Sciences et techniques 16 route de Gray 25 030 Besançon cedex - France)
- UB - Université de Bourgogne (Maison de l'université - Esplanade Érasme - BP 27877 - 21078 Dijon cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR6623 (France)
- UFC - Université de Franche-Comté (1 rue Goudimel 25030 Besançon cedex - France)
4
DIONYSOS - Dependability Interoperability and perfOrmance aNalYsiS Of networkS (Campus de Beaulieu 35042 Rennes cedex - France)
- Inria Rennes – Bretagne Atlantique (Campus de beaulieu
35042 Rennes cedex - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
- IRISA-D2 - RÉSEAUX, TÉLÉCOMMUNICATION ET SERVICES (France)
- IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires (Avenue du général Leclerc
Campus de Beaulieu
35042 RENNES CEDEX - France)
- INSA Rennes - Institut National des Sciences Appliquées - Rennes (20, avenue des Buttes de Coësmes - CS 70839 - 35708 Rennes cedex 7 - France)
- UBS - Université de Bretagne Sud (BP 92116 - 56321 Lorient cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR6074 (France)
- ENS Rennes - École normale supérieure - Rennes (Campus de Ker Lann - avenue Robert Schuman - 35170 Bruz - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
- Télécom Bretagne (Technopôle Brest-Iroise CS 83818 29238 BREST Cedex 3 - France)
- UR1 - Université de Rennes 1 (2 rue du Thabor - CS 46510 - 35065 Rennes cedex - France)
- UNIV-RENNES - Université de Rennes (France)
- CentraleSupélec (3, rue Joliot Curie, Plateau de Moulon, 91192 GIF-SUR-YVETTE Cedex - France)
- IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires (Avenue du général Leclerc
Campus de Beaulieu
35042 RENNES CEDEX - France)
5
LIP6 - Laboratoire d'Informatique de Paris 6 (4 Place JUSSIEU 75252 PARIS CEDEX 05 - France)
- UPMC - Université Pierre et Marie Curie - Paris 6 (4 place Jussieu - 75005 Paris - France)
- CNRS - Centre National de la Recherche Scientifique : UMR7606 (France)
6
Regal - Large-Scale Distributed Systems and Applications (France)
- LIP6 - Laboratoire d'Informatique de Paris 6 (4 Place JUSSIEU 75252 PARIS CEDEX 05 - France)
- UPMC - Université Pierre et Marie Curie - Paris 6 (4 place Jussieu - 75005 Paris - France)
- CNRS - Centre National de la Recherche Scientifique : UMR7606 (France)
- Inria Paris-Rocquencourt (INRIA Rocquencourt : Domaine de Voluceau, Rocquencourt B.P. 105 78153 le Chesnay Cedex - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
7
GRAND-LARGE - Global parallel and distributed computing (PCRI - Université de Paris-Sud, Bâtiment 650, 91405 ORSAY Cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR8623 (France)
- Inria Saclay - Ile de France (1 rue Honoré d'Estienne d'Orves
Bâtiment Alan Turing
Campus de l'École Polytechnique
91120 Palaiseau - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
- UP11 - Université Paris-Sud - Paris 11 (Bâtiment 300 - 91405 Orsay cedex - France)
- LIFL - Laboratoire d'Informatique Fondamentale de Lille (Bâtiment M3 59655 Villeneuve d'Ascq Cédex - France)
- Université de Lille, Sciences et Technologies (Cité Scientifique - 59655 Villeneuve d'Ascq Cedex - France)
- Inria - Institut National de Recherche en Informatique et en Automatique (Domaine de Voluceau Rocquencourt - BP 105 78153 Le Chesnay Cedex - France)
- Université de Lille, Sciences Humaines et Sociales (Domaine universitaire du "Pont de Bois" Rue du Barreau BP 60149 59653 Villeneuve d'Ascq Cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR8022 (France)
- LRI - Laboratoire de Recherche en Informatique (LRI - Bâtiments 650-660 Université Paris-Sud 91405 Orsay Cedex - France)
- UP11 - Université Paris-Sud - Paris 11 (Bâtiment 300 - 91405 Orsay cedex - France)
- CentraleSupélec (3, rue Joliot Curie, Plateau de Moulon, 91192 GIF-SUR-YVETTE Cedex - France)
- CNRS - Centre National de la Recherche Scientifique : UMR8623 (France)
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
Complete list of metadata
https://hal.inria.fr/inria-00384649
Contributor : Samuel Bernard <>
Submitted on : Friday, May 15, 2009 - 5:56:35 PM
Last modification on : Thursday, January 28, 2021 - 10:26:02 AM
Long-term archiving on: : Saturday, November 26, 2016 - 8:51:17 AM
Contributor : Samuel Bernard <>
Submitted on : Friday, May 15, 2009 - 5:56:35 PM
Last modification on : Thursday, January 28, 2021 - 10:26:02 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
Collections
IMAG | INRIA | UNIV-FCOMTE | IRISA | ALGOTEL2009 | UMR6623 | UNIV-RENNES1 | UPMC | LIP6 | UMR8623 | CNRS | IRISA-D2 | UNIV-LILLE3 | INSTITUT-TELECOM | UR1-UFR-ISTIC | UNIV-RENNES | VERIMAG | SORBONNE-UNIVERSITE | SU-SCIENCES | INSA-RENNES | UGA | SU-TI | UNIV-BOURGOGNE
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⟩
Metrics
Record views
1093
Files downloads