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).
Byzantine companions, whiteboards, no map
verifiedWithout a map but with whiteboards, \((f+1)(\Delta+1)\) agents locate the black hole in \(O(m+f)\) rounds.
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: at most weak Byzantine faults
- Up to \(f\) agents behave arbitrarily but always report their own true identifier.
- Black hole appearance: present from the start
- The black hole is present at time 0, and the home base \(s\) is safe throughout.
- Timing: synchronous
- Time proceeds in rounds \(t=1,2,\dots\); in every round every agent communicates, computes and moves (at most one edge) simultaneously.
- 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
Results, in order of publication
With face-to-face communication instead: \((f+1)(\Delta+1)+3f+1\) agents, \(O(mn+f)\) rounds.
Open questions
None recorded for this variant.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.