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

no assumptions›+ static graph, + undirected›+ no faults›asynchronous, topology unknown, + whiteboards

Asynchronous agents with whiteboards

standard settingverified

Agents: tightCost: tight

Without a map, \(\Delta+1\) asynchronous agents are necessary and sufficient, and they need \(\Theta(n^2)\) moves.

Assumed (added on the last edge are outlined)

+Graph dynamicsstatic graph+Edge directionundirected+Faultsno faults+Marking nodeswhiteboards at the nodes

Not assumed

TimingasynchronousKnowledge of the graphno knowledge of the topology (\(n\) is known)Topologyarbitrary connected graph

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.
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: topology unknown: Agents know \(n\) but not the topology of \(G\).
Marking nodes: whiteboards: Every node has a whiteboard that agents read and write under mutual exclusion.
Topology: any topology: \(G\) is any connected graph in the class allowed by the other axes.

What is known

Agents · number of agents needed (team size)

tight

\(\Delta+1\).

lower bounds

\(\Delta+1\) Dobrev et al. 2006

bottleneckagents lost in the black hole

holds when

generic algorithms without topological knowledge
even if \(\Delta\) and \(n\) are known

\(\text{impossible}\) Dobrev et al. 2006

bottleneckasynchrony

holds when

if \(n\) is unknown, or the graph is not 2-connected

introductory—

current best

\(\Delta+1\)

Dobrev et al. 2006

Cost · total moves (asynchronous) or rounds (synchronous)

tight

\(\Theta(n^2)\) moves.

lower bound

\(\Omega(n^2)\) Dobrev et al. 2006

bottleneckasynchrony

holds when

size-optimal generic solutions

introductory—

current best

\(O(n^2)\)

Dobrev et al. 2006

Results, in order of publication

Dobrev et al. 2006 current best

Agents \(\Delta+1\)Cost \(O(n^2)\)

Introductory and current best.

Open questions

None recorded for this variant.

Notes

The anonymous ring was treated first Dobrev et al. 2007; see the variant for rings.

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.