Tight bounds for black hole search with scattered agents in synchronous rings

DOI10.1016/J.TCS.2013.02.010zbMATH Open1358.68315arXiv1104.5076OpenAlexW2952701693MaRDI QIDQ392196FDOQ392196

Authors: J. Chalopin, Shantanu Das, Arnaud Labourel, Euripides Markou 

Publication date: 13 January 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Abstract: We study the problem of locating a particularly dangerous node, the so-called black hole in a synchronous anonymous ring network with mobile agents. A black hole is a harmful stationary process residing in a node of the network and destroying destroys all mobile agents visiting that node without leaving any trace. We consider the more challenging scenario when the agents are identical and initially scattered within the network. Moreover, we solve the problem with agents that have constant-sized memory and carry a constant number of identical tokens, which can be placed at nodes of the network. In contrast, the only known solutions for the case of scattered agents searching for a black hole, use stronger models where the agents have non-constant memory, can write messages in whiteboards located at nodes or are allowed to mark both the edges and nodes of the network with tokens. This paper solves the problem for ring networks containing a single black hole. We are interested in the minimum resources (number of agents and tokens) necessary for locating all links incident to the black hole. We present deterministic algorithms for ring topologies and provide matching lower and upper bounds for the number of agents and the number of tokens required for deterministic solutions to the black hole search problem, in oriented or unoriented rings, using movable or unmovable tokens.

Full work available at URL: https://arxiv.org/abs/1104.5076

Recommendations

• USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
• Black hole search with finite automata scattered in a synchronous torus
• Mobile search for a black hole in an anonymous ring
• Black Hole Search in Asynchronous Rings Using Tokens
• scientific article; zbMATH DE number 2006651

zbMATH Keywords

distributed algorithmsfault tolerancefinite state automatamobile agentsanonymous networksblack hole searchidentical tokens

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed algorithms (68W15) Network design and communication in computer systems (68M10)

Cites Work

• Collective tree exploration
• Exploring an unknown graph
• Ping pong in dangerous graphs: optimal black hole search with pebbles
• Approximation bounds for Black Hole Search problems
• Exploring an unknown dangerous graph using tokens
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Hardness and approximation results for black hole search in arbitrary networks
• Time optimal algorithms for black hole search in rings
• 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
• Complexity of searching for a black hole
• Locating and repairing faults in a network with mobile agents
• Mobile search for a black hole in an anonymous ring

Cited In (11)

• Principles of Distributed Systems
• Mobile search for a black hole in an anonymous ring
• Gathering of robots in a ring with mobile faults
• Gathering of robots on meeting-points: feasibility and optimal resolution algorithms
• Exploring an unknown dangerous graph using tokens
• Hardness and approximation results for black hole search in arbitrary networks
• Exploring an unknown dangerous graph with a constant number of tokens
• More agents may decrease global work: a case in butterfly decontamination
• 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 with finite automata scattered in a synchronous torus

This page was built for publication: Tight bounds for black hole search with scattered agents in synchronous rings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q392196)