FLOCCHINI, Paola; ILCINKAS, David; SANTORO, Nicola

doi:10.1007/s00453-011-9496-3

Metadatos

Licencia de uso del documento

FLOCCHINI, Paola
School of Electrical Engineering and Computer Science [EECS]

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]

Idioma

Article de revue

Este ítem está publicado en

Algorithmica. 2012-04, vol. 62, n° 3-4, p. pages 1006-1033

Springer Verlag

Resumen en inglés

We prove that, for the black hole search problem in networks of arbitrary but known topology, the pebble model of agent interaction is computationally as powerful as the whiteboard model; furthermore the complexity is exactly the same. More precisely, we prove that a team of 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 Θ(nlog n) moves, where n is the number of nodes, even when the links are not FIFO. These results are obtained with a novel algorithmic technique, ping-pong, for agents using pebbles.< Leer menos

Palabras clave en inglés

Distributed computing

Graph exploration

Mobile agents

Autonomous robots

Dangerous graphs

URI

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

DOI

http://dx.doi.org/10.1007/s00453-011-9496-3

Proyecto ANR

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

Orígen

Importado de Hal

Centros de investigación

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