Byzantine Resilience at Swarm Scale: A Decentralized Blocklist Protocol from Inter-robot Accusations
Byzantine Resilience at Swarm Scale: A Decentralized Blocklist Protocol from Inter-robot Accusations
复制标题
DOI：
10.48550/arxiv.2301.06977
复制
发表时间：
2023-01
期刊：
影响因子：
--
通讯作者：
Kacper Wardega;Max von Hippel;Roberto Tron;C. Nita-Rotaru;Wenchao Li
中科院分区：
文献类型：
--
作者：
Kacper Wardega;Max von Hippel;Roberto Tron;C. Nita-Rotaru;Wenchao Li
W-MSR算法是分散式多机器人系统Byzantine弹性设计的最新方法，它基于线性一致协议（LCP）中的离群值丢弃。虽然W-MSR提供了很好理解的理论保证，将强大的网络连接与底层共识的收敛联系起来，但该方法存在一些限制，无法大规模使用：（1）要容忍的拜占庭机器人的数量F应该是先验已知的，（2）每个机器人维护2F+1个邻居的要求对于大F是不切实际的，（3）信息传播受到F+1机器人独立地对共识属性进行局部测量以改变群决策的要求的阻碍，以及（4）W-MSR是特定于LCP的，并且不能推广到不在LCP上实现的应用。在这项工作中，我们提出了一个分散的块列表协议（DBP）的基础上，机器人之间的指控。指控是基于对不当行为的本地观察而做出的，一旦被整个网络中的合作机器人共享，就被用作计算阻止列表的图匹配算法的输入。DBP推广到不通过LCP实现的应用程序，是自适应的拜占庭机器人的数量，并允许通过多机器人系统的快速信息传播，同时减少所需的网络连接相对于W-MSR。在LCP类型的应用中，DBP减少了W-MSR的最坏情况下的连接要求从（2F+1）-连接到（F+1）-连接和传播新信息所需的合作观察者的数量从F+1到只有1个观察者。我们的经验表明，我们的方法拜占庭弹性规模数百机器人的合作目标跟踪，时间同步和本地化的案例研究。
The Weighted-Mean Subsequence Reduced (W-MSR) algorithm, the state-of-the-art method for Byzantine-resilient design of decentralized multi-robot systems, is based on discarding outliers received over Linear Consensus Protocol (LCP). Although W-MSR provides well-understood theoretical guarantees relating robust network connectivity to the convergence of the underlying consensus, the method comes with several limitations preventing its use at scale: (1) the number of Byzantine robots, F, to tolerate should be known a priori, (2) the requirement that each robot maintains 2F+1 neighbors is impractical for large F, (3) information propagation is hindered by the requirement that F+1 robots independently make local measurements of the consensus property in order for the swarm's decision to change, and (4) W-MSR is specific to LCP and does not generalize to applications not implemented over LCP. In this work, we propose a Decentralized Blocklist Protocol (DBP) based on inter-robot accusations. Accusations are made on the basis of locally-made observations of misbehavior, and once shared by cooperative robots across the network are used as input to a graph matching algorithm that computes a blocklist. DBP generalizes to applications not implemented via LCP, is adaptive to the number of Byzantine robots, and allows for fast information propagation through the multi-robot system while simultaneously reducing the required network connectivity relative to W-MSR. On LCP-type applications, DBP reduces the worst-case connectivity requirement of W-MSR from (2F+1)-connected to (F+1)-connected and the number of cooperative observers required to propagate new information from F+1 to just 1 observer. We demonstrate empirically that our approach to Byzantine resilience scales to hundreds of robots on cooperative target tracking, time synchronization, and localization case studies.