Searching for a black hole in arbitrary networks: optimal mobile agents protocols

DOI10.1007/s00446-006-0154-yzbMath1266.68208OpenAlexW1984719907MaRDI QIDQ1954192

Giuseppe Prencipe, Paola Flocchini, Nicola Santoro, Stefan Dobrev

Publication date: 20 June 2013

Published in: Distributed Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00446-006-0154-y

zbMATH Keywords

black holemobile agentsdistributed searchmalicious hosttopological knowledge

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (21)

Unnamed Item ⋮ TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS ⋮ Hardness and approximation results for black hole search in arbitrary networks ⋮ Distributed exploration of dynamic rings ⋮ Tight bounds for black hole search with scattered agents in synchronous rings ⋮ Explore and repair graphs with black holes using mobile entities ⋮ Black Virus Decontamination of Synchronous Ring Networks by Initially Scattered Mobile Agents ⋮ Improved periodic data retrieval in asynchronous rings with a faulty host ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Locating and Repairing Faults in a Network with Mobile Agents ⋮ Ping pong in dangerous graphs: optimal black hole search with pebbles ⋮ Exploration of Faulty Hamiltonian Graphs ⋮ Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens ⋮ Computing by Mobile Robotic Sensors ⋮ Approximation bounds for Black Hole Search problems ⋮ On mobile agent verifiable problems ⋮ Locating and repairing faults in a network with mobile agents ⋮ Searching for black holes in subways ⋮ Synchronous black hole search in directed graphs ⋮ 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

Cites Work

• Rendezvous and election of mobile agents: Impact of sense of direction
• Mobile search for a black hole in an anonymous ring
• Automaten in planaren Graphen
• The theory of search games and rendezvous.
• Piecemeal graph exploration by a mobile robot.
• Sense of direction in distributed computing
• A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree
• On agent-based software engineering
• How to learn an unknown environment. I
• A homology theory for spanning tress of a graph
• Rendezvous search on a graph
• Navigating in Unfamiliar Geometric Terrain
• Sense of direction: Definitions, properties, and classes
• Backward Consistency and Sense of Direction in Advanced Distributed Systems
• Exploring an unknown graph
• Tree exploration with little memory
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• Searching for a black hole in arbitrary networks
• Mathematical Foundations of Computer Science 2004
• Algorithms - ESA 2003
• LATIN 2004: Theoretical Informatics
• LATIN 2004: Theoretical Informatics
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Searching for a black hole in arbitrary networks: optimal mobile agents protocols