Gathering in Dynamic Rings
Gathering in Dynamic Rings
复制标题
汇聚动环
DOI：
10.1007/978-3-319-72050-0_20
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
G. Viglietta
中科院分区：
文献类型：
--
作者：
Giuseppe Antonio Di Luna;P. Flocchini;L. Pagli;G. Prencipe;N. Santoro;G. Viglietta
Thegathering（or multi-agent rendezvous）problem需要一组移动的agent，任意地定位在网络的不同节点上，在有限的时间内在同一个位置分组，而不是固定在advanced.The广泛的现有文献关于这个问题共享相同的基本假设：拓扑结构不改变在rendezvous或gathering;这也是真实的那些调查，考虑故障节点。本文研究了聚集非动态图的问题，即拓扑结构不断变化且位置不可预测的网络，研究了在匿名节点的adjacent环中聚集移动的agent的可行性，这些agent是相同的且没有明确的通信能力，我们考虑的动态类是经典的1-区间连通性，即，然而，动态图在任何时间点都是连接的。我们专注于影响因素，如手性（即，方向的常识）和交叉检测（即，检测的能力，当遍历一个边缘，是否有一些代理是在其他方向上遍历它），对问题的可解性;我们建立了几个results.We提供了一个完整的表征类的初始配置，收集问题是可解的存在和不存在交叉检测和手性。的特征的可行性结果都是建设性的：我们提供了分布式算法，允许代理人在低多项式时间内收集。特别地，交叉检测的聚集算法是时间最优的。我们还表明，交叉检测是一个强大的计算元素。事实上，我们证明，没有手征，知识的环sizenis严格更强大的知识的数量kof代理;另一方面，对于手征性，n的知识可以用k的知识代替，产生相同类别的可行初始配置。从我们的研究可以得出，对于收集问题，由环的动态特性产生的计算障碍可以通过手性或交叉检测的存在来克服。
Thegathering(ormulti-agent rendezvous) problem requires a set of mobile agents, arbitrarily positioned at different nodes of a network to group within finite time at the same location, not fixed in advanced.The extensive existing literature on this problem shares the same fundamental assumption: the topological structure does not change during the rendezvous or the gathering; this is true also for those investigations that consider faulty nodes. In other words, they only considerstatic graphs.In this paper we start the investigation of gathering indynamic graphs, that is networks where the topology changes continuously and at unpredictable locations.We study the feasibility of gathering mobile agents, identical and without explicit communication capabilities, in adynamic ringof anonymous nodes; the class of dynamics we consider is the classic1-interval-connectivity; i.e., dynamic graphs that are however connected at any point in time. We focus on the impact that factors such aschirality(i.e., a common sense of orientation) andcross detection(i.e., the ability to detect, when traversing an edge, whether some agent is traversing it in the other direction), have on the solvability of the problem; and we establish several results.We provide a complete characterization of the classes of initial configurations from which the gathering problem is solvable in presence and in absence of cross detection and of chirality. The feasibility results of the characterization are all constructive: we provide distributed algorithms that allow the agents to gather within low polynomial time. In particular, the algorithms for gathering with cross detection are time optimal.We also show that cross detection is a powerful computational element. Indeed, we prove that, without chirality, knowledge of the ring sizenis strictly more powerful than knowledge of the numberkof agents; on the other hand, with chirality, knowledge ofncan be substituted by knowledge ofk, yielding the same classes of feasible initial configurations.From our investigation it follows that, for the gathering problem, the computational obstacles created by the dynamic nature of the ring can be overcome by the presence of chirality or of cross-detection.
循环图和过滤的半 Gorenstein 环
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
Mitsuhiro Miyazaki;Katsuyuki Naoi;宮崎充弘
通讯作者：
宮崎充弘