Black Hole Search with Finite Automata Scattered in a Synchronous Torus

Details Black Hole Search with Finite Automata Scattered in a Synchronous Torus Black Hole Search with Finite Automata Scattered in a Synchronous Torus

2011-06-29

arxiv.org/abs/1106.6037v2

Computer Science

Data Structures and Algorithms

Scientific paper

We consider the problem of locating a black hole in synchronous anonymous networks using 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. Previous studies for black hole search used more powerful models where the agents had non-constant memory, 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 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 oriented torus networks and first show that no finite team of finite state agents can solve the problem in such networks, when the tokens are not movable. In case the agents are equipped with movable tokens, we determine lower bounds on the number of agents and tokens required for solving the problem in torus networks of arbitrary size. Further, we present a deterministic solution to the black hole search problem for oriented torus networks, using the minimum number of agents and tokens.

Affiliated with

Also associated with

No associations

Rating

Black Hole Search with Finite Automata Scattered in a Synchronous Torus does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Black Hole Search with Finite Automata Scattered in a Synchronous Torus, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Black Hole Search with Finite Automata Scattered in a Synchronous Torus will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-360218