Searching for an Eventually-Emerging Black Hole in Rings

Bonnet, François; Bramas, Quentin; Lamani, Anissa

doi:10.4230/LIPIcs.SAND.2026.18

Searching for an Eventually-Emerging
Black Hole in Rings

François Bonnet

Institute of Science Tokyo, Japan Quentin Bramas

University of Strasbourg, CNRS, ICUBE, France Anissa Lamani

University of Strasbourg, CNRS, ICUBE, France

Abstract

We study a novel variant of the Black Hole Search (BHS) problem where the black hole, a node that silently destroys visiting agents, can appear at any time during execution, rather than being present initially, as is assumed in all previous work. Our focus is on ring networks, and we examine this variant of the BHS problem under various assumptions, including whether the ring size is known and whether agents can use pebbles for marking nodes.

For synchronous agents, we provide four solutions: (1) a 4-agent algorithm for rings without additional assumptions, (2) a 3-agent algorithm assuming known ring size, (3) a 3-agent algorithm using pebbles, and (4) a 3-agent solution without additional assumptions but having a quadratic time complexity. For asynchronous agents, we develop two algorithms: one using $n$ agents without additional assumptions, and another using only 4 agents with pebbles.

Keywords and phrases:

Black hole search, mobile agent, distributed computing

Funding:

Quentin Bramas: This work was partially funded by the ANR project TURFU-NET, ref. ANR-24-IAS1-0001.

Copyright and License:

2012 ACM Subject Classification:

Computing methodologies

\rightarrow

Distributed algorithms ; Computing methodologies

\rightarrow

Mobile agents

Editors:

George B. Mertzios and Andréa W. Richa

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

The Black Hole Search (BHS) problem is a well-studied theoretical problem in distributed computing and algorithm design. It focuses on finding a dangerous node (black hole) in a network where any agent entering the node gets destroyed, and no information is returned. This problem has practical implications for real-world scenarios such as intrusion detection, where the black hole represents a compromised node or malicious activity that disrupts normal operations without immediate detection.

This paper investigates the Black Hole Search problem within a ring topology, but we assume that the black hole can appear at any time during the execution, so it is not necessarily present initially, as is commonly assumed in previous work. We explore various strategies for detecting the black hole using multiple agents under different conditions, such as synchronous and asynchronous communication models, known and unknown network sizes, and with or without external marking mechanisms like pebbles. The study aims to provide a comprehensive understanding of the complexities involved and proposes asymptotically optimal solutions for potential applications in intrusion detection systems.

Related Work

Probably the first paper introducing the Black Hole Search problem was [17] followed by several papers extending the problem to other topologies and settings [2, 8, 7, 13, 11, 12, 20, 14, 15, 19, 36]. In these papers, different conditions have been considered, such as prior knowledge of the network size, the synchrony level of the agents (synchronous or asynchronous), communication mechanisms (e.g., whiteboard/pebbles) [16], and whether the agents are initially scattered [25] or start from a single node called a base station. In these previous works, the main goal is to first identify the conditions that allow a team of agents to successfully solve the BHS problem, and then propose distributed solutions that are optimal in terms of the number of mobile agents required and the move complexity [31, 32, 1, 9, 33]

Variants of the BHS problem include having multiple black holes [10], gray/Byzantine holes [37, 30], and rendezvous in dangerous networks [19, 23]. Byzantine black holes [30] can be seen as a generalization of eventually-emerging black holes as they may decide not to kill an agent passing by and can also erase the content of the whiteboard where they are located. While our problem of eventually-emerging black holes shares similarities with Byzantine black holes, the assumptions and achievable results differ significantly. In [30], the exploration problem is considered assuming that the starting position of the agents remains safe throughout the execution and that the size of the ring $n$ is known. These assumptions are heavily exploited in their algorithms; for instance, their 3-agent algorithm with a pebble relies on the safe home base to continuously coordinate agents. In contrast, our setting considers an unsafe home base, rendering their algorithms inapplicable.

Exploration with fault tolerance [29, 28, 26] and decontamination of mobile threats [6] extend BHS to broader fault models.

Recent investigations have extended the study of the problem to dynamic graphs [27, 4, 3], primarily focusing on ring networks with 1-interval connectivity (e.g., [35, 34]). The goal is to determine how the computational complexity of finding a black hole changes when the graph is dynamic. The problem was again studied under different assumptions.

To the best of our knowledge, all previous investigations of the basic Black Hole Search problem assume that the black hole is present in the initial configuration. In this paper, we address the case in which the black hole can emerge at any time during execution. This fundamental difference prevents solutions from relying exclusively on traditional strategies like the cautious walk (where agents move in such a way that two or more agents never enter the black hole at the same time from the same edge [21]). While cautious walk is highly effective when the black hole is initially present, it is vulnerable in our setting: during execution, if all agents group together on the same node to safely coordinate their next move, an eventually-emerging black hole could appear exactly on that node, killing all agents simultaneously and leaving no one to deduce its location. Therefore, new techniques must be combined with cautious walks to ensure at least one agent survives the initial appearance of the black hole. We explore the impact of such an eventual appearance on ring networks under different assumptions, such as whether the size of the ring is known and whether agents can use pebbles.

Contributions

We address the aforementioned problem on ring networks and present four black hole search algorithms for synchronous agents, each one based on a particular set of assumptions. The first one uses four agents; the second one assumes that the agents know the size of the ring; the third one considers that the agents can use a pebble; and the fourth one has no additional assumptions but has a higher time complexity. When the agents are asynchronous, we provide two algorithms: one that uses $n$ agents without any assumptions, where $n$ denotes the size of the ring, and a second that uses only 4 agents with pebbles. Table 1 summarizes our results. All our algorithms can be visualized in an interactive simulator to see the executions with a given black hole appearance round and location¹¹1https://bramas.fr/static/emerging-BHS/. Asynchronous executions are simulated by adding random idle rounds. The pseudo-code we provide matches the implementation of the online simulation, and one can see the current state of each agent, including the line number of its last instruction in the algorithm.

Due to space limitations, several proofs and algorithm pseudo-codes have been omitted. The full algorithms are available in the online simulator.

Table 1: Summary of our results (we ignored constant terms in the complexity). Underlined values are not optimal along that specific dimension.

Algorithm	# agents	pebble	knowledge $n$	safe HB	complexity	termination
Synchronous agents
Imp. Thm. 1	2	Yes	Yes	Yes	$*$	implicit
$\mathcal{A}_{1}$	4	No	No	No	$3n$	explicit
$\mathcal{A}_{2}$	3	Yes	No	No	$4n$	explicit
$\mathcal{A}_{3}$	3	No	Yes	No	$4n$	explicit
$\mathcal{A}_{4}$	3	No	No	No	$O(n^{2})$	explicit
Asynchronous agents
Imp. Thm. 6	*	Yes	Yes	Yes	$*$	explicit
$\mathcal{A}_{5}$	$n$	No	No	No	$2n$	implicit
$\mathcal{A}_{6}$	4	Yes	No	No	$5n$	implicit

2 Model

We consider a team $\mathcal{A}$ of $k$ agents located on a ring of size $n\geq 2$ . The ring consists of $n$ nodes of degree 2, denoted $u_{0},u_{1},\dots,u_{n-1}$ where $u_{i}$ and $u_{j}$ are connected only if $|j-i|=1\mod n$ . The nodes are anonymous for the agents but the ring is consistently oriented²²2In our setting, this is equivalent to assume that the agents know the input port. i.e., all the agents agree on what is the neighbor in the clockwise orientation and what is the neighbor in the counterclockwise orientation. All the agents start at the same node called the home base (HB). We consider that the agents have unbounded memory, in particular, they have access to an internal clock (which may not be synchronized in the asynchronous setting).

