Paper Info
Title
Space-optimal rendezvous of mobile agents in asynchronous trees
Abstract
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(logn) bits of memory. This algorithm terminates in O(Δn8) time where Δ is the maximum degree of the tree.
Year
DOI
Venue
2010
10.1007/978-3-642-13284-1_8
SIROCCO
Keywords
Field
DocType
space-optimal rendezvous,asymptotically time-optimal algorithm,asynchronous tree,asymptotically time-optimal,asymptotically space-optimal algorithm,asymptotically time-optimal rendezvous algorithm,asymptotically optimal,mobile agent,asymptotically space-optimal,finite time,time complexity,rendezvous problem,algorithm terminates,maximum degree,space complexity,upper bound
Discrete mathematics,Asynchronous communication,Combinatorics,Upper and lower bounds,Mobile agent,Degree (graph theory),Rendezvous,Time complexity,Asymptotically optimal algorithm,Mathematics,Rendezvous problem
Conference
Volume
ISSN
ISBN
6058
0302-9743
3-642-13283-9
Citations 
PageRank 
References 
9
0.54
10
Authors
5
Name
Order
Citations
PageRank
Daisuke Baba1171.74
Tomoko Izumi214121.33
Fukuhito Ooshita323636.40
Hirotsugu Kakugawa427936.35
Toshimitsu Masuzawa563591.06