Sept 21, 2011: Mobile Agents Searching for Black Holes in Computer Networks

We consider the problem of locating a black hole in a synchronous anonymous unoriented torus network using mobile agents – small programs that hop from one computer of the network to the next. A black-hole is a harmful computer in the network that destroys any agent visiting it without leaving any trace. The objective is to locate the black hole with as little agents as possible, furthermore, using agents that are as simple as possible. This is difficult to achieve when the agents are initially scattered in the network and are unaware of the location of each-other.

Previous studies for black hole search used more powerful agents having memory that had to increase as the network size increased, were labelled with distinct identifiers and could either write messages on the nodes of the network or mark the edges of the network. In contrast, we solve the problem using a small team of finite-state agents each carrying a constant number of identical tokens.

Date: Wednesday, September 21, 2011 from 1:20 pm – 1:45 pm
Location: Vanier College, Room D-221
Speaker: Michel Paquette