Distributed Pattern Formation With Faulty Robots
share
Pattern formation is one of the most fundamental problems in distributed computing, which has recently received much attention. In this paper, we initiate the study of distributed pattern formation in situations when some robots can be faulty. In particular, we consider the usual and challenging look-compute-move model with oblivious, anonymous robots. We first present lower bounds and show that any deterministic algorithm takes at least two parallel rounds to form simple patterns in the presence of faulty robots. We then present distributed algorithms for our problem which match this bound, for conic sections: in two parallel rounds, robots form lines, circles, parabola, and ellipses while tolerating f=2, f=3, f=4, and f=5 faults, respectively. We show that the resulting pattern includes the f faulty robots in the pattern of n robots, where n ≥ 2f+1, and that f < n < 2f+1 robots cannot form such patterns. We conclude by discussing several relaxations and extensions.
READ FULL TEXT