Time Optimal Algorithms for Black Hole Search in Rings

Time Optimal Algorithms for Black Hole Search in Rings,10.1007/978-3-642-17461-2_5,Balasingham Balamohan,Paola Flocchini,Ali Miri,Nicola Santoro

Time Optimal Algorithms for Black Hole Search in Rings   (Citations: 2)
BibTex | RIS | RefWorks Download
In a network environments supporting mobile entities (called robots or agents), a black hole is harmful site that destroys any incoming entity without leaving any visible trace. The black-hole search problem is the task of a team of k > 1 mobile entities, starting from the same safe location and executing the same algorithm, to determine within finite time the location of the black hole. In this paper we consider the black hole search problem in asynchronous ring networks of n nodes, and focus on the time complexity. It is known that any algorithm for black-hole search in a ring requires at least 2(n − 2) time in the worst case. The best algorithm achieves this bound with a team of n − 1 agents with an average time cost 2(n − 2), equal to the worst case. In this paper we first show how the same number of agents using 2 extra time units from optimal in the worst case, can solve the problem in only \frac74 n-</font >O(1)\frac{7}{4} n-O(1) time on the average. We then prove that the optimal average case complexity \frac32 n-</font >O(1)\frac{3}{2} n-O(1) can be achieved without increasing the worst case using 2(n − 1) agents Finally we design an algorithm that achieves asymptotically optimal both worst case and average case time complexity employing an optimal team of k = 2 agents, thus improving on the earlier results that required O(n) agents.
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Recently, the optimality of black hole search has been studied in [2]...

    Paola Flocchiniet al. Searching for Black Holes in Subways

    • ...The number of agents has been recently reduced to 2, but the number of moves is still quadratic [1]...
    • ...Our solution improves the existing results of [12,1] which use a quadratic number of moves...
    • ...Recently, we have shown that an asymptotically optimal Θ(n) bound can be achieved using only 2 agents [1]; the number of moves is however still O(n 2 ). We now describe the first protocol that is optimal simultaneously in all three complexity measures: asymptotically in time ,a nd exactly in cost and size...

    Balasingham Balamohanet al. Improving the Optimal Bounds for Black Hole Search in Rings

Sort by: