Optimal Byzantine-resilient Convergence in Unidimensional Robot Networks
Résumé
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. %X Even though convergence and the classical distributed approximate agreement problem (that requires correct processes to decide, for some constant epsilon, values distance epsilon 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. %X In more details, 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.