| Abstrakt: | 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 $\frac{\Delta^2+\Delta}{2} + 1$ agents are necessary to locate the black hole.
We provide an algorithm for the Black Hole Search without the knowledge of incoming link as well.
We prove that this algorithm is correct, and that it uses $\frac{\Delta^2+\Delta}{2} + 1$ agents, thus providing optimal solution.
|
|---|