We consider the problem of fault-tolerant parallel search on an infinite line by @math robots. Starting from the origin, the robots are required to find a target at an unknown location. The robots can move with maximum speed @math and can communicate in wireless mode among themselves. However, among the @math robots, there are @math 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 verification that the target has been found. We aim to design algorithms that minimize the value of @math , the time to find a target at a distance @math from the origin by @math robots among which @math are faulty. We give several different algorithms whose running time depends on the ratio @math , the density of faulty robots, and also prove lower bounds. Our algorithms are optimal for some densities of faulty robots.
A search problem is usually seen as localization of a hidden target using searchers capable to move in the environment. It is an optimization question, usually attempting to minimize the time needed to complete the search. The question has been studied in numerous variations involving static or moving targets, one or many searchers, known or unknown environment, synchronous or asynchronous settings, different speed agents and many others (cf. @cite_10 ).
@cite_10
2106518318
Graph searching encompasses a wide variety of combinatorial problems related to the problem of capturing a fugitive residing in a graph using the minimum number of searchers. In this annotated bibliography, we give an elementary classification of problems and results related to graph searching and provide a source of bibliographical references on this field.