Black Hole Search in Dynamic Rings

In this paper, we start the investigation of distributed computing by mobile agents in dangerous dynamic networks. The danger is posed by the presence in the network of a black hole (BH), a harmful site that destroys all incoming agents without leaving any trace. The problem of determining the location of the black hole in a network, known as black hole search (BHS), has been extensively studied in the literature, but always and only assuming that the network is static. At the same time, the existing results on mobile agents computing in dynamic networks never consider the presence of harmful sites. In this paper we start filling this research gap by studying black hole search in temporal rings, specifically focusing on 1-interval connectivity adversarial dynamics. The main complexity parameter of BHS is the number of agents (called size) needed to solve the problem; other parameters are the number of moves (called cost) performed by the agents, and the time until termination. Feasibility and complexity depend on many factors; the size n of the ring, whether or not n is known, and the type of inter-agent communication (whiteboards, tokens, face-to-face, visual). In this paper, we provide a complete feasibility characterization presenting size optimal algorithms. Furthermore, we establish lower bounds on the cost and time of size-optimal solutions and show that our algorithms achieve those bounds.