Each agent has a unique identifier in the interval $[1,k]$ and executes an algorithm that takes as input the current state of the agent (an arbitrary number of variables used by the algorithm and in particular its internal clock), as well as the states of any co-located agents (located on the same node). In some cases, the agents are allowed to use pebbles which can be dropped on a node, picked up, and carried by the agents. We assume that all the pebbles are identical and hence, there is no way to identify which agent dropped a pebble on a given node.

Scheduler

We consider two kinds of schedulers. Under the synchronous scheduler, the internal clocks of all the agents are synchronized. In other words, time is discretized into rounds and at each round, all agents execute their algorithms synchronously. In this setting, it is meaningful for an agent to “wait” for another agent at a given node. Then, all agents that have decided to move do so simultaneously.

Under the asynchronous scheduler, the internal clocks of the agents have arbitrary speeds. Nevertheless, we still consider that the reading of the states of co-located agents is performed atomically, i.e., an agent retrieves the states of any co-located agents at a given point in time in order to execute its algorithm. Then, the execution takes an arbitrary (but finite) amount of time. Finally, if the agent decides to move, the movement also takes an arbitrary amount of time (during which the agent is “invisible” on the edge). We make no assumption on how agents move along an edge, so we even allow an agent to “overtake” another agent (the link is not necessarily FIFO). In this setting, we can also discretize time into a sequence of time instants representing the moments when events occur (an agent reads the states of co-located agents, leaves a node, or arrives at a node). An asynchronous round is the time required for all agents to perform at least one complete cycle (from reading states to arriving at the destination node, if applicable).

Eventually-emerging black hole

A black hole is a node that destroys every agent located on it. When an agent is destroyed, it disappears from the system. We say that a black hole appears in node $u$ at time $t$ if, starting from time $t$ , node $u$ becomes a black hole. Agents that are not on $u$ are not impacted; agents in node $u$ at time $t-1$ that do not leave $u$ , or those arriving on $u$ at time $t^{\prime}\geq t$ , are killed. We denote by $\mathcal{A}_{t}$ the set of agents that have not been killed by time $t$ .

We say a black hole is initial if it is present in the initial configuration, at time $t=0$ . In this paper, we consider an eventually-emerging black hole, i.e., there exists a time $t\geq 0$ and a node $u$ such that a black hole appears on $u$ at time $t$ . We assume that the black hole cannot appear at the home base at time $t=0$ (otherwise all agents would be killed before starting their execution). However, we consider, unless stated otherwise, that a black hole can appear at the home base at any time $t\geq 1$ in the synchronous case, and at any time after one asynchronous round in the asynchronous case. That is, we assume the home base is not necessarily safe (it is only guaranteed to be safe in the first round).

In the remainder, we consider that a single black hole eventually appears and remains for the rest of the execution. We consider that each agent $a$ has a variable $\texttt{bh}_{a}$ , which contains either $\bot$ or the relative location of a node. It represents the node where the agent thinks a black hole is located, encoded as a distance and direction relative to its own position. $\texttt{bh}_{a}(t)$ denotes the value of the variable at time $t$ . In the online simulation, a negative value means the distance is in the counterclockwise direction. For simplicity, in the remainder, $\texttt{bh}_{a}(t)$ represents the node (in $V$ ) suspected by the agent.

The Eventually-emerging black hole search (EBHS) problem

We say an algorithm solves the EBHS problem with explicit termination if, in any execution with an eventually-emerging black hole, eventually there exists an agent that identifies correctly the location of the black hole and terminates. In other words, we require three properties: an agent must only identify a node where a black hole is located; if an agent $a$ identifies the location of the black hole by setting the value $\texttt{bh}_{a}$ , then it cannot change the value of $\texttt{bh}_{a}$ afterward; and eventually one agent correctly identifies the location of the black hole.

Formally, an algorithm solves the EBHS problem with explicit termination if, in any execution $E$ where a black hole appears on $u$ , the three conditions are satisfied:

	$\displaystyle\forall t\geq 0,\forall a\in\mathcal{A}_{t},\texttt{bh}_{a}(t)\in% \{\bot,u\}$
	$\displaystyle\forall t\geq 0,\forall a\in\mathcal{A}_{t}\cap\mathcal{A}_{t+1},% \left(\texttt{bh}_{a}(t)=u\Rightarrow\texttt{bh}_{a}(t+1)=u\right)$
	$\displaystyle\exists t\geq 0,\exists a\in\mathcal{A}_{t},\text{ s.t. }\texttt{% bh}_{a}(t)=u$

As we show in Theorem 6, EBHS with explicit termination is not solvable with asynchronous agents, so we define a new version of the problem where termination is implicit. We say an algorithm solves the EBHS problem with implicit termination if, in any execution with an eventually-emerging black hole, eventually all the agents that suspect a node, correctly suspect the location of the black hole forever after some time $t$ (and at least one agent suspects the location of the black hole).

Formally, an algorithm solves the EBHS problem with implicit termination if, in any execution $E$ where a black hole appears on $u$ , the two conditions are satisfied:

	$\displaystyle\forall a\in\bigcap_{t\in\mathbb{N}}\mathcal{A}_{t},\exists t\geq 0% ,\text{ such that }(\forall t^{\prime}>t,\texttt{bh}_{a}(t^{\prime})=u)\vee(% \forall t^{\prime}>t,\texttt{bh}_{a}(t^{\prime})=\bot)$
	$\displaystyle\exists a\in\bigcap_{t\in\mathbb{N}}\mathcal{A}_{t},\exists t\geq 0% ,\text{ such that }(\forall t^{\prime}>t,\texttt{bh}_{a}(t^{\prime})=u)$

In the literature, finding the location of the black hole, i.e., identifying a path to the black hole, is sometimes referred to as the weak black hole search problem, and marking all the edges leading to the black hole is the strong version of the problem. Here, we do not consider that edges can be marked and we solve the weak version. Also, one can notice that when $n$ is known, the two versions are equivalent.

Complexity

Since the black hole can appear after an arbitrarily long time, the time complexity is always computed starting from the time at which the BH appears. In other words, the time complexity (or simply complexity) of an algorithm is the number of (synchronous/asynchronous) rounds between the appearance of the black hole and the time $t$ from which an agent correctly identifies the location of the black hole. When considering implicit termination, we consider the number of asynchronous rounds until all the agents suspecting a black hole suspect the correct location and never change their suspicion after that.

3 Synchronous agents

In this section we address the EBHS problem assuming synchronous agents. We present four deterministic algorithms that solve the EBHS problem under different hypotheses. The various algorithms highlight the fact that it is very challenging to find an algorithm that is optimal for all the assumptions simultaneously (number of agents, knowledge of $n$ , storage capability, and time complexity). The four algorithms use different techniques to be optimal regarding several assumptions, but each of them has at least one assumption along which it is not optimal (the underlined values in Table 1). Our four algorithms are different and use new techniques that are not found in the literature. While they may seem simple at first glance, they are in fact the result of a very careful construction to make them correct. It is still open whether there exists an algorithm that is optimal for all the assumptions simultaneously.

The first algorithm uses four agents that are not aware of the size of the ring and do not have any additional external mechanisms to communicate (like pebbles or whiteboards). In the second and third algorithms, the number of agents is reduced to three, assuming the size of the ring $n$ is known or assuming the agents can use pebbles, respectively. The fourth algorithm uses three agents without the knowledge of $n$ and without using pebbles, but its complexity is quadratic. A summary of our results for synchronous agents is presented in Table 1.

Handling small rings ( $n\in\{2,3,4\}$ )

To simplify the presentation of Algorithms $\mathcal{A}_{1}$ – $\mathcal{A}_{4}$ , we assume throughout the remainder of this section that the ring size satisfies $n\geq 5$ . When we assume $n\geq 2$ , the problem can be handled by a short pre-processing phase executed before running any of our four algorithms.

