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. In most settings the black hole is present from the start; an eventually emerging black hole appears at an unknown time during the execution, and time is then counted from its appearance. 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).
Eventually emerging black hole, asynchronous agents, oriented ring
verifiedWith asynchronous agents no algorithm can announce the location of an eventually emerging black hole once and for all; with implicit termination, \(n\) agents that never communicate locate it within \(2n\) epochs.
Assumed (added on the last edge are outlined)
Not assumed
Formal definitions of this setting
- Graph dynamics: static graph
- \(G_t=G\) for all \(t\): the edge set never changes.
- Edge direction: undirected
- \(G=(V,E)\) with \(E\subseteq\binom V2\); every edge can be traversed in both directions.
- Faults: no faults
- All agents follow the algorithm forever.
- Black hole appearance: eventually emerging
- There is a time \(t \ge 0\) and a node \(u\) such that from time \(t\) on \(u\) destroys every agent on it or entering it, and stays a black hole. If \(t = 0\) then \(u \ne s\); the home base may become the black hole after the first round (after one epoch for asynchronous agents). Time is counted from \(t\) Bonnet et al. 2026b.
- Timing: asynchronous
- Each agent's Communicate–Compute–Move steps take finite but unbounded, adversarially chosen time. Time is measured in epochs. An epoch is an interval of time in which every agent completes at least one full Communicate–Compute–Move step; it need not be the shortest such interval. Time is counted by dividing the execution into consecutive epochs, and a bound of \(X\) epochs holds for every such division.
- Knowledge of the graph: sense 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.
- Marking nodes: no marking
- Agents cannot leave information at nodes.
- Topology: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
Statement for this variant
As in the synchronous setting, but agents are asynchronous. No algorithm with explicit termination exists (Theorem 6 of Bonnet et al. 2026b): a node through which every agent is delayed long enough looks like a black hole. The task is therefore implicit termination: eventually every surviving agent that suspects a node suspects the black hole and never changes its suspicion, and at least one agent does. Time is counted in epochs from the appearance of the black hole.
What is known
- synchronous bound (Theorem 1), which holds with implicit termination and therefore for asynchronous agents
Results, in order of publication
Introductory and current best without pebbles (Algorithm A5, Theorem 7): agent \(i\) tours the ring back and forth avoiding node \(u_i\) and always suspects \(u_i\); once the black hole appears, every agent except the one assigned to it is eventually destroyed. At most \(2n\) epochs, without communication.
Open questions
How many asynchronous agents without pebbles are needed with implicit termination: between 3 and \(n\)? With two pebbles four suffice Bonnet et al. 2026b.
Notes
With two pebbles, four agents that do not know \(n\) locate the black hole within \(5n\) epochs by cautious walks in pairs (Algorithm A6, Theorem 8). The impossibility of explicit termination does not hold for a black hole present from the start, where the last unexplored node can be isolated once all others are known to be safe Bonnet et al. 2026b. Checked against the full text of Bonnet et al. 2026b (SAND 2026).
What carries over from neighbouring settings
Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.
Algorithms from weaker settings work here
No catalogued weaker setting.
Lower bounds from stronger settings hold here
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.