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).
Asynchronous agents with whiteboards in a ring
verifiedIn an anonymous ring of known size, two co-located asynchronous agents are necessary and sufficient, at optimal cost \(\Theta(n\log n)\).
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.
- 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: ring
- \(G\) is a cycle \(C_n\) (every node of degree 2), or a path when stated.
What is known
- at least one agent enters the black hole
- if \(n\) is unknown: no deterministic protocol always terminates correctly
- Theorem 1: \((n-1)\log(n-1)+O(n)\) moves, whatever the number of agents
- an adversarial scheduler delays moves along edges
- holds also for dispersed agents in oriented rings (Theorem 8)
Results, in order of publication
Introductory and current best (Algorithm DIVIDE, Theorems 2 and 3), size-optimal and cost-optimal within a factor of two; works in unoriented rings, since co-located agents agree on a direction through the whiteboard.
Open questions
None recorded for this variant.
Notes
Checked against the full text of Dobrev et al. 2007. Agents are anonymous and asynchronous, and the problem is solved when at least one agent survives and all survivors know the location of the black hole. In ideal time (every move one time unit) \(2n-4\) units are necessary whatever the number of agents (Theorem 4) and \(n-1\) co-located agents achieve it (Theorems 5 and 6); \(n^{1/q}+1\) agents need \(2(q+1)n-q-o(n)\) time for \(1\le q\le\log n\) (Theorem 7). With dispersed agents the cost is \(\Omega(n\log n)\), or \(\Omega(n\log(n-k))\) when the number \(k\) of agents is known (Theorems 8 and 9); in an oriented ring two dispersed agents are necessary and sufficient at cost \(O(n\log n)\) (Theorem 10), and in an unoriented ring three are necessary and sufficient at the same cost (Theorem 13).
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
Lower bounds from stronger settings hold here
No catalogued stronger setting.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.