Skip to Main content Skip to Navigation
Reports

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.
Complete list of metadata

Cited literature [35 references]  Display  Hide  Download

https://hal.inria.fr/inria-00637328
Contributor : Yoann Dieudonné Connect in order to contact the contributor
Submitted on : Wednesday, November 2, 2011 - 5:01:39 PM
Last modification on : Friday, October 8, 2021 - 4:28:06 PM
Long-term archiving on: : Friday, February 3, 2012 - 2:35:24 AM

Files

Dieudonne_Pelc.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

67

Files downloads

188