Fault-Tolerant Gathering of Mobile Robots with Weak Multiplicity Detection

摘要

There has been a wide interest in designing distributed algorithms for tiny robots. In particular, it has been shown that the robots can complete certain tasks even in the presence of faulty robots. In this paper, we focus on gathering of all non-faulty robots at a single point in presence of faulty robots. We propose a wait-free algorithm (i.e., no robot waits for other robots and algorithm instructs each robot to move in every step, unless it is already at the gathering location), that gathers all non-faulty robots in the semi-synchronous model without any agreement about the coordinate system and with weak multiplicity detection (i.e., a robot can detect if there are more than one robots at a point, but not their exact number) in the presence of at most n - 1 faulty robots for n ≥ 3. We show that the required capability for gathering robots is minimal in the above model, since relaxing it further makes gathering impossible to solve.