http://swrc.ontoware.org/ontology#TechnicalReport
Rendezvous of Asynchronous Mobile Agents in Trees
en
Graduate School of Information Science and Technology, Osaka University, Osaka, Japan.
College of Information Science and Engineering, Ritsumeikan University, Shiga, Japan.
Graduate School of Information Science and Technology, Osaka University, Osaka, Japan.
Graduate School of Information Science and Technology, Osaka University, Osaka, Japan.
Graduate School of Information Science and Technology, Osaka University, Osaka, Japan.
Daisuke Baba
Tomoko Izumi
Fukuhito Ooshita
Hirotsugu Kakugawa
Toshimitsu Masuzawa
This paper reveals 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 a finite time. We first prove that at least Ω(n) memory size per agent is required to solve the rendezvous problem in O(n) time where n is the number of nodes. Next, we present the rendezvous algorithm which terminates in O(n) time. The space complexity of this algorithm is also O(n) per agent. From this lower/upper bound, Θ(n) memory size per agent is necessary and sufficient to solve the problem in O(n) time (asymptotically time-optimal). Finally, we present the asymptotically space-optimal rendezvous algorithm. This algorithm has space complexity O(log n) and time complexity O(Δn8) where Δ is the maximum degree of the tree.
This paper reveals 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 a finite time. We first prove that at least Ω(n) memory size per agent is required to solve the rendezvous problem in O(n) time where n is the number of nodes. Next, we present the rendezvous algorithm which terminates in O(n) time. The space complexity of this algorithm is also O(n) per agent. From this lower/upper bound, Θ(n) memory size per agent is necessary and sufficient to solve the problem in O(n) time (asymptotically time-optimal). Finally, we present the asymptotically space-optimal rendezvous algorithm. This algorithm has space complexity O(log n) and time complexity O(Δn8) where Δ is the maximum degree of the tree.
AN1009593X
研究報告アルゴリズム（AL）
2010-AL-128
4
1-8
2010-01-19