20160725
Search on a line with faulty robots
Publication
Publication
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 n ≥ 2f + 2, there is a simple algorithm with competitive ratio 1. For f < n < 2f + 2 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 (equition presented) Setting a = n/f as a constant, the asymptotic competitive ratio is (4/a)2/a (4/a  2)12/a + 1. Our search algorithm is easily seen to be optimal for the case n = f + 1. We also show that as n tends to ∞ the competitive ratio of our algorithm for the case n = 2f + 1 approaches 3 and this is optimal. More precisely, we show that asymptotically, the competitive ratio of our proportional schedule algorithm A(2f + 1, f) is at most 3+ 4 lnn/n , while any search algorithm has a lower bound 3 + 2 lnn/ n on its competitive ratio.
Additional Metadata  

Keywords  Competitive ratio, Cowpath problem, Faulty robots, Search on a line 
Persistent URL  dx.doi.org/10.1145/2933057.2933102 
Conference  35th ACM Symposium on Principles of Distributed Computing, PODC 2016 
Citation 
Czyzowicz, J. (Jurek), Kranakis, E, Krizanc, D. (Danny), Narayanan, L. (Lata), & Opatrny, J. (Jaroslav). (2016). Search on a line with faulty robots. Presented at the 35th ACM Symposium on Principles of Distributed Computing, PODC 2016. doi:10.1145/2933057.2933102
