Deterministic gathering of anonymous agents in arbitrary networks - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2011

Deterministic gathering of anonymous agents in arbitrary networks

Résumé

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.
Fichier principal
Vignette du fichier
Dieudonne_Pelc.pdf (185.44 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00637328 , version 1 (01-11-2011)
inria-00637328 , version 2 (02-11-2011)

Identifiants

  • HAL Id : inria-00637328 , version 2

Citer

Yoann Dieudonné, Andrzej Pelc. Deterministic gathering of anonymous agents in arbitrary networks. [Research Report] 2011. ⟨inria-00637328v2⟩
88 Consultations
207 Téléchargements

Partager

Gmail Facebook X LinkedIn More