Overcoming Probabilistic Faults in Disoriented Linear Search
share
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 competitive analysis. First, we study linear search with one deterministic p-faulty agent, i.e., with no access to random oracles, p∈ (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+ϵ, up to the additive term ϵ that can be arbitrarily small. Additionally, it has performance less than 9 for p≤ 0.390388. When p→ 1/2, our algorithm has performance Θ(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∈ (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+ϵ, or a competitive ratio of 4.59112+ϵ. Our final contribution is a novel algorithm for searching with two p-faulty agents that achieves a competitive ratio 3+4√(p(1-p)).
READ FULL TEXT