Rendezvous of Asynchronous Mobile Agents in Trees
スポンサーリンク
概要
- 論文の詳細を見る
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.
- 一般社団法人情報処理学会の論文
- 2010-01-19
著者
-
Daisuke Baba
Graduate School Of Information Science And Technology Osaka University Osaka Japan.
-
Toshimitsu Masuzawa
Graduate School Of Information Science And Technology Osaka University Osaka Japan.
-
Tomoko Izumi
College Of Information Science And Engineering Ritsumeikan University Shiga Japan.
-
Fukuhito Ooshita
Graduate School of Information Science and Technology, Osaka University
-
Hirotsugu Kakugawa
Graduate School of Information Science and Technology, Osaka University
-
Fukuhito Ooshita
Graduate School Of Information Science And Technology Osaka University Osaka Japan.
-
Hirotsugu Kakugawa
Graduate School Of Information Science And Technology Osaka University Japan
関連論文
- Loosely-stabilizing Leader Election in Population Protocol Model
- Complexity of Minimum Certificate Dispersal Problem with Tree Structure
- Rendezvous of Asynchronous Mobile Agents in Trees
- A self-stabilizing distributed algorithm for the multicoloring problem in dynamic networks