Mobility Matters
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 measurescollapse
black holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesblack holesABStart: agents A, B at s; ring of 6Cautious walk: mark the edge trying, cross, return, mark it safeA enters the black hole and is destroyed; B goes onB has explored its half; it walks to A's last safe edgeB reads 'trying' on edge v1-v2: the black hole is v2
Black hole search on a ring by two agents with cautious walk Dobrev et al. 2007 (the problem: Dobrev et al. 2006). Agents A and B start at the safe home base \(s\) of a ring of six nodes; one node (black) destroys every agent that enters it. Each explores half of the unexplored nodes: before crossing a new edge it marks it trying on the whiteboard (dashed), and after arriving it returns to mark it safe (green) before going on. A dies on its second new edge; B finishes its half, walks back through the explored part and finds the edge still marked trying: the one unexplored node beyond it is the black hole. One agent survives and knows it.

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).

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Imagine a computer network in which one computer has been taken over: every travelling program that arrives there is deleted without a trace, and nobody outside can tell. Find that computer by sending such programs, while losing as few of them as possible. We model the network as a graph: computers are nodes, cables between them are edges, and each travelling program is an agent. In the basic version the graph has \(n\) nodes and contains exactly one black hole, a node that destroys every agent that enters it; every other node is safe. A team of identical agents starts at a safe node \(s\), the home base; they have no map, but they know \(n\). At each node the edges leaving it are numbered \(1, 2, \dots\) (these numbers are called ports), each node has a whiteboard (a small memory on which agents can read and write notes), and the agents are asynchronous: every move (one traversal of one edge) takes a finite but unpredictable time, chosen by an adversary (an imagined opponent who picks the worst timing). The task: at least one agent must survive and know exactly which node is the black hole. We count the agents needed and the total number of moves.

1AlgorithmCautious walk and halving the unexplored ring Asynchronous agents with whiteboards in a ring → Dobrev et al. 2007

Two agents start together at \(s\) on a ring of \(n\) nodes (a cycle in which every node has two neighbours); they know \(n\).

  1. Cautious walk (used for every step into the unknown): an agent that crosses an edge nobody has crossed before first writes "I am trying this edge" on the whiteboard where it starts. If it arrives safely, it immediately goes back and changes the note to "this edge is safe", and only then continues. Nobody else ever enters an edge marked "trying".
  2. The unexplored nodes form one stretch of the ring. A phase starts: cut it into two halves of almost equal length; one agent explores the left half, the other the right half, both by cautious walk.
  3. The black hole lies in at most one half, so one agent finishes its half. It walks through the explored part to the last safe edge of the other agent.
  4. What is still unexplored is again one stretch, at most about half as long. A new phase starts: the finishing agent cuts it in two again, writes the new plan on the whiteboard there for its partner (in case the partner is only slow and comes back), and takes the half on the far side, away from the edge its partner is trying.
  5. When only one unexplored node remains, that node is the black hole.
Why it works and what it costs. Under cautious walk an agent that does not come back has died on the very first node beyond its last safe edge, so the black hole, if it has killed the partner, lies in the near half; the finishing agent always takes the far half and never enters an edge marked "trying", so exactly one agent dies and the other survives. Each phase at least halves the unexplored stretch, so there are about \(\log n\) phases, and each phase costs \(O(n)\) moves (walking around the explored part and exploring), giving \(O(n\log n)\) moves. Dobrev et al. 2007 show the exact cost \(2n\log n + O(n)\), and they prove that any algorithm, with any number of agents, needs at least \((n-1)\log(n-1) + O(n)\) moves, so this simple plan is optimal up to a factor of two.

Why it matters. Cautious walk is the basic safety tool of almost every later black hole search algorithm, in rings and in arbitrary graphs.

2Lower boundEvery unexplored port may lead to the black hole Asynchronous agents with whiteboards → Dobrev et al. 2006

Without a map, the agents do not know where a port leads. The adversary may therefore decide, as the algorithm runs, that the first port tried out of a node is the one that leads to the black hole. Take a graph in which the black hole is a neighbour of many nodes, for example the black hole \(0\) joined to every other node, with the home base at node \(1\). The first agent leaving node \(1\) through a new port is sent into the black hole. Some other agent must then reach node \(2\); the first agent that leaves node \(2\) through a new port is again sent into the black hole, and so on, node after node. Each such node costs one agent, and the search is not finished while two or more nodes are still unexplored, because a node that nobody has returned from may be the black hole or may simply be slow to reach.

