Linear time and space gathering of anonymous mobile agents in asynchronous trees
We investigate the relation between the (ideal) time and space complexities for the gathering problem with k anonymous agents in asynchronous anonymous tree networks. The gathering problem requires that all the agents in the network have to meet at a single node within a finite time. Although an asymptotically space-optimal algorithm is known, its time complexity is quite large. In this paper, we consider asymptotically (ideal)time-optimal algorithms and investigate the minimum memory requirement per agent for asymptotically time-optimal algorithms. First, we show that there exists a tree with n nodes in which Omega (n) bits of memory per agent is required to solve the gathering problem in O(n) time (asymptotically time-optimal). Then, we present an asymptotically timeoptimal gathering algorithm. This algorithm can be executed if each agent has O(n) bits of memory. From this lower/upper bound, this algorithm is asymptotically space-optimal on the condition that the time complexity is asymptotically optimal. (C) 2013 Elsevier B.V. All rights reserved.
mobile agents space complexity gathering problem tree networks time complexity