Black hole search with finite automata scattered in a synchronous torus
From MaRDI portal
Publication:3095347
DOI10.1007/978-3-642-24100-0_41zbMATH Open1254.68053arXiv1106.6037OpenAlexW1910061521MaRDI QIDQ3095347FDOQ3095347
Arnaud Labourel, Shantanu Das, J. Chalopin, Euripides Markou
Publication date: 28 October 2011
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Abstract: 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.
Full work available at URL: https://arxiv.org/abs/1106.6037
Recommendations
- Tight bounds for black hole search with scattered agents in synchronous rings
- USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
- Black Hole Search in Asynchronous Rings Using Tokens
- Mobile search for a black hole in an anonymous ring
- Hardness and approximation results for black hole search in arbitrary networks
distributed algorithmsfinite state automatamobile agentsanonymous networksblack hole searchidentical tokens
Cites Work
- Collective tree exploration
- Exploring an unknown graph
- Approximation bounds for Black Hole Search problems
- Searching for a black hole in arbitrary networks: optimal mobile agents protocols
- Hardness and approximation results for black hole search in arbitrary networks
- Black Hole Search in Directed Graphs
- Black Hole Search in Asynchronous Rings Using Tokens
- Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links
- USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
- Structural Information and Communication Complexity
- Searching for a Black Hole in Synchronous Tree Networks
- Black hole search in common interconnection networks
- Mobile search for a black hole in an anonymous ring
- Deterministic symmetric rendezvous with tokens in a synchronous torus
- Principles of Distributed Systems
- Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
- Black Hole Search with Finite Automata Scattered in a Synchronous Torus
- Periodic Data Retrieval Problem in Rings Containing a Malicious Host
Cited In (6)
- Black Hole Search with Finite Automata Scattered in a Synchronous Torus
- Exploring an unknown dangerous graph with a constant number of tokens
- Blackhole pushdown automata
- Black Hole Search in Asynchronous Rings Using Tokens
- USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
- Black hole search despite Byzantine agents
This page was built for publication: Black hole search with finite automata scattered in a synchronous torus
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3095347)
