FLOCCHINI, Paola; ILCINKAS, David; SANTORO, Nicola

doi:10.1007/978-3-540-87779-0_16

Métadonnées

Licence d’utilisation du document

FLOCCHINI, Paola
Distributed Computing Research Group [Ottawa]

ILCINKAS, David
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithmics for computationally intensive applications over wide scale distributed platforms [CEPAGE]

SANTORO, Nicola
School of Computer Science [Ottawa]

Langue

Communication dans un congrès

Ce document a été publié dans

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

Résumé en anglais

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.< Réduire

Mots clés en anglais

distributed computing

graph exploration

mobile agents

autonomous robots

dangerous graphs

URI

https://oskar-bordeaux.fr/handle/20.500.12278/198621

DOI

http://dx.doi.org/10.1007/978-3-540-87779-0_16

Project ANR

Algorithm Design and Analysis for Implicitly and Incompletely Defined Interaction Networks - ANR-07-BLAN-0322

Origine

Importé de hal

Unités de recherche

Laboratoire Bordelais de Recherche en Informatique (LaBRI) - UMR 5800