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