Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure TokensReportar como inadecuado

Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 Distributed Computing Research Group Ottawa 2 LaBRI - Laboratoire Bordelais de Recherche en Informatique 3 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 4 School of Computer Science Ottawa

Abstract : We prove that, for the black hole search problem, the pure token model is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of {\em two} asynchronous agents, each endowed with a single identical pebble that can be placed only on nodes, and with no more than one pebble per node can locate the black hole in an arbitrary network of known topology; this can be done with $\Thetan \log n$ moves, where $n$ is the number of nodes, even when the links are not FIFO.

Keywords : distributed computing graph exploration mobile agents autonomous robots dangerous graphs

Autor: Paola Flocchini - David Ilcinkas - Nicola Santoro -



Documentos relacionados