Asynchronous Exclusive Perpetual Grid Exploration without Sense of Direction

François Bonnet 1 Alessia Milani 2 Maria Potop-Butucaru 3 Sébastien Tixeuil 4
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
3 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
4 NPA - Networks and Performance Analysis
LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : In this paper, we investigate the exclusive perpetual exploration of grid shaped networks using anonymous, oblivious and fully asynchronous robots. Our results hold for robots without sense of direction (i.e. they do not agree on a common North, nor do they agree on a common left and right ; furthermore, the "North" and "left" of each robot is decided by an adversary that schedules robots for execution, and may change between invocations of particular robots). We focus on the minimal number of robots that are necessary and sufficient to solve the problem in general grids. In more details, we prove that three deterministic robots are necessary and sufficient, provided that the size of the grid is n ×m with 3 ≤ n ≤ m or n = 2 and m ≥ 4. Perhaps surprisingly, and unlike results for the exploration with stop problem (where grids are "easier" to explore and stop than rings with respect to the number of robots), exclusive perpetual exploration requires as many robots in the ring as in the grid. Furthermore, we propose a classification of configurations such that the space of configurations to be checked is drastically reduced. This pre-processing lays the bases for the automated verification of our algorithm for general grids as it permits to avoid combinatorial explosion.
Type de document :
Communication dans un congrès
Antonio Fernández Anta and Giuseppe Lipari and Matthieu Roy. OPODIS 2011 - 15th International Conference on Principles of Distributed Systems, Dec 2011, Toulouse, France. Springer, 7109, pp.251-265, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-25873-2_18〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00992679
Contributeur : Corentin Travers <>
Soumis le : lundi 19 mai 2014 - 10:47:24
Dernière modification le : vendredi 31 août 2018 - 09:25:54

Lien texte intégral

Identifiants

Citation

François Bonnet, Alessia Milani, Maria Potop-Butucaru, Sébastien Tixeuil. Asynchronous Exclusive Perpetual Grid Exploration without Sense of Direction. Antonio Fernández Anta and Giuseppe Lipari and Matthieu Roy. OPODIS 2011 - 15th International Conference on Principles of Distributed Systems, Dec 2011, Toulouse, France. Springer, 7109, pp.251-265, 2011, Lecture Notes in Computer Science. 〈10.1007/978-3-642-25873-2_18〉. 〈hal-00992679〉

Partager

Métriques

Consultations de la notice

424