Algorithm $\mathcal{A}_{0}$ is such a pre-processing algorithm. It uses only three agents (agents $a_{1},a_{2},a_{3}$ ); a fourth agent, if present, is ignored (it simply waits). First, the agents detect the case $n=2$ in a constant number of rounds. Otherwise, they start executing $\mathcal{A}_{4}$ (which is correct already for $n\geq 3$ ) while progressively ruling out the remaining small sizes. Importantly, this pre-processing phase can be stopped as soon as the agents have certified that $n\geq 5$ ; the algorithm is designed so that in this case all agents stop in the same round, and we can then start any of $\mathcal{A}_{1}$ – $\mathcal{A}_{4}$ from a clean synchronized configuration.

Cautious walk

In some of our algorithms, we use the cautious walk strategy that was introduced in [18, 21]. The cautious walk is a strategy used when the agents are sure about the existence of the black hole. It ensures that no two or more agents enter the black hole from the same edge. This is done in the following manner: assume that two agents are on node $u$ and one moves from $u$ to a neighboring node $v$ . If the agent comes back to $u$ , then $v$ is identified as safe and both agents can move toward it; otherwise, it is identified as a black hole.

Procedure 1 CautiousWalk

(leader,follower,direction)

.

Of course, a cautious walk works if we know that the black hole has already emerged; otherwise, both agents can be killed when they are co-located.

Procedure 1 presents the algorithm pseudo-code, where agent refers to the current agent executing the algorithm. This procedure can be executed given three arguments: the two agents performing the cautious walk and the direction. The red part of the algorithm shows the code executed when the presence of the black hole is detected. In the cautious walk, the variable bh is set and the agent terminates.

Impossibility with two agents

We can prove that the EBHS problem is not solvable with two agents, as is the case when the black hole exists initially. This result holds even with whiteboards, safe home base, and the knowledge of $n$ . Interestingly, it also holds assuming implicit termination.

Theorem 1.

There is no algorithm solving the EBHS problem with only two synchronized agents, even with a safe home base, whiteboards, the knowledge of $n$ , and implicit termination.

Proof.

Assume, for the sake of contradiction, that such an algorithm exists.

We denote by $1=t_{0},t_{1},t_{2},\ldots$ all the rounds, in increasing order, where the two agents are co-located in an execution where no black hole appears (this sequence contains 1 because the agents are initially co-located, but can be finite or infinite). It is clear that the agents are always co-located on the home base, otherwise a black hole could appear where they are both located, killing them both.

We denote by $P_{i}$ , resp. $Q_{i}$ , the set of nodes visited by the first agent, resp. the second agent, between round $t_{i}$ and $t_{i+1}$ (or in the infinite remaining execution if $t_{i+1}$ does not exist, these sets are still well-defined because the ring is finite).

If $u_{0}$ denotes the home base, we saw that $u_{0}\in P_{i}\cap Q_{i}$ , for all $i\geq 0$ . If there exists another node $v\neq u_{0}$ such that $v\in P_{i}\cap Q_{i}$ for some $i$ , then if the black hole appears on node $v$ at round $t_{i}$ , since the agents do not meet before $t_{i+1}$ , they will perform the same movements as if the black hole was not there, hence they will explore $P_{i}$ and $Q_{i}$ respectively, and both end up in the black hole.

So we know that $P_{i}\cap Q_{i}=\{u_{0}\}$ for all $i\geq 0$ .

If there are two nodes $v_{0}$ and $v_{1}$ that are never visited, then the algorithm cannot distinguish the two executions where the black hole appears in $v_{0}$ and in $v_{1}$ , hence will fail in one of the two executions, a contradiction.

So now consider a ring of size $n\geq 5$ , there exists a $i$ such that, a node at distance 2 from the home base (say $u_{2}$ ) is visited by an agent between $t_{i}$ and $t_{i+1}$ . Consider without loss of generality that $u_{0},u_{1},u_{2}\in P_{i}$ , and $u_{1},u_{2}\not\in Q_{i}$ . Hence, the agent exploring $Q_{i}$ cannot distinguish the two executions where the first agent is killed on its last visit to $u_{1}$ before its first visit of $u_{2}$ , resp. where the agent is killed on its first visit on $u_{2}$ . Indeed, when the two executions differ, the states of the whiteboard at nodes $u_{0}$ and $u_{1}$ (if any) are the same in the two executions (because, by assumption, the agent goes from $u_{1}$ to $u_{2}$ when the executions differ), so when the second agent reaches $u_{0}$ at time $t_{i+1}$ , it cannot distinguish between the two executions. If the agent suspects one of the nodes, she will be wrong in the execution where the black hole appears in the other node, which is a contradiction. $\hfill\blacktriangleleft$

3.1 Algorithm $\mathcal{A}_{1}$ : Four Agents

We present in the following a deterministic algorithm $\mathcal{A}_{1}$ that solves the EBHS problem using four agents using only face-to-face communications. The size of the ring $n$ is unknown and the HB is assumed unsafe. This first algorithm consists of running an algorithm that works when the black hole is initially present, here simply the cautious walk. The idea is to create two groups of agents running such an algorithm. Since the two groups never meet, the appearance of the black hole can only impact one of the two groups. Hence, the correctness of the algorithm follows from the correctness of the cautious walk strategy. The complete algorithm is given in Algorithm 1.

Algorithm 1

\mathcal{A}_{1}

: Four-Agent EBHS Solution.

Observe that when the black hole appears, the worst time complexity is the same as for the cautious walk with initial black hole, which is $3n$ rounds. We hence have the following theorem.

Theorem 2.

Assuming $n\geq 5$ (otherwise, run Algorithm $\mathcal{A}_{0}$ first), Algorithm $\mathcal{A}_{1}$ solves the weak EBHS problem with 4 synchronous agents, with a worst-case time complexity of $3n$ .

3.2 Algorithm $\mathcal{A}_{2}$ : with one pebble

We now solve the problem with Algorithm $\mathcal{A}_{2}$ using three agents having a single pebble with a completely new algorithm. Initially, two agents move in one direction (say clockwise, right on the figures), and one in the opposite direction. Then, if no black hole is detected, the agents perform three moves repeatedly. After the three moves, the configuration is similar but translated one node clockwise.

Algorithm 2

\mathcal{A}_{2}

: Three-Agent EBS Solution with one pebble.

Figure 1 shows the first 5 configurations of the execution of Algorithm $\mathcal{A}_{2}$ . As shown, configuration $C_{4}$ is just the translated version of configuration $C_{1}$ so the same sequence of moves is repeated until a black hole is detected.

A black hole is detected when an agent that is supposed to be co-located with another agent is alone. Then, this agent knows that a black hole appeared. The pseudo-code of the algorithm is given in Algorithm 2. The red parts correspond to the actions when a black hole is detected.

To illustrate how Algorithm $\mathcal{A}_{2}$ works, consider the case where the detection occurs in a configuration similar to $C_{1}$ by agent $a_{3}$ on $u_{2}$ . The detecting agent does not know where the black hole is located but it knows it is either one or two hop(s) counterclockwise, so it moves in the clockwise direction until it sees a pebble. When it finds the pebble, it knows the black hole is adjacent to it.

If the detection occurs in a configuration similar to $C_{2}$ by agent $a_{1}$ (resp. $a_{2}$ ) located on $u_{1}$ , then it knows the black hole is on the clockwise direction and both other agents are killed (resp. on the anticlockwise direction, and the agent continues its movement to tell agent $a_{3}$ about it and to start a cautious walk).

The following Theorem proves the correctness regardless of where the black hole appears.

Figure 1: First 5 configurations of the execution of Algorithm

\mathcal{A}_{2}

. The square added to a position represents the pebble.

Theorem 3.

