Improving the Optimal Bounds for Black Hole Search in Rings

摘要

In this paper we re-examine the well known problem of asynchronous black hole search in a ring. It is well known that at least 2 agents are needed and the total number of agents' moves is at least Ω(n log n); solutions indeed exist that allow a team of two agents to locate the black hole with the asymptotically optimal cost of Θ(n log n) moves. In this paper we first of all determine the exact move complexity of black hole search in an asynchronous ring. In fact, we prove that 3n log_3 n - O(n) moves are necessary. We then present a novel algorithm that allows two agents to locate the black hole with at most 3n log_3 n + O(n) moves, improving the existing upper bounds, and matching the lower bound up to the constant of proportionality. Finally we show how to modify the protocol so to achieve asymptotically optimal time complexity Θ(n), still with 3n log_3 n + O(n) moves; this improves upon all existing time-optimal protocols, which require O(n~2) moves. This protocol is the first that is optimal with respect to all three complexity measures: size (number of agents), cost (number of moves) and time; in particular, its cost and size complexities match the lower bounds up to the constant.