Linear time and space gathering of anonymous mobile agents in asynchronous trees
Linear time and space gathering of anonymous mobile agents in asynchronous trees
复制标题
异步树中匿名移动代理的线性时空聚集
DOI：
10.1016/j.tcs.2013.01.022
复制
发表时间：
2013
影响因子：
1.1
通讯作者：
Toshimitsu Masuzawa
中科院分区：
文献类型：
--
作者：
Daisuke Baba;Tomoko Izumi;Fukuhito Ooshita;Hirotsugu Kakugawa;Toshimitsu Masuzawa
研究了异步匿名树网络中具有k个匿名代理的聚集问题的(理想)时间和空间复杂性之间的关系。聚集问题要求网络中的所有代理必须在有限时间内在单个节点相遇。虽然已知一种渐近空间最优算法，但其时间复杂度相当大。本文研究了渐近(理想)时间最优算法，并研究了渐近时间最优算法的每个代理的最小内存需求。首先，我们证明了存在一个有n个结点的树，其中每个代理需要Ω(N)比特的内存才能在O(N)时间内(渐近时间最优)解决聚集问题。然后，我们提出了一种渐近时间最优的聚集算法。如果每个代理具有O(N)位内存，则可以执行该算法。根据这个上下界，该算法在时间复杂度为渐近最优的条件下是渐近空间最优的。
We investigate the relation between the (ideal) time and space complexities for the gathering problem with k anonymous agents in asynchronous anonymous tree networks. The gathering problem requires that all the agents in the network have to meet at a single node within a finite time. Although an asymptotically space-optimal algorithm is known, its time complexity is quite large. In this paper, we consider asymptotically (ideal-)time-optimal algorithms and investigate the minimum memory requirement per agent for asymptotically time-optimal algorithms. First, we show that there exists a tree with n nodes in which Ω(n) bits of memory per agent is required to solve the gathering problem in O(n) time (asymptotically time-optimal). Then, we present an asymptotically time-optimal gathering 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.
登录
查看更多内容
令牌失败时移动代理会合
DOI：
10.1007/978-3-540-27796-5_15
发表时间：
2004
期刊：
--
影响因子：
--
作者：
P. Flocchini;E. Kranakis;D. Krizanc;F. Luccio;N. Santoro;C. Sawchuk
通讯作者：
C. Sawchuk
DOI：
10.1007/978-3-642-25873-2_29
发表时间：
2011
期刊：
--
影响因子：
--
作者：
Samuel Guilbault;A. Pelc
通讯作者：
A. Pelc
移动代理使用错误令牌在环中会合
DOI：
10.1007/978-3-540-77444-0_29
发表时间：
2008
期刊：
--
影响因子：
--
作者：
S. Das
通讯作者：
S. Das
使用对数内存进行树探索
影响因子：
1.3
作者：
Ambühl C
通讯作者：
Ambühl C
DOI：
10.1007/11611257_26
发表时间：
2006
期刊：
--
影响因子：
--
作者：
L. Gąsieniec;E. Kranakis;D. Krizanc;X. Zhang
通讯作者：
X. Zhang