Assuming $n\geq 5$ (otherwise, run Algorithm $\mathcal{A}_{0}$ first), Algorithm $\mathcal{A}_{2}$ solves the EBHS using three synchronous agents having a single pebble, with a worst-case time complexity of $4n$ .

Proof.

Let $a_{1}$ , $a_{2}$ and $a_{3}$ denote the three agents (when illustrated by a figure, we consider them ordered from left to right).

While no agent is killed by a black hole, the three agents move such that every three rounds they are translated by one node, so when a black hole appears, at least one agent is eventually killed.

Without loss of generality, we can assume that the first time an agent is destroyed is in configuration $C_{1},C_{2},$ or $C_{3}$ , in node $u_{0},u_{1},u_{2},$ or $u_{3}$ that contains at least an agent. We now show that in all the 7 possible cases, at least one agent remains and identify the black hole correctly.

$\blacksquare$

If the black hole appears during $C_{1}$ on node $u_{0}$ . Then $a_{1}$ is killed and agent $a_{2}$ detects it in the next round, since she is not co-located with $a_{1}$ . This corresponds to Line 14. $a_{2}$ then meets with $a_{3}$ and they start a cautious walk to eventually detect the black hole (after 2 iterations of the cautious walk).
$\blacksquare$

If the black hole appears during $C_{1}$ on node $u_{2}$ . Then $a_{2}$ and $a_{3}$ are killed and the third agent $a_{1}$ detects it in the next configuration since no other agent is co-located with her (in $C_{2}$ , $a_{1}$ should be co-located with $a_{2}$ ). This corresponds to Line 5 of the algorithm. $a_{1}$ , located on $u_{1}$ , correctly identifies that the black hole is located on its clockwise adjacent node.
$\blacksquare$

If the black hole appears during $C_{2}$ on node $u_{1}$ . Then agents $a_{1}$ and $a_{2}$ are killed and the third agent $a_{3}$ detects it 2 rounds after, when no other agent is co-located with her (in $C_{4}$ , $a_{3}$ should be co-located with $a_{2}$ ). This corresponds to Line 24. $a_{3}$ moves clockwise until she sees the pebble in $u_{0}$ , and she knows that the black hole is adjacent to the pebble.
$\blacksquare$

If the black hole appears during $C_{2}$ on node $u_{3}$ . Then agent $a_{3}$ is killed. Two rounds after, $a_{2}$ is also killed and we are in a configuration similar to $C_{1}$ where the black hole appears in $u_{2}$ .
$\blacksquare$

If the black hole appears during $C_{3}$ on node $u_{0}$ . Then $a_{1}$ is killed and agent $a_{2}$ detects two rounds after, since she is not co-located with $a_{1}$ (in a configuration similar to $C_{2}$ in the next phase). This corresponds to Line 14. $a_{2}$ then meets with $a_{3}$ and they start a cautious walk and eventually detects the black hole (after 3 iterations of the cautious walk).
$\blacksquare$

If the black hole appears during $C_{3}$ on node $u_{2}$ . Then $a_{2}$ is killed ( $a_{1}$ is also killed two rounds after). Agent $a_{3}$ moves clockwise until she sees the pebble in $u_{1}$ , and she knows that the black hole is adjacent to the pebble.
$\blacksquare$

If the black hole appears during $C_{3}$ on node $u_{3}$ . Then agent $a_{3}$ is killed and one round after $a_{2}$ is also killed and we are in a configuration similar to $C_{1}$ with a black hole on $u_{2}$ .

When the black hole appears, one agent is killed after at most $3n$ rounds and the worst time complexity is obtained in the penultimate case, as it requires $n$ additional rounds for the last agent to find the pebble. $\hfill\blacktriangleleft$

3.3 Algorithm $\mathcal{A}_{3}$ : when $𝒏$ is known

We now present Algorithm $\mathcal{A}_{3}$ assuming $n$ is known, with three synchronous agents, unsafe home base and explicit termination. The algorithm uses a different technique from the previous one.

The algorithm works as follows: Initially, one agent has a role denoted traveler and moves clockwise and the two others stay idle. Then, the agents repeatedly perform the same phase. In a phase, the traveler moves $n-2$ times clockwise and then stays idle for one round. Another agent takes the role next traveler and stays idle for $n-1$ rounds. The last agent takes the role waiter, moves once counterclockwise, and then stays idle for $n-2$ rounds.

The first three configurations $C_{0},C_{1},C_{2}$ are shown in Figure 2. The first phase starts in configuration $C_{1}$ .

Figure 2: The first three configuration of Algorithm

\mathcal{A}_{3}

.

After $n-2$ rounds in the phase, the traveler agent reaches the waiter agent. Then each agent stays idle for one round and then they repeat the phase after exchanging their role: the traveler becomes the waiter, the waiter becomes the next-traveler, and the next-traveler becomes the traveler, as shown in Figure 3.

Observe that at each phase the configuration is similar but rotated by one node counterclockwise.

This phase is repeated until a black hole appears. If a black hole kills the traveler agent while she performs the tour of the ring, then, after $n-2$ rounds, the waiter agent detects that and moves clockwise to warn the third agent and starts a cautious walk to find the black hole, as shown in Figure 4.

Figure 3: Execution of Algorithm

\mathcal{A}_{3}

when no black hole is detected.

Figure 4: Execution of Algorithm

\mathcal{A}_{3}

when the traveler agent is killed.

Figure 5: Execution of Algorithm

\mathcal{A}_{3}

when two agents are killed.

If a black hole appears and kills two co-located agents, then this happens at the beginning of the phase and the traveler is still alive. When the traveler agent finishes its tour, it detects that the waiter agent is not here waiting for her, hence knows that the adjacent node contains a black hole, as shown in Figure 5. We obtain the following theorem.

Theorem 4.

Assuming $n\geq 5$ (otherwise, run Algorithm $\mathcal{A}_{0}$ first), Algorithm $\mathcal{A}_{3}$ solves the EBHS with three synchronous agents that know the size $n$ of the ring, with a worst-case time complexity of $4n$ .

Proof.

Consider the phase when the black hole first kills an agent. Let $u_{0}$ denotes the node where the waiter and the next-traveler are co-located, and $u_{1},u_{2},\ldots,u_{n-1}$ the nodes clockwise. We have four cases to consider. If the black hole appears in a node $u_{i}$ , $i\in[1,n-2]$ killing only the traveler. Then the traveler never meets with the waiter and the waiter detects the problem and starts a cautious walk with the third agent. One agent correctly identifies the black hole by the correctness of the cautious walk.

If the black hole appears in $u_{0}$ killing both the waiter and the next-traveler. Then the traveler detects it when reaching $u_{n-1}$ and the waiter is not present.

If the black hole appears in $u_{0}$ but kills only the next-traveler, then the phase terminates without the two other agents realizing it and a new phase starts. Now we are exactly in the case where the traveler is killed in $u_{1}$ .

If the black hole appears in node $u_{n-1}$ killing first the waiter and then the traveler. Again a new phase starts for the remaining agent, which is now the traveler, and the situation is exactly like when the waiter and the next-traveler are killed in $u_{0}$ .

The worst time complexity is obtained when the traveler is killed and, after waiting for $n$ rounds, the two other agents require at most $3n$ rounds to find the black hole. $\hfill\blacktriangleleft$

3.4 Algorithm $\mathcal{A}_{4}$ : with quadratic complexity

In the following, we address the case in which $n\geq 3$ is unknown and the number of agents is 3. To make our strategy easier to understand, we first describe the algorithm assuming that the HB is safe.

This simplified algorithm consists in repeating the following for $i=1,2,\ldots$ : one agent moves to the $i$ -th node on one side, and then comes back. Eventually, either $(a)$ the agent does not come back and we know there is a black hole or $(b)$ for a given $i$ , the agent reaches the home base from the other side. In case $(a)$ the two remaining agents execute the cautious walk to locate the black hole. In case $(b)$ the three agents apply the algorithm where $n$ is known. The quadratic complexity is obtained when the black hole appears initially adjacent to the HB in the opposite direction of the exploration.

