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

DOI10.1016/j.tcs.2013.02.010zbMath1358.68315arXiv1104.5076OpenAlexW2952701693MaRDI QIDQ392196

Arnaud Labourel, Jérémie Chalopin, Shantanu Das, 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

fault tolerancedistributed algorithmsmobile agentsfinite state automataanonymous networksblack hole searchidentical tokens

Mathematics Subject Classification ID

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

Related Items (4)

More agents may decrease global work: a case in butterfly decontamination ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Gathering of robots on meeting-points: feasibility and optimal resolution algorithms ⋮ Gathering of robots in a ring with mobile faults

Cites Work

• Unnamed Item
• Locating and repairing faults in a network with mobile agents
• Mobile search for a black hole in an anonymous ring
• 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
• Ping pong in dangerous graphs: optimal black hole search with pebbles
• TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS
• Black Hole Search in Directed Graphs
• Collective tree exploration
• Black Hole Search in Asynchronous Rings Using Tokens
• Rendezvous of Mobile Agents in Unknown Graphs with Faulty Links
• Approximation bounds for Black Hole Search problems
• USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS
• Exploring an unknown graph
• Structural Information and Communication Complexity
• Searching for a Black Hole in Synchronous Tree Networks
• Black hole search in common interconnection networks

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