Exclusive Perpetual Ring Exploration without Chirality

Abstract : In this paper, we study the exclusive perpetual exploration problem with mobile anonymous and oblivious robots in a discrete space. Our results hold for the most generic settings: robots are asynchronous and are not given any sense of direction, so the left and right sense (i.e. chirality) is decided by the adversary that schedules robots for execution, and may change between invocations of a particular robots (as robots are oblivious). We investigate both the minimal and the maximal number of robots that are necessary and sufficient to solve the exclusive perpetual exploration problem. On the minimal side, we prove that three deterministic robots are necessary and sufficient, provided that the size n of the ring is at least 10, and show that no protocol with three robots can exclusively perpetually explore a ring of size less than 10. On the maximal side, we prove that k = n − 5 robots are necessary and sufficient to exclusively perpetually explore a ring of size n when n is co-prime with k.
Type de document :
Communication dans un congrès
Nancy A. Lynch and Alexander A. Shvartsman. DISC 2010 - 24th International Symposium Distributed Computing, Sep 2010, Cambridge, MA, United States. Springer, 6343, pp.312-327, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-15763-9_29〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00992700
Contributeur : Corentin Travers <>
Soumis le : lundi 19 mai 2014 - 10:55:36
Dernière modification le : vendredi 25 mai 2018 - 12:02:03

Lien texte intégral

Identifiants

Collections

Citation

Lélia Blin, Alessia Milani, Maria Potop-Butucaru, Sébastien Tixeuil. Exclusive Perpetual Ring Exploration without Chirality. Nancy A. Lynch and Alexander A. Shvartsman. DISC 2010 - 24th International Symposium Distributed Computing, Sep 2010, Cambridge, MA, United States. Springer, 6343, pp.312-327, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-15763-9_29〉. 〈hal-00992700〉

Partager

Métriques

Consultations de la notice

280