Let us now describe the algorithm assuming an unsafe home base. As before, the red parts correspond to the actions when the presence of the black hole is detected. In the first round, we spread the three agents in three consecutive nodes. Let $u_{0},u_{1},$ and $u_{2}$ be the three consecutive occupied nodes from left to right, occupied by $a_{1}$ , $a_{2}$ , and $a_{3}$ respectively. The algorithm repeats a sequence of moves while increasing the value of $i=1,2,3,\ldots$ . A given phase $i$ is split into 4 sub-phases (see Figure 6 for an illustration of the agents’ moves). The first one lasts $2i$ rounds, and sub-phases (2), (3), and (4) last one round each:

1.

In this sub-phase, $a_{3}$ performs $i-1$ moves clockwise, waits two rounds, and then performs $i-1$ moves counter-clockwise;
At the same time, $a_{1}$ moves one node counter-clockwise, stays there for $2i-2$ rounds, and then moves back one node clockwise; $a_{2}$ simply stays idle for $2i$ rounds.
2.

both $a_{2}$ and $a_{3}$ move counter-clockwise ( $a_{1}$ and $a_{2}$ becomes co-located on $u_{0}$ );
3.

$a_{2}$ moves clockwise and becomes co-located with $a_{3}$ on $u_{1}$ ;
4.

Finally, $a_{3}$ moves clockwise on $u_{2}$ . After this move, the agents are again spread on $u_{0},u_{1}$ , and $u_{2}$ . A new phase starts after incrementing $i$ ( $i$ is not incremented if the size of the ring $n$ has been discovered during the phase).

Figure 6: Illustration of agents’ moves by Algorithm

\mathcal{A}_{4}

.

In phase (1), it is possible that $a_{3}$ meets $a_{1}$ after performing its $i-1$ moves clockwise. If this happens, then both agents get to know the value of $n$ . The agents continue to execute the same algorithm keeping the same value of $i$ ( $i=n-2$ ) for all the next iterations. Observe that in the smallest ring of size $n=3$ , the value of $i$ is already equal to $n-2$ at the first phase, so the algorithm works as well for this case. Recall that for the case $n=2$ , we can run the first part of Algorithm $\mathcal{A}_{0}$ to detect the case $n=2$ and solve the problem.

By repeating these actions, the agents can detect a black hole when an agent is missing (is not co-located where she is supposed to be). Informally, if $a_{3}$ does not come back because it was killed in a black hole during the exploration of the ring, agent $a_{2}$ eventually knows it and informs $a_{1}$ to start a cautious walk. If the black hole appears on $u_{1}$ , then $a_{2}$ is eventually killed and $a_{1}$ identifies $u_{1}$ as a black hole because $a_{2}$ never comes back to $u_{0}$ . If $a_{1}$ is killed on $u_{n-1}$ , then $a_{2}$ detects it and can tell $a_{3}$ about the presence of the black hole. Finally, if the black hole kills $a_{1}$ and $a_{2}$ on $u_{0}$ , then $a_{3}$ eventually identifies the node when it sees that $a_{2}$ is not co-located on $u_{1}$ . The formal case by case analysis is given in the proof of Theorem 5.

Here, the worst case complexity occurs when the black hole is initially on node $u_{n-2}$ as it is discovered when $i=n-3$ (recall that $i=n-2$ corresponds to the case where agent $a_{3}$ meets with agent $a_{1}$ on node $u_{n-1}$ ). The number of round before reaching $i=n-3$ is asymptotically quadratic.

Theorem 5.

Assuming $n\geq 3$ (otherwise, run Algorithm $\mathcal{A}_{0}$ first), Algorithm $\mathcal{A}_{4}$ solves the EBHS problem with 3 synchronous agents with a quadratic worst-case complexity.

4 Asynchronous agents

We start by giving a simple impossibility result that explains why we only consider algorithms with implicit termination.

Theorem 6.

There is no eventually-emerging black hole search algorithm with explicit termination with asynchronous agents.

Proof.

Assume for the sake of contradiction that such an algorithm exists. Consider an execution with an initial black hole at some node $u$ . Consider the time $t$ where a surviving agent $a$ detects the black hole and explicitly terminates. Consider another execution (indistinguishable from the previous one) where node $u$ is not a black hole but all agents entering $u$ are slowed down until $t$ . In this scenario, agent $a$ wrongly detects $u$ as the black hole. Observe that this proof does not work in the case of an initial black hole, since a particular node can be isolated after all the other nodes have been checked, so that the position of the black hole can be known for sure. In our case, checking a node does not mean that this node is safe forever. $\hfill\blacktriangleleft$

One can observe that, with implicit termination, knowing $n$ is not required. This does not contradict previous results, for instance [22, 24]. For example, even with an initial black hole, it is possible to find it with implicit termination by using a simple cautious walk with two agents.

In this section, we present two algorithms: one that requires $n$ agents and one that only uses four agents with two pebbles. In both algorithms, the home base is unsafe, and in the second algorithm, $n$ is not known. The number of asynchronous rounds required for all agents to have correct suspicions is asymptotically optimal in $O(n)$ .

4.1 Algorithm $\mathcal{A}_{5}$ : $𝒏$ asynchronous agents

We propose a simple algorithm $\mathcal{A}_{5}$ that uses $n$ agents but does not require communication capabilities. The algorithm works as follows: assign one node to each agent i.e., agent $a_{i}$ is assigned to node $u_{i}$ , for $i\in[0,n-1]$ ³³3if the identifiers were in the interval $[1,k^{c}]$ , face-to-face communication would be required to assign the node. Then, each agent $a_{i}$ explores the ring back and forth by avoiding node $u_{i}$ . Also, agent $a_{i}$ always suspects node $u_{i}$ to be the black hole. Eventually, after the emergence of the black hole, all agents except one disappear. The surviving agent correctly suspects black hole’s location. We have the trivial following theorem.

Theorem 7.

For all $n\geq 2$ , Algorithm $\mathcal{A}_{5}$ solves the EBHS with $n$ asynchronous agents without communication, with a worst-case time complexity of $2n$ .

4.2 Algorithm $\mathcal{A}_{6}$ : four agents with two pebbles

Algorithm $\mathcal{A}_{6}$ solves the EBHS problem with four asynchronous agents using only two pebbles. We split the agents into two groups of two agents, each group doing a variant of the cautious walk using pebbles. The first step is to order agents $a_{1}$ and $a_{2}$ to move clockwise once; agents $a_{3}$ and $a_{4}$ stay idle until they do not see $a_{1}$ and $a_{2}$ anymore. Then, each group of agents performs a cautious walk with a pebble, as follows. One of the agents of the group, called the leader of the pair, moves in the direction of the walk and puts down a pebble to warn the other pair that they are moving in. Then the leader returns to the other agent, called the follower, so that they both move to the target node, and the leader picks up her pebble.

The two pairs of agents may be moving in the same direction or in opposite directions. Figure 8 shows the cautious move with a pebble performed by each pair of agents.

If a leader sees that there is already a pebble or another agent, when arriving on a node, then it moves back to the other agent and the pair of agents starts exploring in the opposite direction, as shown in Figure 8 and 10.

Figure 7: A cautious move with a pebble.

Figure 8: An agent discovers a pebble when arriving on a node.

Figure 9: An agent discovers another agent from the other pair when arriving on a node.

Figure 10: An agent suspects the adjacent node while waiting for the other agent to return.

While the follower of a pair waits for the leader to return, the target node is suspected, as shown in Figure 10. Observe that face-to-face communication (i.e., reading the state of the co-located agents) is still possible even in the asynchronous setting, but requires a syncing mechanism. In our variant of the cautious walk the agents use a sync variable. An agent can set a particular value when she sees a co-located agent that she was waiting for to indicate to the other agent that she can continue.

