Mobile agent rendezvous in a ring
Mobile agent rendezvous in a ring
复制标题
移动代理在环中会合
DOI：
10.1109/icdcs.2003.1203510
复制
发表时间：
2003
期刊：
影响因子：
--
通讯作者：
D. Krizanc
中科院分区：
文献类型：
--
作者：
E. Kranakis;N. Santoro;C. Sawchuk;D. Krizanc
在交会搜索问题中，两个移动代理必须沿着网络的n个节点移动，以最小化相遇或交会所需的时间。然而，当移动代理是相同的并且网络是匿名的时，所产生的对称性可能使问题无法解决。通常通过让移动代理运行随机算法或不同的确定性算法来打破对称性。我们研究了使用相同的令牌来打破对称性，以便两个移动代理可以运行相同的确定性算法。在给出了n节点环上使用相同令牌打破对称性的显式条件后，我们给出了不同参数集集合搜索问题的时间复杂度和存储复杂度的上下界。虽然这些结果表明移动代理的内存和会合搜索问题的时间复杂性之间可能存在权衡，但我们证明这种权衡是有限的。
In the rendezvous search problem, two mobile agents must move along the n nodes of a network so as to minimize the time required to meet or rendezvous. When the mobile agents are identical and the network is anonymous, however, the resulting symmetry can make the problem impossible to solve. Symmetry is typically broken by having the mobile agents run either a randomized algorithm or different deterministic algorithms. We investigate the use of identical tokens to break symmetry so that the two mobile agents can run the same deterministic algorithm. After deriving the explicit conditions under which identical tokens can be used to break symmetry on the n node ring, we derive the lower and upper bounds for the time and memory complexity of the rendezvous search problem with various parameter sets. While these results suggest a possible tradeoff between the mobile agents' memory and the time complexity of the rendezvous search problem, we prove that this tradeoff is limited.