Why it holds. In this example the algorithm loses an agent at almost every node adjacent to the black hole, and the black hole can have up to \(\Delta\) neighbours, where \(\Delta\) is the largest number of edges at any node (the maximum degree). With a cleverer graph (a ring of nodes all joined to a central black hole, which the adversary later replaces by a graph of maximum degree \(\Delta\) that looks the same to the agents) Dobrev et al. 2006 prove that \(\Delta + 1\) agents are needed; the full proof is longer. The same paper gives an algorithm with exactly \(\Delta + 1\) agents and \(O(n^2)\) moves, and shows that \(\Omega(n^2)\) moves are necessary for a team of this size, so both bounds are tight.

Why it matters. It shows that what limits a team without a map is the number of ports that can lead to the black hole, which is why a map or a sense of direction lowers the team to two agents.

3ImpossibilityWithout knowing \(n\), slow and dead look the same Asynchronous agents with whiteboards → Dobrev et al. 2006

Because moves take unpredictable time, an agent that has not come back may be dead or just slow. Suppose the agents do not know \(n\). Take a graph \(G\) with the black hole at node \(v\), and a second graph \(G'\) in which \(v\) is replaced by two nodes \(v_1\) and \(v_2\) joined to each other, sharing the edges that went to \(v\). In \(G'\) the adversary makes every edge into \(v_1\) or \(v_2\) extremely slow. Up to the moment the algorithm stops, the agents see exactly the same things in \(G\) and in \(G'\), so they stop in \(G'\) too, with both \(v_1\) and \(v_2\) unexplored: they cannot know which one is the black hole.

Why it holds. The same reasoning shows that the agents can never stop while two nodes are unexplored, and that the problem is unsolvable when the graph has a node (other than \(s\)) whose removal disconnects it: if that node is the black hole, everything behind it stays unexplored Dobrev et al. 2006. This is why the basic version assumes that \(n\) is known and that the graph stays connected after removing any one node (it is 2-connected).

Why it matters. The indistinguishability of slow and dead agents is the reason asynchronous black hole search needs knowledge of \(n\), and it reappears in every asynchronous lower bound for the problem.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Agents
Cost
Asynchronous agents with whiteboards standard
Without a map, \(\Delta+1\) asynchronous agents are necessary and sufficient, and they need \(\Theta(n^2)\) moves.
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
In an anonymous ring of known size, two co-located asynchronous agents are necessary and sufficient, at optimal cost \(\Theta(n\log n)\).
tight \(2\) vs \(2\) agents lost in the black hole
tight \(2n\log n+O(n)\) vs \(\Omega(n\log n)\) asynchrony
Whiteboards and a map
With a map, two agents locate the black hole in \(\Theta(n\log n)\) moves.
tight \(2\) vs \(2\) agents lost in the black hole
tight \(\Theta(n\log n)\) vs —
Tokens and a map
Whiteboards can be replaced by one pebble per agent: two agents, \(\Theta(n\log n)\) moves, even on non-FIFO edges.
tight \(2\) vs \(2\) agents lost in the black hole
tight \(\Theta(n\log n)\) vs —
Whiteboards and sense of direction
With sense of direction two agents suffice, still with \(\Theta(n^2)\) moves.
tight \(2\) vs \(2\) agents lost in the black hole
tight \(O(n^2)\) vs —
Tokens, no map
With a constant number of tokens and no map, \(\Delta+2\) agents and 3 tokens are necessary and sufficient.
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
With synchrony, two agents and a map, the question becomes the fastest exploration schedule, which is NP-hard to find.
tight \(2\) vs —
polynomial gap \(3\tfrac{3}{8}\text{-approx.}\) vs \(\text{NP-hard}\) combinatorial hardness
Byzantine companions, with a map
If up to \(f\) agents are Byzantine (they collude with the black hole and survive it), \(2f+2\) agents suffice with a map.
near-optimal \(2f+2\) vs —
unknown \(O(n+f)\) vs —
Byzantine companions, whiteboards, no map
Without a map but with whiteboards, \((f+1)(\Delta+1)\) agents locate the black hole in \(O(m+f)\) rounds.
near-optimal \((f+1)(\Delta+1)\) vs —
unknown \(O(m+f)\) vs —
Dynamic rings
In a 1-interval-connected ring three agents are necessary and sufficient; with pebbles they need \(\Theta(n^{1.5})\) moves.
tight \(3\) vs \(3\) adversarial edge changes
tight \(O(n^{1.5})\) vs \(\Omega(n^{1.5})\) adversarial edge changes

What the community started looking at

