Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
ILCINKAS, David
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
ILCINKAS, David
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
< Leer menos
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]
Idioma
en
Communication dans un congrès
Este ítem está publicado en
Proceedings of the 22nd International Symposium on Distributed Computing, Proceedings of the 22nd International Symposium on Distributed Computing, DISC 2008, 2008-09. 2008-09, vol. 5218, p. 227-241
Springer Berlin / Heidelberg
Resumen en inglés
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 ...Leer más >
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 $\Theta(n \log n)$ moves, where $n$ is the number of nodes, even when the links are not FIFO.< Leer menos
Palabras clave en inglés
distributed computing
graph exploration
mobile agents
autonomous robots
dangerous graphs
Proyecto ANR
Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322
Orígen
Importado de HalCentros de investigación