Gathering and Exclusive Searching on Rings under Minimal Assumptions

Gianlorenzo D'Angelo 1 Alfredo Navarra 1 Nicolas Nisse 2, 3
2 COATI - Combinatorics, Optimization and Algorithms for Telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Consider a set of mobile robots with minimal capabilities placed over distinct nodes of a discrete anonymous ring. Asynchronously, each robot takes a snapshot of the ring, determining which nodes are either occupied by robots or empty. Based on the observed configuration, it decides whether to move to one of its adjacent nodes or not. In the first case, it performs the computed move, eventually. The computation also depends on the required task. In this paper, we solve both the well-known Gathering and Exclusive Searching tasks. In the former problem, all robots must simultaneously occupy the same node, eventually. In the latter problem, the aim is to clear all edges of the graph. An edge is cleared if it is traversed by a robot or if both its endpoints are occupied. We consider the exclusive searching where it must be ensured that two robots never occupy the same node. Moreover, since the robots are oblivious, the clearing is perpetual, i.e., the ring is cleared infinitely often. In the literature, most contributions are restricted to a subset of initial configurations. Here, we design two different algorithms and provide a characterization of the initial configurations that permit the resolution of the problems under minimal assumptions.
Type de document :
Communication dans un congrès
Mainak Chatterjee; Jian-Nong Cao; Kishore Kothapalli; Sergio Rajsbaum. 15th International Conference on Distributed Computing and Networking (ICDCN), Jan 2014, Coimbatore, India. Springer, 8314, pp.149-164, 2014, <10.1007/978-3-642-45249-9_10>


https://hal.inria.fr/hal-00931514
Contributeur : Nicolas Nisse <>
Soumis le : mercredi 15 janvier 2014 - 13:55:33
Dernière modification le : lundi 5 octobre 2015 - 17:00:25
Document(s) archivé(s) le : mardi 15 avril 2014 - 22:44:22

Fichier

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

Identifiants

Collections

Citation

Gianlorenzo D'Angelo, Alfredo Navarra, Nicolas Nisse. Gathering and Exclusive Searching on Rings under Minimal Assumptions. Mainak Chatterjee; Jian-Nong Cao; Kishore Kothapalli; Sergio Rajsbaum. 15th International Conference on Distributed Computing and Networking (ICDCN), Jan 2014, Coimbatore, India. Springer, 8314, pp.149-164, 2014, <10.1007/978-3-642-45249-9_10>. <hal-00931514>

Partager

Métriques

Consultations de
la notice

190

Téléchargements du document

112