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

DOI10.1007/s00446-006-0154-yzbMath1266.68208MaRDI 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 hole; mobile agents; distributed search; malicious host; topological knowledge

Mathematics Subject Classification ID

68M10: Network design and communication in computer systems

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C85: Graph algorithms (graph-theoretic aspects)

68W15: Distributed algorithms

Related Items

Black Virus Decontamination of Synchronous Ring Networks by Initially Scattered Mobile Agents, Computing by Mobile Robotic Sensors, Tight bounds for black hole search with scattered agents in synchronous rings, Searching for black holes in subways, Synchronous black hole search in directed graphs, Explore and repair graphs with black holes using mobile entities, 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, On mobile agent verifiable problems, Distributed exploration of dynamic rings, 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, Exploration of Faulty Hamiltonian Graphs, Black Hole Search with Finite Automata Scattered in a Synchronous Torus, Unnamed Item, Locating and Repairing Faults in a Network with Mobile Agents, Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens, Approximation bounds for Black Hole Search problems, USING SCATTERED MOBILE AGENTS TO LOCATE A BLACK HOLE IN AN UN-ORIENTED RING WITH TOKENS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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