Gathering of Six Robots on Anonymous Symmetric Rings

Abstract : The paper deals with a recent model of robot-based computing which makes use of identical, memoryless mobile robots placed on nodes of anonymous graphs. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot. In particular, we consider the case of only six robots placed on the nodes of an anonymous ring in such a way they constitute a symmetric placement with respect to one single axis of symmetry, and we ask whether there exists a strategy that allows the robots to gather at one single node. This is in fact the first case left open after a series of papers [1,2,3,4] dealing with the gathering of oblivious robots on anonymous rings. As long as the gathering is feasible, we provide a new distributed approach that guarantees a positive answer to the posed question. Despite the very special case considered, the provided strategy turns out to be very interesting as it neither completely falls into symmetry-breaking nor into symmetry-preserving techniques.
Type de document :
Communication dans un congrès
Adrian Kosowski and Masafumi Yamashita. Structural Information and Communication Complexity, Jun 2011, Gdansk, Poland. Springer, 6796, pp.174-185, 2011, Lecture Notes in Computer Science; Structural Information and Communication Complexity. <10.1007/978-3-642-22212-2_16>
Liste complète des métadonnées


https://hal.inria.fr/hal-00644039
Contributeur : Gianlorenzo D'Angelo <>
Soumis le : mercredi 23 novembre 2011 - 14:45:15
Dernière modification le : mardi 22 mai 2012 - 15:13:30
Document(s) archivé(s) le : vendredi 24 février 2012 - 02:26:51

Fichier

GatheringSixRobots.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Gianlorenzo D'Angelo, Gabriele Di Stefano, Alfredo Navarra. Gathering of Six Robots on Anonymous Symmetric Rings. Adrian Kosowski and Masafumi Yamashita. Structural Information and Communication Complexity, Jun 2011, Gdansk, Poland. Springer, 6796, pp.174-185, 2011, Lecture Notes in Computer Science; Structural Information and Communication Complexity. <10.1007/978-3-642-22212-2_16>. <hal-00644039>

Partager

Métriques

Consultations de
la notice

339

Téléchargements du document

173