Theorem 8.

For all $n\geq 2$ , Algorithm $\mathcal{A}_{6}$ solves the EBHS problem with 4 asynchronous agents and two pebbles, with a worst-case time complexity of $5n$ .

5 Conclusion

In this work, we explored the problem of searching for an eventually-emerging black hole in a ring topology using multiple agents under various conditions. We proposed multiple deterministic algorithms for both synchronous and asynchronous settings, each making different assumptions about agent capabilities, knowledge of the network size, and available resources such as pebbles. Our results demonstrate that it is possible to efficiently locate an eventually-emerging black hole with minimal agent assumptions, though trade-offs exist between agent count, memory, and complexity.

Future work could focus on further reducing agent assumptions while maintaining optimal search complexity. Additionally, investigating strategies for handling multiple black holes or dynamic network structures could extend the applicability of these findings to more complex real-world scenarios.

References

[1] B. BALAMOHAN, P. FLOCCHINI, A. MIRI, and N. SANTORO. Time optimal algorithms for black hole search in rings. Discrete Mathematics, Algorithms and Applications, 03(04):457–471, December 2011. doi:10.1142/s1793830911001346.
[2] Balasingham Balamohan, Stefan Dobrev, Paola Flocchini, and Nicola Santoro. Exploring an unknown dangerous graph with a constant number of tokens. Theor. Comput. Sci., 610:169–181, 2016. doi:10.1016/j.tcs.2014.07.013.
[3] Adri Bhattacharya, Giuseppe F. Italiano, and Partha Sarathi Mandal. Black hole search in dynamic tori, 2024. doi:10.48550/arXiv.2402.04746.
[4] Adri Bhattacharya, Giuseppe F. Italiano, and Partha Sarathi Mandal. Searching for a black hole in a dynamic cactus. Journal of Graph Algorithms and Applications, 29(2):127–166, May 2025. doi:10.7155/jgaa.v29i2.3042.
[5] Quentin Bramas. Simulant: Mobile Entities Simulator. Software, swhId: swh:1:dir:af491d4b38ca608f7557889b24026ba58e8ac886 (visited on 2026-06-17). URL: https://github.com/Bramas/simulant, doi:10.4230/artifacts.26632.
[6] Jie Cai, Paola Flocchini, and Nicola Santoro. Decontaminating a network from a black virus. International Journal of Networking and Computing, 4(1):151–173, 2014. doi:10.15803/ijnc.4.1_151.
[7] Jérémie Chalopin, Shantanu Das, Arnaud Labourel, and Euripides Markou. Black hole search with finite automata scattered in a synchronous torus. In Distributed Computing - 25th International Symposium, DISC, volume 6950 of Lecture Notes in Computer Science, pages 432–446. Springer, 2011. doi:10.1007/978-3-642-24100-0_41.
[8] Jérémie Chalopin, Shantanu Das, Arnaud Labourel, and Euripides Markou. Tight bounds for scattered black hole search in a ring. In Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO, volume 6796 of Lecture Notes in Computer Science, pages 186–197. Springer, 2011. doi:10.1007/978-3-642-22212-2_17.
[9] Jérémie Chalopin, Shantanu Das, Arnaud Labourel, and Euripides Markou. Tight bounds for black hole search with scattered agents in synchronous rings. Theoretical Computer Science, 509:70–85, October 2013. doi:10.1016/j.tcs.2013.02.010.
[10] Colin Cooper, Ralf Klasing, and Tomasz Radzik. Searching for Black-Hole Faults in a Network Using Multiple Agents, pages 320–332. Springer Berlin Heidelberg, 2006. doi:10.1007/11945529_23.
[11] Jurek Czyzowicz, Stefan Dobrev, Rastislav Královic, Stanislav Miklík, and Dana Pardubská. Black hole search in directed graphs. In Structural Information and Communication Complexity, 16th International Colloquium, SIROCCO, volume 5869 of Lecture Notes in Computer Science, pages 182–194. Springer, 2009. doi:10.1007/978-3-642-11476-2_15.
[12] Jurek Czyzowicz, Dariusz R. Kowalski, Euripides Markou, and Andrzej Pelc. Searching for a black hole in tree networks. In Principles of Distributed Systems, 8th International Conference, OPODIS, volume 3544 of Lecture Notes in Computer Science, pages 67–80. Springer, 2004. doi:10.1007/11516798_5.
[13] Jurek Czyzowicz, Dariusz R. Kowalski, Euripides Markou, and Andrzej Pelc. Searching for a black hole in synchronous tree networks. Comb. Probab. Comput., 16(4):595–619, 2007. doi:10.1017/S0963548306008133.
[14] S. Dobrev, P. Flocchini, R. Královič, P. Ružička, G. Prencipe, and N. Santoro. Black hole search in common interconnection networks. Networks, 47(2):61–71, January 2006. doi:10.1002/net.20095.
[15] Stefan Dobrev, Paola Flocchini, Rastislav Kralovic, Giuseppe Prencipe, Peter Ruzicka, and Nicola Santoro. Black hole search by mobile agents in hypercubes and related networks. In Procedings of the 6th International Conference on Principles of Distributed Systems. OPODIS, volume 3 of Studia Informatica Universalis, pages 169–180, 2002.
[16] Stefan Dobrev, Paola Flocchini, Rastislav Královič, and Nicola Santoro. Exploring an unknown dangerous graph using tokens. Theoretical Computer Science, 472:28–45, February 2013. doi:10.1016/j.tcs.2012.11.022.
[17] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Mobile search for a black hole in an anonymous ring. In Distributed Computing, 15th International Conference, DISC 2001, Lisbon, Portugal, October 3-5, 2001, Proceedings, volume 2180 of Lecture Notes in Computer Science, pages 166–179. Springer, 2001. doi:10.1007/3-540-45414-4_12.
[18] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Searching for a black hole in arbitrary networks: optimal mobile agent protocols. In Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, PODC, pages 153–161. ACM, 2002. doi:10.1145/571825.571853.
[19] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Multiple agents rendezvous in a ring in spite of a black hole. In Marina Papatriantafilou and Philippe Hunel, editors, Principles of Distributed Systems, 7th International Conference, OPODIS, volume 3144 of Lecture Notes in Computer Science, pages 34–46. Springer, 2003. doi:10.1007/978-3-540-27860-3_6.
[20] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Searching for a black hole in arbitrary networks: optimal mobile agents protocols. Distributed Comput., 19(1):1–35, 2006. doi:10.1007/s00446-006-0154-y.
[21] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Searching for a black hole in arbitrary networks: optimal mobile agents protocols. Distributed Comput., 19(1):1–35, 2006. doi:10.1007/S00446-006-0154-Y.
[22] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Mobile search for a black hole in an anonymous ring. Algorithmica, 48(1):67–90, 2007. doi:10.1007/s00453-006-1232-z.
[23] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Asynchronous gathering in a dangerous ring. Algorithms, 16(5):222, April 2023. doi:10.3390/a16050222.
[24] Stefan Dobrev, Rastislav Kralovic, Nicola Santoro, and Wei Shi. Black hole search in asynchronous rings using tokens. In Algorithms and Complexity, 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings, volume 3998 of Lecture Notes in Computer Science, pages 139–150. Springer, 2006. doi:10.1007/11758471_16.
[25] Stefan Dobrev, Nicola Santoro, and Wei Shi. Locating a Black Hole in an Un-oriented Ring Using Tokens: The Case of Scattered Agents, pages 608–617. Springer Berlin Heidelberg, 2007. doi:10.1007/978-3-540-74466-5_64.
[26] Mattia D’Emidio, Daniele Frigioni, and Alfredo Navarra. Exploring and Making Safe Dangerous Networks Using Mobile Entities, pages 136–147. Springer Berlin Heidelberg, 2013. doi:10.1007/978-3-642-39247-4_12.
[27] Paola Flocchini, Matthew Kellett, Peter C. Mason, and Nicola Santoro. Searching for black holes in subways. Theory of Computing Systems, 50(1):158–184, July 2011. doi:10.1007/s00224-011-9341-8.
[28] Paola Flocchini, Matthew Kellett, Peter C. Mason, and Nicola Santoro. Fault-Tolerant Exploration of an Unknown Dangerous Graph by Scattered Agents, pages 299–313. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-33536-5_30.
[29] Paola Flocchini, Matthew Kellett, Peter C. Mason, and Nicola Santoro. Finding Good Coffee in Paris, pages 154–165. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-30347-0_17.
[30] Pritam Goswami, Adri Bhattacharya, Raja Das, and Partha Sarathi Mandal. Perpetual Exploration of a Ring in Presence of Byzantine Black Hole. In Silvia Bonomi, Letterio Galletta, Etienne Rivière, and Valerio Schiavoni, editors, 28th International Conference on Principles of Distributed Systems (OPODIS 2024), volume 324 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:17, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2024.17.
[31] Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco. Hardness and Approximation Results for Black Hole Search in Arbitrary Graphs, pages 200–215. Springer Berlin Heidelberg, 2005. doi:10.1007/11429647_17.
[32] Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco. Hardness and approximation results for black hole search in arbitrary networks. Theoretical Computer Science, 384(2–3):201–221, October 2007. doi:10.1016/j.tcs.2007.04.024.
[33] Adrian Kosowski, Alfredo Navarra, and Cristina M. Pinotti. Synchronization Helps Robots to Detect Black Holes in Directed Graphs, pages 86–98. Springer Berlin Heidelberg, 2009. doi:10.1007/978-3-642-10877-8_9.
[34] Giuseppe Antonio Di Luna, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Black hole search in dynamic rings: The scattered case. In Alysson Bessani, Xavier Défago, Junya Nakamura, Koichi Wada, and Yukiko Yamauchi, editors, 27th International Conference on Principles of Distributed Systems, OPODIS 2023, December 6-8, 2023, Tokyo, Japan, volume 286 of LIPIcs, pages 33:1–33:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.OPODIS.2023.33.
[35] Giuseppe Antonio Di Luna, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Locating a black hole in a dynamic ring. J. Parallel Distributed Comput., 196:104998, 2025. doi:10.1016/J.JPDC.2024.104998.
[36] Euripides Markou and Michel Paquette. Black Hole Search and Exploration in Unoriented Tori with Synchronous Scattered Finite Automata, pages 239–253. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-35476-2_17.
[37] Jaydip Sen, M. Girish Chandra, S.G. Harihara, Harish Reddy, and P. Balamuralidhar. A mechanism for detection of gray hole attack in mobile ad hoc networks. In 2007 6th International Conference on Information, Communications & Signal Processing, pages 1–5. IEEE, 2007. doi:10.1109/icics.2007.4449664.

