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

DOI10.1016/J.TCS.2013.02.010MaRDI QIDQ392196zbMATH OpenOpenAlexFDO

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

Publication date 13 January 2014

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

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

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)

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.

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

Cites work

• Approximation bounds for Black Hole Search problems
• Black Hole Search in Asynchronous Rings Using Tokens
• Black hole search in common interconnection networks
• Black hole search in directed graphs
• Collective tree exploration
• Complexity of searching for a black hole
• Exploring an unknown dangerous graph using tokens
• Exploring an unknown graph
• Hardness and approximation results for black hole search in arbitrary networks
• Locating and repairing faults in a network with mobile agents
• Mobile search for a black hole in an anonymous ring
• Ping pong in dangerous graphs: optimal black hole search with pebbles
• Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links
• Searching for a Black Hole in Synchronous Tree Networks
• Searching for a black hole in arbitrary networks: optimal mobile agents protocols
• Structural Information and Communication Complexity
• Time optimal algorithms for black hole search in rings
• USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS

Cited in

(11)

• Gathering of robots in a ring with mobile faults
• More agents may decrease global work: a case in butterfly decontamination
• Hardness and approximation results for black hole search in arbitrary networks
• Black hole search with finite automata scattered in a synchronous torus
• Principles of Distributed Systems
• Mobile search for a black hole in an anonymous ring
• Exploring an unknown dangerous graph using tokens
• USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
• Black Hole Search in Asynchronous Rings Using Tokens
• Exploring an unknown dangerous graph with a constant number of tokens
• Gathering of robots on meeting-points: feasibility and optimal resolution algorithms

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)