Optimal Memory Rendezvous of Anonymous Mobile Agents in a Unidirectional Ring
Optimal Memory Rendezvous of Anonymous Mobile Agents in a Unidirectional Ring
复制标题
单向环中匿名移动代理的最优内存交会
DOI：
10.1007/11611257_26
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
X. Zhang
中科院分区：
文献类型：
--
作者：
L. Gąsieniec;E. Kranakis;D. Krizanc;X. Zhang
我们研究了节点环中 k≥2 个移动代理的会合问题。我们提出了一种新算法，可以解决环上任何非周期性分布的代理的会合问题。移动代理需要使用 O(logk)——按位大小的内部存储器和每个不可区分的令牌。在周期性（但非对称）情况下，我们的新程序允许代理得出结论：会合不可行。众所周知，在对称情况下，如果代理的内存仅限于 ω(loglogn) 位，则代理无法决定会合的可行性，请参阅[15]。在这种情况下，我们展示了新的空间最优确定性算法，可以有效识别对称情况。该算法基于O(logk+loglogn)位内部存储器和提供给每个移动代理的单个令牌。最后，众所周知，在周期性和对称情况下，由于对称性破缺的问题，交会不能通过任何确定性过程来完成。
We study the rendezvous problem withk≥2 mobile agents in an-node ring. We present a new algorithm which solves the rendezvous problem for any non-periodic distribution of agents on the ring. The mobile agents require the use ofO(logk)–bit-wise size of internal memory and one indistinguishable token each. In the periodic (but not symmetric) case our new procedure allows the agents to conclude that rendezvous is not feasible. It is known that in the symmetric case the agents cannot decide the feasibility of rendezvous if their internal memory is limited toω(loglogn) bits, see [15]. In this context we show new space optimal deterministic algorithm allowing effective recognition of the symmetric case. The algorithm is based onO(logk+ loglogn)-bit internal memory and a single token provided to each mobile agent. Finally, it is known that both in the periodic as well as in the symmetric cases the rendezvous cannot be accomplished by any deterministic procedure due to problems with breaking symmetry.