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
Université Sciences et Technologies - Bordeaux 1, Inria Bordeaux - Sud-Ouest, École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), CNRS - Centre National de la Recherche Scientifique : UMR5800
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.
Type de document :
Communication dans un congrès
David and Sebastien Tixeuil. 10ème Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications (AlgoTel'08), 2008, Saint-Malo, France. pp.101-104, 2008
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00374463
Contributeur : David Coudert <>
Soumis le : mercredi 8 avril 2009 - 17:02:46
Dernière modification le : jeudi 11 janvier 2018 - 06:22:11
Document(s) archivé(s) le : jeudi 10 juin 2010 - 20:07:00

Fichier

26.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00374463, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

246

Téléchargements de fichiers

92