2024-11-06T11:58:17Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000673032024-03-29T05:26:34Z01164:02592:05970:05971
Rendezvous of Asynchronous Mobile Agents in TreesRendezvous of Asynchronous Mobile Agents in Treesenghttp://id.nii.ac.jp/1001/00067303/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=67303&item_no=1&attribute_id=1&file_no=1Copyright (c) 2010 by the Information Processing Society of JapanGraduate 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, BabaTomoko, IzumiFukuhito, OoshitaHirotsugu, KakugawaToshimitsu, MasuzawaThis 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-1284182010-01-192009-12-24