Corelab Seminar

Euripides Markou (UCG)
Black Hole Search with Finite Automata Scattered in Synchronous Rings and Tori

We consider the problem of locating a black hole in synchronous anonymous networks using indistinguishable finite state agents. A black hole is a harmful node in the network that destroys any agent visiting that node without leaving any trace. The objective is to locate the black hole without destroying too many agents. This is difficult to achieve when the agents are initially scattered in the network and are unaware of the location of each other. In contrast to previous results, we solve the problem using a small team of finite-state agents each carrying a constant number of identical tokens that could be placed on the nodes of the network. Thus, all resources used in our algorithms are independent of the network size. We restrict our attention to ring and torus networks. We show lower bonus on the number of agents and tokens and we present deterministic algorithms that match those lower bounds.

This is a joint work with Jeremie Chalopin, Shantanu Das and Arnaud Labourel and part of this work has been presented at SIROCCO 2011 and DISC 2011.