  We study the problem of locating a particularly dangerous node, the so-called
black hole in a synchronous anonymous ring network with mobile agents. A black
hole is a harmful stationary process residing in a node of the network and
destroying destroys all mobile agents visiting that node without leaving any
trace. We consider the more challenging scenario when the agents are identical
and initially scattered within the network. Moreover, we solve the problem with
agents that have constant-sized memory and carry a constant number of identical
tokens, which can be placed at nodes of the network. In contrast, the only
known solutions for the case of scattered agents searching for a black hole,
use stronger models where the agents have non-constant memory, can write
messages in whiteboards located at nodes or are allowed to mark both the edges
and nodes of the network with tokens. This paper solves the problem for ring
networks containing a single black hole. We are interested in the minimum
resources (number of agents and tokens) necessary for locating all links
incident to the black hole. We present deterministic algorithms for ring
topologies and provide matching lower and upper bounds for the number of agents
and the number of tokens required for deterministic solutions to the black hole
search problem, in oriented or unoriented rings, using movable or unmovable
tokens.

Multiagent Systems