Gathering on rings under the Look–Compute–Move model
Gathering on rings under the Look–Compute–Move model
复制标题
在“观察-计算-移动”模型下聚集在环上
DOI：
10.1007/s00446-014-0212-9
复制
发表时间：
2014
影响因子：
1.3
通讯作者：
A. Navarra
中科院分区：
文献类型：
--
作者：
Gianlorenzo D'angelo;G. Stefano;A. Navarra
一组任意放置在匿名环的不同节点上的机器人必须在一个公共节点上相遇，并且仍然存在。这个问题在文献中被称为聚集。匿名和不经意的机器人在Look-Compute-Move循环中运行;在一个循环中，机器人获取当前配置的快照（Look），决定是否保持空闲或移动到其邻居之一（Compute），并在后一种情况下使计算的即时移动（Move）。机器人之间的周期是异步的。此外，每个机器人被赋予所谓的多重性检测能力，也就是说，它能够在其查找操作期间检测节点是否为空，或被一个机器人占用，或被大于一个的未定义数量的机器人占用。所描述的问题在过去几年中得到了广泛的研究。然而，已知的解决方案仅适用于特定的初始配置，并且留下了一些悬而未决的案例。在本文中，我们提供了一个算法，解决了一般的问题，但很少的边缘和特定的情况下，并能够检测所有的不可分割的配置。值得注意的是，我们的新算法利用了一些以前的技术，并将它们与新的策略相结合，以处理任何初始配置，即使是那些由以前的作品留下的开放。
A set of robots arbitrarily placed on different nodes of an anonymous ring have to meet at one common node and there remain. This problem is known in the literature as thegathering. Anonymous and oblivious robots operate in Look–Compute–Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), decides whether to stay idle or to move to one of its neighbors (Compute), and in the latter case makes the computed move instantaneously (Move). Cycles are asynchronous among robots. Moreover, each robot is empowered by the so calledmultiplicity detectioncapability, that is, it is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. The described problem has been extensively studied during the last years. However, the known solutions work only for specific initial configurations and leave some open cases. In this paper, we provide an algorithm which solves the general problem but for few marginal and specific cases, and is able to detect all the ungatherable configurations. It is worth noting that our new algorithm makes use of some previous techniques and unifies them with new strategies in order to deal with any initial configuration, even those left open by previous works.
循环图和过滤的半 Gorenstein 环
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
Mitsuhiro Miyazaki;Katsuyuki Naoi;宮崎充弘
通讯作者：
宮崎充弘