Space-Optimal Rendezvous of Mobile Agents in Asynchronous Trees

We investigate the relation between the time complexity and the space complexity for the rendezvous problem with

k

agents in asynchronous tree networks. The rendezvous problem requires that all the agents in the system have to meet at a single node within finite time. First, we consider asymptotically time-optimal algorithms and investigate the minimum memory requirement per agent for asymptotically time-optimal algorithms. We show that there exists a tree with

n

nodes in which Ω(

n

) bits of memory per agent is required to solve the rendezvous problem in

O

(

n

) time (asymptotically time-optimal). Then, we present an asymptotically time-optimal rendezvous 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. Finally, we consider asymptotically space-optimal algorithms while allowing slowdown in time required to achieve rendezvous. We present an asymptotically space-optimal algorithm that each agent uses only

O

(log

n

) bits of memory. This algorithm terminates in

O

(Δ

n

8

) time where Δ is the maximum degree of the tree.