论文标题
快速拜占庭聚集，图表中具有可见性
Fast Byzantine Gathering with Visibility in Graphs
论文作者
论文摘要
我们考虑了$ n $节点图中的$ M $同步移动机器人团队的收集任务。每个机器人都有一个标识符（ID），并运行其自己的确定性算法，即没有集中式协调员。我们认为一个特别具有挑战性的情况：团队中有$ f $ byzantine机器人可以任意行为，甚至可以随时将其ID更改为任何值。除了观察奇怪或意外的行为之外，没有办法将这些机器人与非故障机器人区分开。收集任务的目的是最终在同一一轮的同一节点上所有非故障机器人。众所周知，除非团队中至少有$ f+1 $非可损坏的机器人，否则没有算法可以解决此任务。在本文中，我们设计了一种在多项式时间内运行的算法，相对于$ n $和$ m $，它与此键相匹配的算法，即它在具有$ f+1 $ $ nonfaulty机器人的团队中起作用。在我们的模型中，我们为机器人配备了传感器，使每个机器人能够在其当前节点的一定距离内查看子图（包括机器人）。我们证明，如果此可见性范围$ h $至少是图表的半径，则可以解决收集任务，如果$ h $是任何固定常数，则无法解决。
We consider the gathering task by a team of $m$ synchronous mobile robots in a graph of $n$ nodes. Each robot has an identifier (ID) and runs its own deterministic algorithm, i.e., there is no centralized coordinator. We consider a particularly challenging scenario: there are $f$ Byzantine robots in the team that can behave arbitrarily, and even have the ability to change their IDs to any value at any time. There is no way to distinguish these robots from non-faulty robots, other than perhaps observing strange or unexpected behaviour. The goal of the gathering task is to eventually have all non-faulty robots located at the same node in the same round. It is known that no algorithm can solve this task unless there at least $f+1$ non-faulty robots in the team. In this paper, we design an algorithm that runs in polynomial time with respect to $n$ and $m$ that matches this bound, i.e., it works in a team that has exactly $f+1$ non-faulty robots. In our model, we have equipped the robots with sensors that enable each robot to see the subgraph (including robots) within some distance $H$ of its current node. We prove that the gathering task is solvable if this visibility range $H$ is at least the radius of the graph, and not solvable if $H$ is any fixed constant.
