Byzantine gathering in networks
Byzantine gathering in networks
复制标题
网络中的拜占庭式聚会
DOI：
10.1007/s00446-016-0276-9
复制
发表时间：
2015
影响因子：
1.3
通讯作者：
B. Ducourthial
中科院分区：
文献类型：
--
作者：
S. Bouchard;Yoann Dieudonné;B. Ducourthial
本文研究了Dieudonné等人（ACM Trans Algorithms 11（1）：1，2014）中提出的一个开放问题。两个或多个移动的代理从网络的节点开始，并且必须完成收集的任务，该任务包括在同一时间在同一节点处聚集在一起。对手选择代理的初始节点，并为每个代理分配一个不同的正整数（称为标签）。最初，每个代理知道它的标签，但不知道其他代理的标签或它们相对于自己的位置。代理在同步轮中移动，并且只有当位于同一节点时才能相互通信。多达个特工是拜占庭人。一个拜占庭代理可以选择一个任意的端口，当它移动，可以传递任意的信息给其他代理，并可以改变其标签在每一轮，特别是通过伪造标签的另一个代理或通过创建一个全新的。什么是最低数量的好代理，保证确定性收集所有这些，与终止？我们提供确切的答案，这个开放的问题，考虑的情况下，当代理最初知道的网络的大小和情况下，他们不。在前一种情况下，我们证明，而在后一种情况下，我们证明。更准确地说，对于已知规模的网络，我们设计了一个确定性算法收集所有好的代理在任何网络中的好代理的数量至少是。对于未知规模的网络，我们还设计了一个确定性的算法，确保收集所有的好代理在任何网络，但提供的好代理的数量至少是。我们的两种算法在所需的良好代理数量方面都是最优的，因为它们中的每一个都完美地匹配Dieudonné et al.（2014）中所示的各自的下限，当网络的大小已知时，该下限为，当网络的大小未知时，该下限为。也许令人惊讶的是，我们的研究结果突出了一个有趣的功能，当与已知结果的角度来看，这个问题的一个宽松的变种，拜占庭代理不能改变他们的初始标签。事实上，在这个变量下，对于已知规模的网络和未知规模的网络.从这个角度来看，事实证明，当网络的大小已知时，拜占庭代理改变标签的能力会显著影响的值。然而，这种能力的相关性完全消失在最一般的情况下，网络的大小是未知的，无论拜占庭代理是否可以改变他们的标签或没有。
This paper investigates an open problem introduced in Dieudonné et al. (ACM Trans Algorithms 11(1):1, 2014). Two or more mobile agents start from nodes of a network and have to accomplish the task of gathering which consists in getting all together at the same node at the same time. An adversary chooses the initial nodes of the agents and assigns a different positive integer (called label) to each of them. Initially, each agent knows its label but does not know the labels of the other agents or their positions relative to its own. Agents move in synchronous rounds and can communicate with each other only when located at the same node. Up tofof the agents are Byzantine. A Byzantine agent can choose an arbitrary port when it moves, can convey arbitrary information to other agents and can change its label in every round, in particular by forging the label of another agent or by creating a completely new one.What is the minimum numberof good agents that guarantees deterministic gathering of all of them, with termination?We provide exact answers to this open problem by considering the case when the agents initially know the size of the network and the case when they do not. In the former case, we provewhile in the latter, we prove. More precisely, for networks of known size, we design a deterministic algorithm gathering all good agents in any network provided that the number of good agents is at least. For networks of unknown size, we also design a deterministic algorithm ensuring the gathering of all good agents in any network but provided that the number of good agents is at least. Both of our algorithms are optimal in terms of required number of good agents, as each of them perfectly matches the respective lower bound onshown in Dieudonné et al. (2014), which is ofwhen the size of the network is known and ofwhen it is unknown. Perhaps surprisingly, our results highlight an interesting feature when put in perspective with known results concerning a relaxed variant of this problem in which the Byzantine agents cannot change their initial labels. Indeed under this variantfor networks of known size andfor networks of unknown size. Following this perspective, it turns out that when the size of the network is known, the ability for the Byzantine agents to change their labels significantly impacts the value of. However, the relevance forof such an ability completely disappears in the most general case where the size of the network is unknown, asregardless of whether Byzantine agents can change their labels or not.
容错和自稳定移动机器人聚集。
DOI：
--
发表时间：
2006
期刊：
Proc. 20th Int. Symp. Distributed Computing LNCS 4167
影响因子：
--
作者：
X.Defago;M.Gradinariu;S.Messika;P.Raipin
通讯作者：
P.Raipin
循环图和过滤的半 Gorenstein 环
DOI：
--
发表时间：
2022
期刊：
影响因子：
--
作者：
Mitsuhiro Miyazaki;Katsuyuki Naoi;宮崎充弘
通讯作者：
宮崎充弘
DOI：
--
发表时间：
2008
期刊：
影响因子：
--
作者：
N.Inuzuka;Y.Tomida;T.Izumi;Y.Katayama;K.Wada
通讯作者：
K.Wada