We consider the problem of fault-tolerant parallel search on an infinite line by $n$ robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed $1$ and can communicate wirelessly among themselves. However, among the $n$ robots, there are $f$ robots that exhibit byzantine faults. A faulty robot can fail to report the target even after reaching it, or it can make malicious claims about having found the target when in fact it has not. Given the presence of such faulty robots, the search for the target can only be concluded when the non-faulty robots have sufficient evidence that the target has been found. We aim to design algorithms that minimize the value of $S_{d} (n, f)$ , the time to find a target at a (unknown) distance $d$ from the origin by $n$ robots among which $f$ are faulty. We give several different algorithms whose running time depends on the ratio $f / n$ , the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.

This is an extended and revised version of a paper which appeared in the proceedings of ISAAC 2016, December 12-14, 2016, Sydney, Australia.

Communicated by Marek Chrobak

Keywords:

References

1. N. Agmon and D. Peleg, Fault-tolerant gathering algorithms for autonomous mobile robots, SIAM J. Comput. 36(1) (2006) 56–82. Crossref, Web of Science, Google Scholar
2. S. Albers and M. R. Henzinger, Exploring unknown environments, SIAM J. Comput. 29(4) (2000) 1164–1188. Crossref, Web of Science, Google Scholar
3. S. Albers, K. Kursawe and S. Schuierer, Exploring unknown environments with obstacles, Algorithmica 32(1) (2002) 123–143. Crossref, Web of Science, Google Scholar
4. S. Alpern and S. Gal, The Theory of Search Games and Rendezvous, Vol. 55 (Kluwer Academic Publishers, 2002). Google Scholar
5. R. Baeza Yates, J. Culberson and G. Rawlins, Searching in the plane, Inform. Comput. 106(2) (1993) 234–252. Crossref, Web of Science, Google Scholar
6. E. Bampas, J. Czyzowicz, L. Gasieniec, D. Ilcinkas, R. Klasing, T. Kociumaka and D. Pajak, Linear search by a pair of distinct-speed robots, In SIROCCO. to appear, 2016. Google Scholar
7. A. Beck, On the linear search problem, Israel Journal of Mathematics 2(4) (1964) 221–228. Crossref, Web of Science, Google Scholar
8. A. Beck, More on the linear search problem, Israel Journal of Mathematics 3(2) (1965) 61–70. Crossref, Web of Science, Google Scholar
9. A. Beck and M. Beck, Son of the linear search problem, Israel Journal of Mathematics 48(2-3) (1984) 109–122. Crossref, Web of Science, Google Scholar
10. A. Beck and D. Newman, Yet more on the linear search problem, Israel Journal of Mathematics 8(4) (1970) 419–429. Crossref, Web of Science, Google Scholar
11. A. Beck and P. Warren, The return of the linear search problem, Israel Journal of Mathematics 14(2) (1973) 169–183. Crossref, Web of Science, Google Scholar
12. R. Bellman, An optimal search, SIAM Review 5(3) (1963) 274–274. Crossref, Google Scholar
13. P. Bose and J.-L. De Carufel, A general framework for searching on a line, In WALCOM: Algorithms and Computation — 10th International Workshop, WALCOM 2016, Kathmandu, Nepal, March 29-31, 2016, Proceedings (2016), pp. 143–153. Crossref, Google Scholar
14. P. Bose, J.-L. De Carufel and S. Durocher, Revisiting the problem of searching on a line, In Algorithms - ESA 2013 - 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings (2013), pp. 205–216. Crossref, Google Scholar
15. A. Casteigts, P. Flocchini, W. Quattrociocchi and N. Santoro, Time-varying graphs and dynamic networks, In Ad-hoc, Mobile, and Wireless Networks, LNCS, Vol. 6811 (Springer, 2011), pp. 346–359. Crossref, Google Scholar
16. Marek Chrobak, Leszek Gasieniec, Thomas Gorry and Russell Martin, Group search on the line, In International Conference on Current Trends in Theory and Practice of Informatics (SOFSEM) (Springer, 2015), pp. 164–176. Google Scholar
17. R. Cohen and D. Peleg, Convergence properties of the gravitational algorithm in asynchronous robot systems, SIAM J. Comput. 41(1) (2005) 1516–1528. Crossref, Web of Science, Google Scholar
18. J. Czyzowicz, L. Gasieniec, A. Kosowski, E. Kranakis, D. Krizanc and N. Taleb, When patrolmen become corrupted: Monitoring a graph using faulty mobile robots, In Algorithms and Computation - Proceedings of 26th International Symposium, ISAAC 2015 (2015), pp. 343–354. Crossref, Google Scholar
19. Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan and Jaroslav Opatrny, Search on a line with faulty robots, In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing (ACM, 2016), pp. 405–414. Crossref, Google Scholar
20. E. D. Demaine, S. P. Fekete and S. Gal, Online searching with turn cost, Theor. Comput. Sci. 361(2) (2006) 342–355. Crossref, Web of Science, Google Scholar
21. X. Deng, T. Kameda and C. Papadimitriou, How to learn an unknown environment, In FOCS (IEEE, 1991), pp. 298–303. Crossref, Google Scholar
22. Y. Dieudonné, A. Pelc and D. Peleg, Gathering despite mischief, ACM Transactions on Algorithms (TALG) 11(1) (2014) 1. Crossref, Web of Science, Google Scholar
23. F. V. Fomin and D. M. Thilikos, An annotated bibliography on guaranteed graph searching, Theoretical Computer Science 399(3) (2008) 236–245. Crossref, Web of Science, Google Scholar
24. F. Hoffmann, C. Icking, R. Klein and K. Kriegel, The polygon exploration problem, SIAM J. Comput. 31(2) (2001) 577–600. Crossref, Web of Science, Google Scholar
25. J. Hromkovič, R. Klasing, B. Monien and R. Peine, Dissemination of information in interconnection networks (broadcasting & gossiping), In Combinatorial Network Theory (Springer, 1996), pp. 125–212. Crossref, Google Scholar
26. J. Kleinberg, On-line search in a simple polygon, In SODA (SIAM, 1994), p. 8. Google Scholar
27. F. Kuhn, N. Lynch and R. Oshman, Distributed computation in dynamic networks, In Proceedings of the Forty-Second ACM Symposium on Theory of Computing (ACM, 2010), pp. 513–522. Crossref, Google Scholar
28. Andrey Kupavskii and Emo Welzl, Lower bounds for searching robots, some faulty, In Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing (ACM, 2018), pp. 447–453. Crossref, Google Scholar
29. L. Lamport, R. Shostak and M. Pease, The byzantine generals problem, ACM Transactions on Programming Languages and Systems (TOPLAS) 4(3) (1982) 382–401. Crossref, Web of Science, Google Scholar
30. N. A. Lynch, Distributed Algorithms (Morgan Kaufmann, 1996). Google Scholar
31. C. H. Papadimitriou and M. Yannakakis, Shortest paths without a map, In ICALP (Springer, 1989), pp. 610–620. Crossref, Google Scholar
32. S. Souissi, X. Défago and M. Yamashita, Gathering asynchronous mobile robots with inaccurate compasses, Principles of Distributed Systems (2006) 333–349. Google Scholar