From the start the objective was the minimum number of agents that guarantees success, since every agent that enters the black hole is lost; the number of moves came second Dobrev et al. 2006. Later work replaced whiteboards by tokens Dobrev et al. 2013 Flocchini et al. 2012 Balamohan et al. 2016, turned to synchronous agents where time can be optimised Czyzowicz et al. 2006 Klasing et al. 2007, to dynamic graphs Di Luna et al. 2025, and to Byzantine companions Di Luna et al. 2025.

Variant of Collaborative exploration

Locating the black hole means exploring every other node safely, so black hole search is exploration of a dangerous graph by a team, where agents can be lost.

Related problems

Network decontamination: Both are security problems for agents in a hostile network: in black hole search the network destroys agents, in decontamination agents must clear a network that an arbitrarily fast intruder (or contamination) can re-enter.

Perspectives

  • Why compute by moving The atlas collects four models that grew out of four different wishes: software that travels through a network, swarms of robots that are as weak as possible, searchers that must find something at an unknown place, and matter that reshapes itself. They share an adversary, locality and symmetry; they differ in what they count.
  • When agents fail A node that destroys visitors, a robot that stops, an agent that lies, a searcher that misses the target: the papers motivate each fault by the hardware or the network, and each kind of fault changes a different measure, from team size to feasibility to an exact constant.
  • What forces the bounds Every lower bound in the atlas names the resource the adversary exploits. Read side by side, a few bottlenecks (distance, symmetry, missing information, an adversary that acts) explain most tight results, and the open entries cluster where no bottleneck beyond distance is known.

All settings

The assumption tree (10 settings, 5 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Agents, Cost); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Graph dynamics › Edge direction › Faults › Timing › Knowledge of the graph › Marking nodes › Topology.

tight near-optimal polynomial gap unknown impossible no variant

Assumptions specific to this problem

Knowledge of the graph

0no knowledge of the topology (\(n\) is known)1sense of direction2a map of the graph

Dobrev, Flocchini, Prencipe and Santoro organised black hole search in arbitrary networks around the agents' a priori knowledge: with topological ignorance, \(\Delta+1\) agents are necessary and sufficient and the cost is \(\Theta(n^2)\); with sense of direction two agents suffice, still at cost \(\Theta(n^2)\); with complete topological knowledge two agents suffice at cost \(\Theta(n\log n)\) Dobrev et al. 2006. Knowing \(n\) is the floor of the axis, because they prove that asynchronous black hole search is unsolvable when \(n\) is unknown Dobrev et al. 2006. Sense of direction is the notion of Flocchini, Mans and Santoro: a globally consistent labelling of the ports from which one can decide, from the label sequences alone, whether two walks from a node end at the same node Flocchini et al. 1998 (as defined in Dobrev et al. 2006); Dobrev et al. trace its effect on exploration back to Blum and Kozen's study of the power of a compass Blum & Kozen 1978. The three levels thus separate team size (from \(\Delta+1\) down to \(2\)) and, independently, cost (from \(n^2\) down to \(n\log n\)).

Formal definitions
0topology unknown
Agents know \(n\) but not the topology of \(G\).
1sense of direction
Agents have a consistent sense of direction: a globally consistent labelling of edges from which they can tell whether two walks lead to the same node.
2map
Agents have a map of \(G\) and know their starting position on it.

Marking nodes

0no marking1tokens (pebbles) that agents carry and drop2whiteboards at the nodes

The first black hole search papers gave the agents a whiteboard at every node Dobrev et al. 2007 Dobrev et al. 2006. Flocchini, Ilcinkas and Santoro observe that whiteboards let a protocol assume FIFO links and break symmetry, whereas "the theoretical quest, on the contrary, has been for the weakest interaction mechanism allowing the problem to be solved"; that weaker mechanism is identical tokens, taken from the early work on exploring safe graphs Flocchini et al. 2012. Dobrev, Flocchini, Královič and Santoro showed that \(\Delta+1\) agents, each with a token that may be placed on a node or a port, locate the black hole without a map at polynomial cost Dobrev et al. 2013 (as summarised in Flocchini et al. 2012); with a map, Flocchini, Ilcinkas and Santoro gave the first proof that one pebble per agent, on nodes only, matches the whiteboard bounds of two agents and \(\Theta(n\log n)\) moves, even on non-FIFO links Flocchini et al. 2012. Without a map the equivalence fails for a constant number of tokens: Balamohan, Dobrev, Flocchini and Santoro show that \(\Delta+2\) agents with three tokens are necessary and sufficient, one agent more than with whiteboards Balamohan et al. 2016.

Formal definitions
0no marking
Agents cannot leave information at nodes.
1tokens
Agents carry tokens (pebbles) they can place at nodes or on ports; tokens are identical and carry no other information.
2whiteboards
Every node has a whiteboard that agents read and write under mutual exclusion.

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