期刊名称：International Journal of Networking and Computing
印刷版ISSN：2185-2847
出版年度：2018
卷号：8
期号：1
页码：32-52
语种：English
出版社：International Journal of Networking and Computing
摘要：We consider the distributed setting of N autonomous?mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other robots using colored lights (the robots with lights model). We study the fundamental Complete Visibility problem of repositioning N robots on a plane so that each robot is visible to all others. We assume obstructed visibility under which a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. We are interested in fault-tolerant algorithms; all existing algorithms for this problem are not fault-tolerant (except handling some special cases). We study fault-tolerance with respect to failures on the mobility of robots. Therefore, any algorithm for Complete Visibility is required to provide visibility between all non-faulty robots, independently of the behavior of the faulty ones. We model mobility failures as crash faults in which each faulty robot is allowed to stop its movement at any time and, once the faulty robot stopped moving, that robot will remain stationary indefinitely. In this paper, we present and analyze an algorithm that solves Complete Visibility tolerating one crash-faulty robot in a system of N>=3 robots, starting from any arbitrary initial configuration. We also provide an impossibility result on solving Complete Visibility if a single robot is Byzantine-faulty in a system of N=3 robots; in the Byzantine fault model, a faulty robot might behave in an unpredictable, arbitrary, and unforeseeable ways. Furthermore, we discuss how to solve Complete Visibility for some initial configurations of robots (which we call feasible initial configurations) in the crash fault model, where two robots are (crash) faulty.
其他摘要：We consider the distributed setting of N autonomous?mobile robots that operate in Look-Compute-Move (LCM) cycles and communicate with other robots using colored lights (the robots with lights model). We study the fundamental Complete Visibility problem of repositioning N robots on a plane so that each robot is visible to all others. We assume obstructed visibility under which a robot cannot see another robot if a third robot is positioned between them on the straight line connecting them. We are interested in fault-tolerant algorithms; all existing algorithms for this problem are not fault-tolerant (except handling some special cases). We study fault-tolerance with respect to failures on the mobility of robots. Therefore, any algorithm for Complete Visibility is required to provide visibility between all non-faulty robots, independently of the behavior of the faulty ones. We model mobility failures as crash faults in which each faulty robot is allowed to stop its movement at any time and, once the faulty robot stopped moving, that robot will remain stationary indefinitely. In this paper, we present and analyze an algorithm that solves Complete Visibility tolerating one crash-faulty robot in a system of N>=3 robots, starting from any arbitrary initial configuration. We also provide an impossibility result on solving Complete Visibility if a single robot is Byzantine-faulty in a system of N=3 robots; in the Byzantine fault model, a faulty robot might behave in an unpredictable, arbitrary, and unforeseeable ways. Furthermore, we discuss how to solve Complete Visibility for some initial configurations of robots (which we call feasible initial configurations) in the crash fault model, where two robots are (crash) faulty.
