Fault-tolerant Gathering of Semi-synchronous Robots

Abstract

This paper addresses the Gathering problem which asks robots to gather at a single point which is not fixed in advance, for a set of small, autonomous, mobile robots. The problem is studied for a set of semi-synchronous robots under SSY NC model when the robots may become faulty (crash fault). Depending upon the capabilities of the robots, the algorithms are designed to tolerate maximum number of faults. This work assumes weak multiplicity detection capability of the robots. The contribution of this work is in two folds. First, a distributed algorithm is presented which can tolerate at most (⌊n/2 - 1⌋) crash faults for n ≥ 7 robots with weak multiplicity detection only. For the second algorithm, it is also assumed that robots know the mobility capacity of all the robots. The algorithm presented here can tolerate at most (n - 6) crash faults for n ≥ 7 robots.