论文标题
在弱拜占庭环境中与一个强大的团队聚会
Gathering with a strong team in weakly Byzantine environments
论文作者
论文摘要
我们研究了需要一个移动代理团队在任意网络中单个节点聚集的聚会问题。该团队由具有唯一标识符（IDS）的$ K $代理组成，其中$ f $是微弱的拜占庭特工，除了伪造其标识符外，其行为是任意的。代理商同步弹移动，不能留下有关节点的任何信息。如果给代理的节点$ n $的数量，则现有的最快算法忍受了任何数量的弱拜占庭代理，并同时终止$ O（n^4 \ cdot | cdot |λ_{good} {good} | \ cdot x（n））$ |λ_| em |λ_| $ emantiine and iD-iad是and | nistiine | nistine | good-lenge and iS | $ x（n）$是探索由$ n $节点组成的任何网络所需的回合数。在本文中，我们询问一个问题，即如果我们有一个强大的团队，即拥有少数拜占庭特工的团队，我们是否可以减少时间复杂性，因为在实践中没有那么多代理商会遭受过错。我们通过提出两种算法在至少$ 4F^2+9f+4 $ 4 $代理的情况下提出两种算法来给出一个积极的答案。两种算法都将$ n $的上限$ n $作为输入。第一个算法以$ o（（（f+|λ_{good} |）\ cdot x（n））$ roughs中的非同时终止，以非同时终止的方式进行聚集。第二个算法在$ o中同时终止进行聚集，（（（f+|λ_{all} |）\ cdot x（n））$ rounds，其中$ |λ_{ash ash ash ash ash as y是所有代理的最大ID的长度。如果将$ n $给出给代理商，而$ |λ_{all} | = o（|λ_{good} |）$ holds，则第二算法大大降低了时间复杂性。
We study the gathering problem requiring a team of mobile agents to gather at a single node in arbitrary networks. The team consists of $k$ agents with unique identifiers (IDs), and $f$ of them are weakly Byzantine agents, which behave arbitrarily except falsifying their identifiers. The agents move in synchronous rounds and cannot leave any information on nodes. If the number of nodes $n$ is given to agents, the existing fastest algorithm tolerates any number of weakly Byzantine agents and achieves gathering with simultaneous termination in $O(n^4\cdot|Λ_{good}|\cdot X(n))$ rounds, where $|Λ_{good}|$ is the length of the maximum ID of non-Byzantine agents and $X(n)$ is the number of rounds required to explore any network composed of $n$ nodes. In this paper, we ask the question of whether we can reduce the time complexity if we have a strong team, i.e., a team with a few Byzantine agents, because not so many agents are subject to faults in practice. We give a positive answer to this question by proposing two algorithms in the case where at least $4f^2+9f+4$ agents exist. Both the algorithms take the upper bound $N$ of $n$ as input. The first algorithm achieves gathering with non-simultaneous termination in $O((f+|Λ_{good}|)\cdot X(N))$ rounds. The second algorithm achieves gathering with simultaneous termination in $O((f+|Λ_{all}|)\cdot X(N))$ rounds, where $|Λ_{all}|$ is the length of the maximum ID of all agents. The second algorithm significantly reduces the time complexity compared to the existing one if $n$ is given to agents and $|Λ_{all}|=O(|Λ_{good}|)$ holds.
