  In this paper we investigate the problem of searching for a black hole in a
dynamic graph by a set of scattered agents (i.e., the agents start from
arbitrary locations of the graph). The black hole is a node that silently
destroys any agent visiting it. This kind of malicious node nicely models
network failures such as a crashed host or a virus that erases the visiting
agents. The black hole search problem is solved when at least one agent
survives, and it has the entire map of the graph with the location of the black
hole. We consider the case in which the underlining graph is a dynamic
1-interval connected ring: a ring graph in which at each round at most one edge
can be missing. We first show that the problem cannot be solved if the agents
can only communicate by using a face-to-face mechanism: this holds for any set
of agents of constant size, with respect to the size $n$ of the ring.
  To circumvent this impossibility we consider agents equipped with movable
pebbles that can be left on nodes as a form of communication with other agents.
When pebbles are available, three agents can localize the black hole in
$O(n^2)$ moves. We show that such a number of agents is optimal.
  We also show that the complexity is tight, that is $\Omega(n^2)$ moves are
required for any algorithm solving the problem with three agents, even with
stronger communication mechanisms (e.g., a whiteboard on each node on which
agents can write messages of unlimited size). To the best of our knowledge this
is the first paper examining the problem of searching a black hole in a dynamic
environment with scattered agents.
