Computability of Perpetual Exploration in Highly Dynamic Rings

Marjorie Bournat 1 Swan Dubois 1 Franck Petit 1
1 Regal - Large-Scale Distributed Systems and Applications
Inria de Paris, LIP6 - Laboratoire d'Informatique de Paris 6
Abstract : We consider systems made of autonomous mobile robots evolving in highly dynamic discrete environment, i.e., graphs where edges may appear and disappear unpredictably without any recurrence, stability, nor periodicity assumption. Robots are uniform (they execute the same algorithm), they are anonymous (they are devoid of any observable ID), they have no means allowing them to communicate together, they share no common sense of direction, and they have no global knowledge related to the size of the environment. However, each of them is endowed with persistent memory and is able to detect whether it stands alone at its current location. A highly dynamic environment is modeled by a graph such that its topology keeps continuously changing over time. In this paper, we consider only dynamic graphs in which nodes are anonymous, each of them is infinitely often reachable from any other one, and such that its underlying graph (i.e., the static graph made of the same set of nodes and that includes all edges that are present at least once over time) forms a ring of arbitrary size. In this context, we consider the fundamental problem of perpetual exploration: each node is required to be infinitely often visited by a robot. This paper analyses the computability of this problem in (fully) synchronous settings, i.e., we study the deterministic solvability of the problem with respect to the number of robots. We provide three algorithms and two impossibility results that characterize, for any ring size, the necessary and sufficient number of robots to perform perpetual exploration of highly dynamic rings.
Type de document :
Communication dans un congrès
The 37th IEEE International Conference on Distributed Computing Systems (ICDCS 2017) , Jun 2017, Atlanta, United States
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger
Contributeur : Swan Dubois <>
Soumis le : vendredi 7 juillet 2017 - 09:17:43
Dernière modification le : samedi 24 novembre 2018 - 01:40:24
Document(s) archivé(s) le : mercredi 24 janvier 2018 - 08:30:23


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01548109, version 1


Marjorie Bournat, Swan Dubois, Franck Petit. Computability of Perpetual Exploration in Highly Dynamic Rings. The 37th IEEE International Conference on Distributed Computing Systems (ICDCS 2017) , Jun 2017, Atlanta, United States. 〈hal-01548109〉



Consultations de la notice


Téléchargements de fichiers