# Brief Announcement: Distributed Exclusive and Perpetual Tree Searching

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, CNRS - Centre National de la Recherche Scientifique : UMR8623, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, LIFL - Laboratoire d'Informatique Fondamentale de Lille
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>
Domaine :

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)

### 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>

Consultations de
la notice

## 290

Téléchargements du document