[bib.bib1] [1] B. BALAMOHAN, P. FLOCCHINI, A. MIRI, and N. SANTORO. Time optimal algorithms for black hole search in rings. Discrete Mathematics, Algorithms and Applications, 03(04):457–471, December 2011. doi:10.1142/s1793830911001346.

[bib.bib2] [2] Balasingham Balamohan, Stefan Dobrev, Paola Flocchini, and Nicola Santoro. Exploring an unknown dangerous graph with a constant number of tokens. Theor. Comput. Sci., 610:169–181, 2016. doi:10.1016/j.tcs.2014.07.013.

[bib.bib3] [3] Adri Bhattacharya, Giuseppe F. Italiano, and Partha Sarathi Mandal. Black hole search in dynamic tori, 2024. doi:10.48550/arXiv.2402.04746.

[bib.bib4] [4] Adri Bhattacharya, Giuseppe F. Italiano, and Partha Sarathi Mandal. Searching for a black hole in a dynamic cactus. Journal of Graph Algorithms and Applications, 29(2):127–166, May 2025. doi:10.7155/jgaa.v29i2.3042.

[bib.bib5] [5] Quentin Bramas. Simulant: Mobile Entities Simulator. Software, swhId: swh:1:dir:af491d4b38ca608f7557889b24026ba58e8ac886 (visited on 2026-06-17). URL: https://github.com/Bramas/simulant, doi:10.4230/artifacts.26632.

[bib.bib6] [6] Jie Cai, Paola Flocchini, and Nicola Santoro. Decontaminating a network from a black virus. International Journal of Networking and Computing, 4(1):151–173, 2014. doi:10.15803/ijnc.4.1_151.

[bib.bib7] [7] Jérémie Chalopin, Shantanu Das, Arnaud Labourel, and Euripides Markou. Black hole search with finite automata scattered in a synchronous torus. In Distributed Computing - 25th International Symposium, DISC, volume 6950 of Lecture Notes in Computer Science, pages 432–446. Springer, 2011. doi:10.1007/978-3-642-24100-0_41.

[bib.bib8] [8] Jérémie Chalopin, Shantanu Das, Arnaud Labourel, and Euripides Markou. Tight bounds for scattered black hole search in a ring. In Structural Information and Communication Complexity - 18th International Colloquium, SIROCCO, volume 6796 of Lecture Notes in Computer Science, pages 186–197. Springer, 2011. doi:10.1007/978-3-642-22212-2_17.

[bib.bib9] [9] Jérémie Chalopin, Shantanu Das, Arnaud Labourel, and Euripides Markou. Tight bounds for black hole search with scattered agents in synchronous rings. Theoretical Computer Science, 509:70–85, October 2013. doi:10.1016/j.tcs.2013.02.010.

[bib.bib10] [10] Colin Cooper, Ralf Klasing, and Tomasz Radzik. Searching for Black-Hole Faults in a Network Using Multiple Agents, pages 320–332. Springer Berlin Heidelberg, 2006. doi:10.1007/11945529_23.

[bib.bib11] [11] Jurek Czyzowicz, Stefan Dobrev, Rastislav Královic, Stanislav Miklík, and Dana Pardubská. Black hole search in directed graphs. In Structural Information and Communication Complexity, 16th International Colloquium, SIROCCO, volume 5869 of Lecture Notes in Computer Science, pages 182–194. Springer, 2009. doi:10.1007/978-3-642-11476-2_15.

[bib.bib12] [12] Jurek Czyzowicz, Dariusz R. Kowalski, Euripides Markou, and Andrzej Pelc. Searching for a black hole in tree networks. In Principles of Distributed Systems, 8th International Conference, OPODIS, volume 3544 of Lecture Notes in Computer Science, pages 67–80. Springer, 2004. doi:10.1007/11516798_5.

[bib.bib13] [13] Jurek Czyzowicz, Dariusz R. Kowalski, Euripides Markou, and Andrzej Pelc. Searching for a black hole in synchronous tree networks. Comb. Probab. Comput., 16(4):595–619, 2007. doi:10.1017/S0963548306008133.

[bib.bib14] [14] S. Dobrev, P. Flocchini, R. Královič, P. Ružička, G. Prencipe, and N. Santoro. Black hole search in common interconnection networks. Networks, 47(2):61–71, January 2006. doi:10.1002/net.20095.

[bib.bib15] [15] Stefan Dobrev, Paola Flocchini, Rastislav Kralovic, Giuseppe Prencipe, Peter Ruzicka, and Nicola Santoro. Black hole search by mobile agents in hypercubes and related networks. In Procedings of the 6th International Conference on Principles of Distributed Systems. OPODIS, volume 3 of Studia Informatica Universalis, pages 169–180, 2002.

