We study a group of mobile agents operating on an arbitrary unknown distributed system. One of the nodes of the distributed system is extremely harmful and destroys any incoming agent without notification. The task of exploring the distributed system and locating the harmful node, Black hole search, has been studied with various modifications. We are studying the effects of the knowledge of incoming link on the size of the optimal solution. When an agent enters a node, the information which port leads back can be given to it. We refer to this as to the knowledge of incoming link. In previous research, it was always assumed that the agent is given this information. In this paper we study arbitrary, unknown distributed systems without the knowledge of incoming link. Agents are asynchronous and they communicate via whiteboards. We present a lower bound on the size of the optimal solution, proving that at least ∆ 2 +∆ 2 + 1 agents are necessary to locate the black hole. We provide an algorithm for black hole search without the knowledge of incoming link as well. We prove that this algorithm is correct, and that it uses ∆ 2 +∆ 2 + 1 agents, thus providing optimal solution.
In REF the effects of knowledge of incoming link on the optimal team size has been studied and lower bounds provided.
Locating a Black Hole without the Knowledge of Incoming Link
ALGOSENSORS
Computer Science