Black Hole Search and Exploration in Unoriented Tori with Synchronous Scattered Finite Automata

Abstract. We consider the problem of locating a black hole in a syn-chronous, anonymous, and unoriented torus network using mobile agents. A black hole is a harmful network node that destroys any agent visit-ing it without leaving any trace. The objective is to locate the black hole using as few agents as possible. We present here an almost optimal deter-ministic algorithm for synchronous (partially) unoriented tori using five scattered agents with constant memory and three identical tokens. We also study the exploration problem of a safe (i.e., without black holes) unoriented torus. While it has been previously shown that there is no universal algorithm for one agent with constant memory and any con-stant number of tokens which can explore all cubic planar graphs, we give here the first algorithm which enables a finite automaton with two tokens to explore (without termination detection) any totally unoriented torus and we prove optimality on the number of tokens