Deterministic gathering of anonymous agents in arbitrary networks

Abstract : A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, possibly at different times, have to meet at the same node. Agents are anonymous (identical), execute the same deterministic algorithm and move in synchronous rounds along links of the network. Which configurations are gatherable and how to gather all of them deterministically by the same algorithm? We give a complete solution of this gathering problem in arbitrary networks. We characterize all gatherable configurations and give two universal deterministic gathering algorithms, i.e., algorithms that gather all gatherable configurations. The first algorithm works under the assumption that an upper bound n on the size of the network is known. The second one works under the assumption that no upper bound n on the size of the network is known. The time of the first algorithm is polynomial in the upper bound n on the size of the network, and the time of the second algorithm is polynomial in the (unknown) size itself. Our results have an important consequence for the leader election problem for anonymous agents in arbitrary graphs. For anonymous agents in graphs, leader election turns out to be equivalent to gathering with detection. Hence, we also obtain a complete solution of the leader election problem for anonymous agents in arbitrary graphs.
Liste complète des métadonnées

Littérature citée [35 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00637328
Contributeur : Yoann Dieudonné <>
Soumis le : mercredi 2 novembre 2011 - 17:01:39
Dernière modification le : lundi 11 décembre 2017 - 14:04:10
Document(s) archivé(s) le : vendredi 3 février 2012 - 02:35:24

Fichiers

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

Identifiants

  • HAL Id : inria-00637328, version 2

Collections

Citation

Yoann Dieudonné, Andrzej Pelc. Deterministic gathering of anonymous agents in arbitrary networks. [Research Report] 2011. 〈inria-00637328v2〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

50