论文标题
尽管有线性数量弱的拜占庭式代理，但仍在聚集
Gathering despite a linear number of weakly Byzantine agents
论文作者
论文摘要
我们研究收集问题，以使最初散布在任意网络中的多个代理聚集在一个节点上。网络中存在具有唯一标识符（ID）的$ K $代理，其中$ f $是弱拜占庭代理，除了伪造其ID外，其行为是任意的。代理人在同步回合中行为，每个节点都没有任何记忆，例如白板。在文献中，存在一种聚集算法，可容忍任何数量的拜占庭代理，而最快的聚集算法则需要$ω（f^2）$ non-bybyzantine代理。本文提出了一种用$ω（f）$ non-byzantine代理有效地解决收集问题的算法，因为在先前的工作中，非拜津丁剂的数量之间存在很大的差距。所提出的算法在$ o中获得聚会（f \ cdot |λ_{good} | \ cdot x（n））$ rounds如果$ 9F+8 \ 8 \ 8 \ leq k $，并且同时启动$ n $，如果$ n $给予了$ |λ_{好}的$ ran-iad $ lar-y-y-y-y-y-y-y-y-y-y-y-y-y-y-iad and-y-y-y-y-iad and-y-y-y-y-y-y-y-y-y-y-y-y-y-y-y-iad）xine xine and xine xine（探索由$ n $节点组成的任何网络所需的回合。该算法比现有算法最容易多，如果给定给代理的$ n $，同时终止和启动延迟的保证并不相同，那么如果给代理的算法，则需要的非byzantine代理比最快的算法更少。为了实现此属性，我们提出了一种新技术，以模拟代理系统上同步消息系统的拜占庭共识算法。
We study the gathering problem to make multiple agents initially scattered in arbitrary networks gather at a single node. There exist $k$ agents with unique identifiers (IDs) in the network, and $f$ of them are weakly Byzantine agents, which behave arbitrarily except for falsifying their IDs. The agents behave in synchronous rounds, and each node does not have any memory like a whiteboard. In the literature, there exists a gathering algorithm that tolerates any number of Byzantine agents, while the fastest gathering algorithm requires $Ω(f^2)$ non-Byzantine agents. This paper proposes an algorithm that solves the gathering problem efficiently with $Ω(f)$ non-Byzantine agents since there is a large gap between the number of non-Byzantine agents in previous works. The proposed algorithm achieves the gathering in $O(f\cdot|Λ_{good}|\cdot X(N))$ rounds in case of $9f+8\leq k$ and simultaneous startup if $N$ is given to agents, where $|Λ_{good}|$ is the length of the largest ID among non-Byzantine agents, and $X(n)$ is the number of rounds required to explore any network composed of $n$ nodes. This algorithm is faster than the most fault-tolerant existing algorithm and requires fewer non-Byzantine agents than the fastest algorithm if $n$ is given to agents, although the guarantees on simultaneous termination and startup delay are not the same. To achieve this property, we propose a new technique to simulate a Byzantine consensus algorithm for synchronous message-passing systems on agent systems.
