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 kk 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 nn nodes in which Ω(n)Ω(n) bits of memory per agent is required to solve the gathering problem in O(n)O(n) time (asymptotically time-optimal). Then, we present an asymptotically time-optimal gathering algorithm. This algorithm can be executed if each agent has O(n)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.

► We consider the gathering problem of kk anonymous agents in asynchronous trees.
► We prove linear space per agent is required for linear time gathering algorithms.
► We propose a linear time and space gathering algorithm.