Space-efficient Uniform Deployment of Mobile Agents in Asynchronous Unidirectional Rings
Space-efficient Uniform Deployment of Mobile Agents in Asynchronous Unidirectional Rings
复制标题
异步单向环中移动代理的空间高效统一部署
DOI：
10.1016/j.tcs.2019.12.031
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Toshimitsu Masuzawa
中科院分区：
文献类型：
--
作者：
Masahiro Shibata;Hirotsugu Kakugawa;Toshimitsu Masuzawa
在本文中，我们考虑异步单向环网中移动代理的统一部署问题。这个问题需要代理在网络中均匀分布。在本文中，我们重点关注解决问题所需的每个代理的内存空间。我们考虑两个问题设置。第一个设置假设代理没有多重性检测，即代理无法检测另一个代理是否停留在同一节点。在这种情况下，我们表明每个代理需要 Ω (log n) 内存空间来解决问题，其中 n 是节点数。此外，我们提出了一种算法来解决每个智能体具有 O (k+ log n) 内存空间的问题，其中 k 是智能体的数量。第二个设置假设每个智能体都配备了弱重数检测，即智能体可以检测另一个智能体是否停留在同一节点，但无法获得有关智能体数量的任何其他信息。然后，我们证明每个代理的内存空间可以减少到 O (log k+ log log n)。据我们所知，这是第一个考虑多重性检测对解决问题所需的内存空间的影响的研究。
In this paper, we consider the uniform deployment problem of mobile agents in asynchronous unidirectional ring networks. This problem requires agents to spread uniformly in the network. In this paper, we focus on the memory space per agent required to solve the problem. We consider two problem settings. The first setting assumes that agents have no multiplicity detection, that is, agents cannot detect whether another agent is staying at the same node or not. In this case, we show that each agent requires Ω (log n) memory space to solve the problem, where n is the number of nodes. In addition, we propose an algorithm to solve the problem with O (k+ log n) memory space per agent, where k is the number of agents. The second setting assumes that each agent is equipped with the weak multiplicity detection, that is, agents can detect whether another agent is staying at the same node or not, but cannot get any other information about the number of the agents. Then, we show that the memory space per agent can be reduced to O (log k+ log log n). To the best of our knowledge, this is the first research considering the effect of the multiplicity detection on memory space required to solve problems.