Gathering and Exclusive Searching on Rings under Minimal Assumptions
Gathering and Exclusive Searching on Rings under Minimal Assumptions
复制标题
最小假设下环的聚集和排它搜索
DOI：
10.1007/978-3-642-45249-9_10
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Nicolas Nisse
中科院分区：
文献类型：
--
作者：
Gianlorenzo D'angelo;A. Navarra;Nicolas Nisse
考虑将一组具有最小功能的移动机器人放置在离散匿名环的不同节点上。异步地，每个机器人拍摄环的快照，确定哪些节点被机器人占用或空。根据观察到的配置，它决定是否移动到相邻节点之一。在第一种情况下，它最终执行计算的移动。计算也取决于所需的任务。在本文中，我们解决了众所周知的收集和排除搜索任务。在前一个问题中，所有机器人最终必须同时占据同一个节点。在后一个问题中，目标是清除图的所有边。如果一条边被机器人穿过，或者它的两个端点都被占用，则该边被清除。我们考虑排他性研究，其中必须确保两个机器人永远不会占用同一个节点。此外，由于机器人是无意识的，清理是永久的，也就是说，清理环的频率是无限的。在文献中，大多数贡献都局限于初始配置的子集。在这里，我们设计了两种不同的算法，并提供了允许在最小假设下解决问题的初始配置的表征。
Consider a set of mobile robots with minimal capabilities placed over distinct nodes of a discrete anonymous ring. Asynchronously, each robot takes a snapshot of the ring, determining which nodes are either occupied by robots or empty. Based on the observed configuration, it decides whether to move to one of its adjacent nodes or not. In the first case, it performs the computed move, eventually. The computation also depends on the required task. In this paper, we solve both the well-knownGatheringandExclusive Searchingtasks. In the former problem, all robots must simultaneously occupy the same node, eventually. In the latter problem, the aim is to clear all edges of the graph. An edge is cleared if it is traversed by a robot or if both its endpoints are occupied. We consider theexclusivesearching where it must be ensured that two robots never occupy the same node. Moreover, since the robots are oblivious, the clearing isperpetual, i.e., the ring is cleared infinitely often. In the literature, most contributions are restricted to a subset of initial configurations. Here, we design two different algorithms and provide a characterization of the initial configurations that permit the resolution of the problems under minimal assumptions.
DOI：
10.1007/978-3-642-25873-2_18
发表时间：
2011
期刊：
Proc.15th Intl.Conf.on Principles of Distributed Systems (OPODIS 2011)
影响因子：
--
作者：
F.Bonnet;A.Milani;M.Potop-Butucaru;S.Tixeuil
通讯作者：
S.Tixeuil