Mobile Agent Rendezvous in a Synchronous Torus
Mobile Agent Rendezvous in a Synchronous Torus
复制标题
同步环面中的移动代理会合
DOI：
10.1007/11682462_60
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
Euripides Markou
中科院分区：
文献类型：
--
作者：
E. Kranakis;D. Krizanc;Euripides Markou
我们考虑了具有方向感的同步环面上具有令牌的相同移动代理(即运行相同的确定性算法)的交会问题，并且证明了一个令牌和多个令牌之间存在显著的计算差异。更具体地说，我们证明了：1)两个具有固定数量的不可移动令牌或具有一个可移动令牌的代理，如果它们有(Logn)个记忆，则每个代理不能相遇，而只要它们有一个不可移动的令牌和(Logn)个记忆，它们就可以执行检测相会；相反，当两个代理各有两个可移动令牌时，在任意n×m(分别为n×n)个环面上具有恒定记忆的相会(分别具有检测相遇)是可能的；最后，3)两个具有三个可移动令牌且具有恒定记忆的代理可以在一个×mTorus中执行相会和检测。这是文献中第一次研究代理在这样一个网络中满足所需的令牌数量、内存和知识之间的权衡。
We consider the rendezvous problem for identical mobile agents (i.e., running the same deterministic algorithm) with tokens in a synchronous torus with a sense of direction and show that there is a strikingcomputational differencebetween one and more tokens. More specifically, we show that 1) two agents with a constant number of unmovable tokens, or with one movable token, each cannot rendezvous if they haveo(logn) memory, while they can perform rendezvous with detection as long as they have one unmovable token andO(logn) memory; in contrast, 2) when two agents have two movable tokens each then rendezvous (respectively, rendezvous with detection) is possible with constant memory in an arbitraryn×m(respectively,n×n) torus; and finally, 3) two agents with three movable tokens each and constant memory can perform rendezvous with detection in an×mtorus. This is the first publication in the literature that studies tradeoffs between the number of tokens, memory and knowledge the agents need in order to meet in such a network.
循环图和过滤的半 Gorenstein 环
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
Mitsuhiro Miyazaki;Katsuyuki Naoi;宮崎充弘
通讯作者：
宮崎充弘