Brief Announcement: Distributed Exclusive and Perpetual Tree Searching

Lélia Blin 1, 2 Janna Burman 3, 4 Nicolas Nisse 5
2 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
4 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
5 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : We tackle a practical version of the well known {\it graph searching} problem, where a team of robots aims at capturing an intruder in a graph. The robots and the intruder move along the edges of the graph. The intruder is invisible, arbitrary fast, and omniscient. It is caught whenever it stands on a node occupied by a robot, and cannot escape to a neighboring node. We study graph searching in the CORDA model of mobile computing: robots are asynchronous, and they perform cycles of {\it Look-Compute-Move} actions. Moreover, motivated by physical constraints, we consider the \emph{exclusive} property, stating that no two or more robots can occupy the same node at the same time. In addition, we assume that the network and the robots are anonymous. Finally, robots are \emph{oblivious}, i.e., each robot performs its move actions based only on its current ''vision'' of the positions of the other robots. Our objective is to characterize, for a graph $G$, the set of integers $k$ such that graph searching can be achieved by a team of $k$ robots starting from \emph{any} $k$ distinct nodes in $G$. Our main result consists in a full characterization of this set, for any asymmetric tree. Towards providing a characterization for all trees, including trees with non-trivial automorphisms, we have also provides a set of positive and negative results, including a full characterization for any line. All our positive results are based on the design of algorithms enabling \emph{perpetual} graph searching to be achieved with the desired number of robots.
Type de document :
Communication dans un congrès
DISC 2012 - 26th International Symposium on Distributed Computing, Oct 2012, Salvador, Brazil. Springer, 7611, pp.403-404, 2012, Lecture Notes in Computer Science. <10.1007/978-3-642-33651-5_29>
Liste complète des métadonnées

https://hal.inria.fr/hal-00741982
Contributeur : Nicolas Nisse <>
Soumis le : lundi 15 octobre 2012 - 16:00:14
Dernière modification le : jeudi 9 février 2017 - 15:03:24
Document(s) archivé(s) le : mercredi 16 janvier 2013 - 03:40:42

Fichier

disc2012-final88-2.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Lélia Blin, Janna Burman, Nicolas Nisse. Brief Announcement: Distributed Exclusive and Perpetual Tree Searching. DISC 2012 - 26th International Symposium on Distributed Computing, Oct 2012, Salvador, Brazil. Springer, 7611, pp.403-404, 2012, Lecture Notes in Computer Science. <10.1007/978-3-642-33651-5_29>. <hal-00741982>

Partager

Métriques

Consultations de
la notice

399

Téléchargements du document

91