Home›Mobile agents on graphs›Exploration›Collaborative exploration›Black hole search

Black hole search

A black hole destroys every agent that enters it, without trace; a team must locate it, losing as few agents as possible.

Problem statement and measuresexpand

A connected graph contains one black hole: a node that destroys any agent arriving there, leaving no trace. All other nodes are safe. Agents start at a safe node \(s\) (the home base) and must determine the location of the black hole; at least one agent must survive and know it. The primary measure is the team size (number of agents needed); the secondary measure is the cost (total number of moves, a move being one traversal of one edge) or, for synchronous agents, the time. Some papers also start the agents scattered, at distinct safe nodes; those results are recorded in the notes, because every catalogued variant starts at a home base.

Measures: Agents, number of agents needed (team size); Cost, total moves (asynchronous) or rounds (synchronous).

Progress map

tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Agents

Cost

No assumptions

—

Faults + static graph, + undirected

—

Timing + no faults

—

Asynchronous agents with whiteboards asynchronous, topology unknown, + whiteboards

0 open · 1 results

tight \(\Delta+1\) vs \(\Delta+1\) agents lost in the black hole

tight \(O(n^2)\) vs \(\Omega(n^2)\) asynchrony

Asynchronous agents with whiteboards in a ring + ring

0 open · 1 results

tight \(2\) vs \(2\) agents lost in the black hole

tight \(2n\log n+O(n)\) vs \(\Omega(n\log n)\) asynchrony

Marking nodes asynchronous, + map

—

Whiteboards and a map + whiteboards

0 open · 1 results

tight \(2\) vs \(2\) agents lost in the black hole

tight \(\Theta(n\log n)\) vs —

Tokens and a map + tokens

0 open · 1 results

tight \(2\) vs \(2\) agents lost in the black hole

tight \(\Theta(n\log n)\) vs —

Whiteboards and sense of direction asynchronous, + sense of direction, + whiteboards

0 open · 1 results

tight \(2\) vs \(2\) agents lost in the black hole

tight \(O(n^2)\) vs —

Tokens, no map asynchronous, topology unknown, + tokens

0 open · 2 results

tight \(\Delta+2\) vs \(\Delta+2\) agents lost in the black hole

polynomial gap \(O(mn)\) vs \(\Omega(n^2/\Delta)\) asynchrony

Synchronous agents with a map + synchronous, + map

0 open · 2 results

tight \(2\) vs —

polynomial gap \(3\tfrac{3}{8}\text{-approx.}\) vs \(\text{NP-hard}\) combinatorial hardness

Knowledge of the graph + at most weak Byzantine faults, + synchronous

—

Byzantine companions, with a map + map

0 open · 1 results

near-optimal \(2f+2\) vs —

unknown \(O(n+f)\) vs —

Byzantine companions, whiteboards, no map topology unknown, + whiteboards

0 open · 1 results

near-optimal \((f+1)(\Delta+1)\) vs —

unknown \(O(m+f)\) vs —

Dynamic rings + connected every round, + undirected, + no faults, + synchronous, + tokens, + ring

0 open · 1 results

tight \(3\) vs \(3\) adversarial edge changes

tight \(O(n^{1.5})\) vs \(\Omega(n^{1.5})\) adversarial edge changes

Know a better result, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.