FLOCCHINI, Paola; ILCINKAS, David; SANTORO, Nicola

doi:10.1007/s00453-011-9496-3

Métadonnées

Licence d’utilisation du document

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]

Langue

Article de revue

Ce document a été publié dans

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

Springer Verlag

Résumé en anglais

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.< 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/197869

DOI

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

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