Overcoming Probabilistic Faults in Disoriented Linear Search

We consider search by mobile agents for a hidden, idle target, placed on the infinite line. Feasible solutions are agent trajectories in which all agents reach the target sooner or later. A special feature of our problem is that the agents are p-faulty, meaning that every attempt to change direction is an independent Bernoulli trial with known probability p, where p is the probability that a turn fails. We are looking for agent trajectories that minimize the worst-case expected termination time, relative to the distance of the hidden target to the origin (competitive analysis). Hence, searching with one 0-faulty agent is the celebrated linear search (cow-path) problem that admits optimal 9 and 4.59112 competitive ratios, with deterministic and randomized algorithms, respectively. First, we study linear search with one deterministic p-faulty agent, i.e., with no access to random oracles, p is an element of(0, 1/2). For this problem, we provide trajectories that leverage the probabilistic faults into an algorithmic advantage. Our strongest result pertains to a search algorithm (deterministic, aside from the adversarial probabilistic faults) which, as p -> 0, has optimal performance 4.59112+ epsilon, up to the additive term epsilon that can be arbitrarily small. Additionally, it has performance less than 9 for p <= 0.390388. When p -> 1/2, our algorithm has performance Theta(1/(1 - 2p)), which we also show is optimal up to a constant factor. Second, we consider linear search with two p-faulty agents, p is an element of (0, 1/2), for which we provide three algorithms of different advantages, all with a bounded competitive ratio even as p -> 1/2. Indeed, for this problem, we show how the agents can simulate the trajectory of any 0-faulty agent (deterministic or randomized), independently of the underlying communication model. As a result, searching with two agents allows for a solution with a competitive ratio of 9 + epsilon (which we show can be achieved with arbitrarily high concentration) or a competitive ratio of 4.59112+ epsilon. Our final contribution is a novel algorithm for searching with two p-faulty agents that achieves a competitive ratio 3+ 4 root p(1 - p), with arbitrarily high concentration.