Search on a line with faulty robots
We consider the problem of searching on a line using n mobile robots, of which at most f are faulty, and the remaining are reliable. The robots start at the same location and move in parallel along the line with the same speed. There is a target placed on the line at a location unknown to the robots. Reliable robots can find the target when they reach its location, but faulty robots cannot detect the target. Our goal is to design a parallel algorithm minimizing the competitive ratio, represented by the worst case ratio between the time of arrival of the first reliable robot at the target, and the distance from the source to the target. If (Formula presented.), there is a simple algorithm with a competitive ratio of 1. For (Formula presented.) we develop a new class of algorithms, called proportional schedule algorithms. For any given (n, f), we give a proportional schedule algorithm A(n, f), whose competitive ratio is (Formula presented.)Setting (Formula presented.) as a constant, the asymptotic competitive ratio is (Formula presented.). Our search algorithm is easily seen to be optimal for the case (Formula presented.). We also show that as n tends to (Formula presented.) the competitive ratio of our algorithm for the case (Formula presented.) approaches 3 and this is optimal. More precisely, we show that asymptotically (after excluding small order terms), the competitive ratio of our proportional schedule algorithm (Formula presented.) is at most (Formula presented.), while any search algorithm has a lower bound (Formula presented.) on its competitive ratio.
|Keywords||Competitive ratio, Cow-path problem, Faulty robots, Search on a line|
Czyzowicz, J. (Jurek), Kranakis, E, Krizanc, D. (Danny), Narayanan, L. (Lata), & Opatrny, J. (Jaroslav). (2017). Search on a line with faulty robots. Distributed Computing, 1–12. doi:10.1007/s00446-017-0296-0