Skip to Main content Skip to Navigation
Conference papers

Recherche optimale de trou noir avec cailloux

Paola Flocchini 1 David Ilcinkas 2, 3, 4, 5 Nicola Santoro 6
4 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
CNRS - Centre National de la Recherche Scientifique : UMR5800, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Inria Bordeaux - Sud-Ouest, Université Sciences et Technologies - Bordeaux 1
5 CEPAGE - Algorithmics for computationally intensive applications over wide scale distributed platforms
INRIA Futurs, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
Résumé : Un trou noir est un noeud d'un réseau qui détruit tout agent (ou robot) y entrant sans laisser de trace détectable. L'emplacement du trou noir doit être déterminé par une une équipe d'agents mobiles identiques déployée à partir d'un emplacement sain. Pratiquement tous les résultats existants pour des agents asynchrones supposent la présence à chaque noeud d'une mémoire partagée (tableau blanc), de taille logarithmique, sur laquelle les agents peuvent lire et écrire. Un méchanisme moins puissant et moins exigeant consiste en l'utilisation de cailloux identiques (qui peuvent être déposés sur les noeuds, repris, et transportés par les agents), traditionnellement employés pour l'exploration de graphes sains (i.e. sans trou noir). Deux résultats récents montrent qu'il est possible d'utiliser des cailloux comme moyen de communication pour la recherche de trou noir. Ces résultats autorisent cependant les cailloux à être placés non seulement sur les noeuds mais aussi sur les liens. Ils supposent également que les liens sont FIFO. Dans ce papier, nous considérons le modèle des cailloux idéaux, c'est-à-dire le modèle où un caillou ne peut être placé que sur les noeuds, et pas plus d'un caillou ne peut être placé sur un noeud donné. Nous prouvons que pour les réseaux de topologie connue il est possible d'obtenir exactement les mêmes bornes optimales en utilisant des cailloux idéaux qu'en utilisant des tableaux blancs, et ce même si les liens ne sont pas FIFO. Plus précisément, nous prouvons qu'une équipe de deux agents asynchrones, chacun équipé d'un seul caillou indistinguable (qui ne peut être placé que sur les noeuds, avec au plus un caillou par noeud), peut localiser le trou noir. Ce résultat est obtenu en utilisant le nombre optimal de mouvements $\Theta(n\log{n})$, où n est le nombre de noeuds. Pour résumer, nous fournissons la première preuve que, pour la recherche de trou noir, le modèle des cailloux idéaux est aussi puissant que le modèle des tableaux blancs.
Document type :
Conference papers
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal.inria.fr/inria-00374463
Contributor : David Coudert <>
Submitted on : Wednesday, April 8, 2009 - 5:02:46 PM
Last modification on : Thursday, February 11, 2021 - 2:46:03 PM
Long-term archiving on: : Thursday, June 10, 2010 - 8:07:00 PM

File

26.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00374463, version 1

Collections

Citation

Paola Flocchini, David Ilcinkas, Nicola Santoro. Recherche optimale de trou noir avec cailloux. 10ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'08), 2008, Saint-Malo, France. pp.101-104. ⟨inria-00374463⟩

Share

Metrics

Record views

326

Files downloads

163