Byzantine-Resilient Convergence in Oblivious Robot Networks
Byzantine-Resilient Convergence in Oblivious Robot Networks
复制标题
遗忘机器人网络中的拜占庭弹性融合
DOI：
10.1007/978-3-540-92295-7_33
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
Z. Bouzid;M. Potop;S. Tixeuil
给定一组机器人具有任意初始位置且在全局坐标系上没有一致，收敛要求所有机器人渐近接近完全相同的但事先未知的位置。机器人是健忘的--它们不会回忆过去的计算--它们被允许在一维空间中移动。此外，机器人不能直接通信，它们只能通过传感器获得与系统相关的信息。我们证明了([4])移动机器人收敛的充要条件，尽管它们的子集是拜占庭的(即它们可以表现出任意的行为)。此外，我们还提出了一种机器人网络的确定性收敛算法，并分析了其在不同同步设置下的正确性和复杂性。该算法支持完全同步网络中(2f+ 1)规模的拜占庭机器人、半同步网络中(3f+ 1)规模的拜占庭机器人和异步网络中(4f+ 1)规模的拜占庭机器人。原子模型的边界对于谨慎算法来说是最优的，这类算法保证正确的机器人总是在正确的机器人的位置范围内移动。
Given a set of robots with arbitrary initial location and no agreement on a global coordinate system,convergencerequires that all robots asymptotically approach the exact same, but unknown beforehand, location. Robots are oblivious— they do not recall the past computations — and are allowed to move in a one-dimensional space. Additionally, robots cannot communicate directly, instead they obtain system related information onlyviavisual sensors. We prove ([4]) necessary and sufficient conditions for the convergence of mobile robots despite a subset of them being Byzantine (i.e.they can exhibit arbitrary behavior). Additionally, we propose a deterministic convergence algorithm for robot networks and analyze its correctness and complexity in various synchrony settings. The proposed algorithm toleratesfByzantine robots for (2f+ 1)-sized robot networks in fully synchronous networks, (3f+ 1)-sized in semi-synchronous networks and (4f+ 1)-sized in asynchronous networks. The bounds obtained for the ATOM model are optimal for the class ofcautiousalgorithms, which guarantee that correct robots always move inside the range of positions of the correct robots.