Recherche optimale de trou noir avec cailloux

Abstract

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.