[bib.bib16] [16] Stefan Dobrev, Paola Flocchini, Rastislav Královič, and Nicola Santoro. Exploring an unknown dangerous graph using tokens. Theoretical Computer Science, 472:28–45, February 2013. doi:10.1016/j.tcs.2012.11.022.

[bib.bib17] [17] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Mobile search for a black hole in an anonymous ring. In Distributed Computing, 15th International Conference, DISC 2001, Lisbon, Portugal, October 3-5, 2001, Proceedings, volume 2180 of Lecture Notes in Computer Science, pages 166–179. Springer, 2001. doi:10.1007/3-540-45414-4_12.

[bib.bib18] [18] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Searching for a black hole in arbitrary networks: optimal mobile agent protocols. In Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, PODC, pages 153–161. ACM, 2002. doi:10.1145/571825.571853.

[bib.bib19] [19] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Multiple agents rendezvous in a ring in spite of a black hole. In Marina Papatriantafilou and Philippe Hunel, editors, Principles of Distributed Systems, 7th International Conference, OPODIS, volume 3144 of Lecture Notes in Computer Science, pages 34–46. Springer, 2003. doi:10.1007/978-3-540-27860-3_6.

[bib.bib20] [20] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Searching for a black hole in arbitrary networks: optimal mobile agents protocols. Distributed Comput., 19(1):1–35, 2006. doi:10.1007/s00446-006-0154-y.

[bib.bib21] [21] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Searching for a black hole in arbitrary networks: optimal mobile agents protocols. Distributed Comput., 19(1):1–35, 2006. doi:10.1007/S00446-006-0154-Y.

[bib.bib22] [22] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Mobile search for a black hole in an anonymous ring. Algorithmica, 48(1):67–90, 2007. doi:10.1007/s00453-006-1232-z.

[bib.bib23] [23] Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Asynchronous gathering in a dangerous ring. Algorithms, 16(5):222, April 2023. doi:10.3390/a16050222.

[bib.bib24] [24] Stefan Dobrev, Rastislav Kralovic, Nicola Santoro, and Wei Shi. Black hole search in asynchronous rings using tokens. In Algorithms and Complexity, 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings, volume 3998 of Lecture Notes in Computer Science, pages 139–150. Springer, 2006. doi:10.1007/11758471_16.

[bib.bib25] [25] Stefan Dobrev, Nicola Santoro, and Wei Shi. Locating a Black Hole in an Un-oriented Ring Using Tokens: The Case of Scattered Agents, pages 608–617. Springer Berlin Heidelberg, 2007. doi:10.1007/978-3-540-74466-5_64.

[bib.bib26] [26] Mattia D’Emidio, Daniele Frigioni, and Alfredo Navarra. Exploring and Making Safe Dangerous Networks Using Mobile Entities, pages 136–147. Springer Berlin Heidelberg, 2013. doi:10.1007/978-3-642-39247-4_12.

[bib.bib27] [27] Paola Flocchini, Matthew Kellett, Peter C. Mason, and Nicola Santoro. Searching for black holes in subways. Theory of Computing Systems, 50(1):158–184, July 2011. doi:10.1007/s00224-011-9341-8.

[bib.bib28] [28] Paola Flocchini, Matthew Kellett, Peter C. Mason, and Nicola Santoro. Fault-Tolerant Exploration of an Unknown Dangerous Graph by Scattered Agents, pages 299–313. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-33536-5_30.

[bib.bib29] [29] Paola Flocchini, Matthew Kellett, Peter C. Mason, and Nicola Santoro. Finding Good Coffee in Paris, pages 154–165. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-30347-0_17.

[bib.bib30] [30] Pritam Goswami, Adri Bhattacharya, Raja Das, and Partha Sarathi Mandal. Perpetual Exploration of a Ring in Presence of Byzantine Black Hole. In Silvia Bonomi, Letterio Galletta, Etienne Rivière, and Valerio Schiavoni, editors, 28th International Conference on Principles of Distributed Systems (OPODIS 2024), volume 324 of Leibniz International Proceedings in Informatics (LIPIcs), pages 17:1–17:17, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.OPODIS.2024.17.

[bib.bib31] [31] Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco. Hardness and Approximation Results for Black Hole Search in Arbitrary Graphs, pages 200–215. Springer Berlin Heidelberg, 2005. doi:10.1007/11429647_17.

[bib.bib32] [32] Ralf Klasing, Euripides Markou, Tomasz Radzik, and Fabiano Sarracco. Hardness and approximation results for black hole search in arbitrary networks. Theoretical Computer Science, 384(2–3):201–221, October 2007. doi:10.1016/j.tcs.2007.04.024.

[bib.bib33] [33] Adrian Kosowski, Alfredo Navarra, and Cristina M. Pinotti. Synchronization Helps Robots to Detect Black Holes in Directed Graphs, pages 86–98. Springer Berlin Heidelberg, 2009. doi:10.1007/978-3-642-10877-8_9.

[bib.bib34] [34] Giuseppe Antonio Di Luna, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Black hole search in dynamic rings: The scattered case. In Alysson Bessani, Xavier Défago, Junya Nakamura, Koichi Wada, and Yukiko Yamauchi, editors, 27th International Conference on Principles of Distributed Systems, OPODIS 2023, December 6-8, 2023, Tokyo, Japan, volume 286 of LIPIcs, pages 33:1–33:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023. doi:10.4230/LIPIcs.OPODIS.2023.33.

[bib.bib35] [35] Giuseppe Antonio Di Luna, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Locating a black hole in a dynamic ring. J. Parallel Distributed Comput., 196:104998, 2025. doi:10.1016/J.JPDC.2024.104998.

[bib.bib36] [36] Euripides Markou and Michel Paquette. Black Hole Search and Exploration in Unoriented Tori with Synchronous Scattered Finite Automata, pages 239–253. Springer Berlin Heidelberg, 2012. doi:10.1007/978-3-642-35476-2_17.

[bib.bib37] [37] Jaydip Sen, M. Girish Chandra, S.G. Harihara, Harish Reddy, and P. Balamuralidhar. A mechanism for detection of gray hole attack in mobile ad hoc networks. In 2007 6th International Conference on Information, Communications & Signal Processing, pages 1–5. IEEE, 2007. doi:10.1109/icics.2007.4449664.

Searching for an Eventually-Emerging Black Hole in Rings

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Supplementary Material:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Related Work

Contributions

2 Model

Scheduler

Eventually-emerging black hole

The Eventually-emerging black hole search (EBHS) problem

Complexity

3 Synchronous agents

Handling small rings (𝒏∈{𝟐,𝟑,𝟒})

Cautious walk

Impossibility with two agents

Theorem 1.

Proof.

3.1 Algorithm 𝓐𝟏: Four Agents

Theorem 2.

3.2 Algorithm 𝓐𝟐: with one pebble

Theorem 3.

Proof.

3.3 Algorithm 𝓐𝟑: when 𝒏 is known

Theorem 4.

Proof.

3.4 Algorithm 𝓐𝟒: with quadratic complexity

Theorem 5.

4 Asynchronous agents

Theorem 6.

Proof.

4.1 Algorithm 𝓐𝟓: 𝒏 asynchronous agents

Theorem 7.

4.2 Algorithm 𝓐𝟔: four agents with two pebbles

Theorem 8.

5 Conclusion

References

Searching for an Eventually-Emerging
Black Hole in Rings

Handling small rings ( $n\in\{2,3,4\}$ )

3.1 Algorithm $\mathcal{A}_{1}$ : Four Agents

3.2 Algorithm $\mathcal{A}_{2}$ : with one pebble

3.3 Algorithm $\mathcal{A}_{3}$ : when $𝒏$ is known

3.4 Algorithm $\mathcal{A}_{4}$ : with quadratic complexity

4.1 Algorithm $\mathcal{A}_{5}$ : $𝒏$ asynchronous agents

4.2 Algorithm $\mathcal{A}_{6}$ : four agents with two pebbles