Overcoming Probabilistic Faults in Disoriented Linear Search

Abstract

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\in (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\rightarrow 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\le 0.390388$. When $p\rightarrow 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\in (0,1/2)$, for which we provide three algorithms of different advantages, all with a bounded competitive ratio even as $p\rightarrow 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\sqrt{p(1-p)}$, with arbitrarily high concentration.

Research supported in part by NSERC, and by the Fields Institute for Research in Mathematical Sciences

Extended Abstract—The full version of this paper appears on arXiv [17].