Optimal Byzantine-resilient convergence in uni-dimensional robot networks
Optimal Byzantine-resilient convergence in uni-dimensional robot networks
复制标题
一维机器人网络中的最佳拜占庭弹性收敛
DOI：
10.1016/j.tcs.2010.05.006
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S. Tixeuil
中科院分区：
文献类型：
--
作者：
Z. Bouzid;M. Potop;S. Tixeuil
给定一组具有任意初始位置且在全局坐标系上没有一致的机器人，收敛要求所有机器人渐进地逼近完全相同的但事先未知的位置。机器人是健忘的--它们不会回忆过去的计算--它们被允许在一维空间中移动。此外，机器人不能直接通信，它们只能通过视觉传感器获得与系统相关的信息。尽管收敛和经典的分布式近似一致问题(需要正确的过程来确定，对于某些常数ϵ，距离ϵ相隔并且在初始建议的值的范围内)是相似的，我们提供了证据，证明在机器人网络中解决收敛需要关于同步和拜占庭弹性的特定假设。更详细地，我们证明了移动机器人收敛的充要条件，尽管它们的子集是拜占庭的(即它们可以表现出任意的行为)。此外，我们还提出了两种机器人网络确定性收敛算法，并分析了它们在不同原子性和同步性设置下的正确性和复杂性。第一个算法容忍完全同步原子网络中(2f+1)个机器人网络的f个拜占庭机器人，第二个算法容忍非原子Corda网络中(3f+1)个机器人网络的f个拜占庭机器人。证明了这两种算法的抗攻击能力是最优的。
Given a set of robots with arbitrary initial location and no agreement on a global coordinate system, convergence requires 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 only via visual sensors. Even though convergence and the classical distributed approximate agreement problem (that requires correct processes to decide, for some constant ϵ, values distance ϵ apart and within the range of initial proposed values) are similar, we provide evidence that solving convergence in robot networks requires specific assumptions about synchrony and Byzantine resilience. In more detail, we prove 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 two deterministic convergence algorithms for robot networks and analyze their correctness and complexity in various atomicity and synchrony settings. The first algorithm tolerates f Byzantine robots for (2f+1)-sized robot networks in fully synchronous ATOM networks, while the second proposed algorithm tolerates f Byzantine robots for (3f+1)-sized robot networks in non-atomic CORDA networks. The resilience of these two algorithms is proved to be optimal.
容错和自稳定移动机器人聚集。
DOI：
--
发表时间：
2006
期刊：
Proc. 20th Int. Symp. Distributed Computing LNCS 4167
影响因子：
--
作者：
X.Defago;M.Gradinariu;S.Messika;P.Raipin
通讯作者：
P.Raipin