Don’t Be Afraid to Die: Black Hole Search in Dynamic Graphs with Fewer Agents⋆ Kass Bileski and Avery Miller[0000−0002−8231−3697]
arXiv:2609.06850v1 [cs.DC] 6 Sep 2026
University of Manitoba, Winnipeg MB, Canada [email protected], [email protected]
Abstract. We consider a team of synchronous mobile agents operating in a port-labeled network. There is one node in the network called a black hole that permanently destroys any agent that visits the node. The team of agents must safely locate the black hole, i.e., at least one agent must survive, terminate its algorithm at a node adjacent to the black hole, and output the port number that leads to the black hole from its current position. In the setting where the network is a 1-bounded 1-interval connected dynamic graph, previous work [19] showed that a team consisting of 2δBH + 17 agents is sufficient to solve the task from a scattered configuration, where δBH denotes the degree of the black hole node. We show that 2δBH + 3 agents are sufficient, nearly matching the 2δBH + 1 lower bound provided in [20]. Keywords: black hole search · dynamic graphs · distributed algorithms.
Security is a significant concern in distributed systems. One kind of security hazard is a site attack : a malicious entity has compromised a node in a distributed system, and has perhaps changed the node’s behaviour as to inhibit or destroy functionality, information, or entities. Once we have suspected that some node in a system has been compromised, the first step towards dealing with the hazard is to locate it. The Black Hole Search (BHS) problem abstractly models this task: a network or a network-like environment is represented using a graph in which one node is a “black hole” that immediately destroys any mobile entity that visits it. The goal of the problem is to employ a team of mobile agents to find the location of the black hole in a distributed way, i.e., each agent is independently executing a copy of the algorithm rather than having a central entity that can control and monitor all of the agents. This goal is complicated by the fact that an agent that finds the black hole is not able to report its location (since the agent has been destroyed) so the actual requirement is that at least one agent must correctly deduce the location of a node that is adjacent to the black hole, as well as the incident edge that leads to the black hole. As a potential practical setting, the mobile agents might be a group of software agents that must search a network to locate a dangerous virus that has ⋆
This work was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery Grant RGPIN-2024-06411.
2
K. Bileski and A. Miller
infected one of the network nodes. As another example, the graph might represent a map of an environment in which robots or self-driving cars move around, and the attack might come in the form of a person intercepting and deactivating the robots/cars at some particular location. In this work, we create a deterministic distributed mobile agent algorithm that solves BHS in environments where the network edges (on which the agents travel) are not reliable. Such environments complicate the task of deducing the location of the black hole because if one agent a sees that another agent b has traversed a link but does not return, agent a cannot immediately know for certain whether this was due to agent b visiting the black hole or due to the link disappearing. Regarding efficiency, our main goal is to minimize the number of mobile agents in the team, but we also want the agents to find the black hole relatively quickly, e.g., in polynomial time with respect to the network size.
1
Preliminaries
1.1
The Model and the Problem
The setting is a dynamic network, modeled as a time-varying graph G. There is a static underlying simple graph G = (V, E) where V is a fixed set of n nodes and E is a fixed set of m undirected edges. Each node is anonymous, and at each node v, its incident edges have been labeled with distinct port numbers from the range {0, . . . , deg(v) − 1}. The port numbers at the endpoints of an edge may be the same or differ arbitrarily. There is one special node in G called the black hole, and the degree of this node in the underlying graph is denoted by δBH . All nodes other than the black hole are called safe. Time proceeds in synchronous rounds, starting with round 0, and for each integer t ≥ 0, the snapshot Gt represents the state of the graph during round t. We restrict G to be a 1-bounded 1-interval connected graph: each Gt is connected and can be obtained from the underlying graph G by removing at most one edge. Each edge in Gt is said to be active in round t, and otherwise an edge is said to be inactive in round t. In each round, at most one edge is inactive. We consider a team of k mobile agents that act in a synchronous, distributed way. Each agent possesses a unique integer identifier, and we assume that this identifier comes from the range {1, . . . , nc } for some fixed positive constant c. Each agent knows its own identifier, but does not initially know the value of c, k, or any other property of the graph. Each agent is equipped with O(log n) bits of memory. In addition to this internal memory possessed by each agent, there is also external memory: at each node v in the network, there is a whiteboard wbv that can store O(log n) bits of information, and this information can be written and read by any agent that is located at the node. Initially, i.e., in round 0, the agents are in a scattered configuration: each agent is located at a safe node in G, and each safe node in G may contain 0 or more agents. Essentially, other than the fact that no agent starts at the black hole, we assume that the initial configuration is arbitrary, in contrast to a rooted configuration in which all agents start at the same safe node.
Black Hole Search in Dynamic Graphs with Fewer Agents
3
At the start of each round t, each agent a that has not yet been destroyed by the black hole is located at some node v ∈ V . If the agent has not terminated its execution before round t, then it performs a Look-Compute-Move (LCM) cycle in round t, i.e., it performs the following phases in the following order: 1. Look phase: Agent a sees the degree of node v in the underlying graph G, but does not see which edges are active in the current round. Also, agent a sees all other agents co-located at v and can read the entire internal memory of each such agent. Agent a can also read the contents of the whiteboard wbv . If the agent attempted to move in round t − 1, then it learns whether or not the move was successful, i.e., whether the edge it attempted to move along was active or inactive in round t − 1. If the move was successful, the agent learns the port number at node v from which it entered v. 2. Compute phase: Based on all the information it acquired during this round’s Look phase, as well as the contents of its own memory, agent a deterministically decides which action it will take in the Move phase of the current round t: move, wait, or terminate. We place no computational restrictions on agent a’s decision-making. If it decides to move, it computes the port number at v of the edge that it will attempt to move along. Agent a may also modify the contents of the whiteboard wbv during this phase. 3. Move phase: If, during the Compute phase, the agent a decided that it will attempt to move using some port p, then the agent now attempts to move along the incident edge corresponding to the port p at node v. If the edge {v, u} corresponding to p is active in the current round t, and node u is a safe node, then agent a will be located at u at the start of round t + 1; otherwise, if u is the black hole, then agent a is immediately destroyed and does not appear at any node from the start of round t + 1 onward. If the edge {v, u} is inactive in round t, or, the agent decided to wait or terminate, then the agent will be located at node v at the start of round t + 1. We study the task of locating the black hole node in G, defined as follows. Definition 1 (Black Hole Search in 1-bounded 1-interval connected time-varying graphs (1-BHS)). Let G = G0 , G1 , . . . be a 1-bounded 1-interval connected time-varying graph with underlying graph G such that exactly one node vBH in G is designated as the black hole. A team of k ≥ 1 mobile agents starts in a scattered configuration in round 0. To solve the task, there must exist a round t ≥ 0 and a node u adjacent to vBH such that at least one agent a terminates its execution in round t at node u and agent a outputs the port number at u that leads to vBH . We say that this agent has reported the black hole. We create an algorithm that each agent will follow during its Compute phase in each round such that 1-BHS is solved for any G, any black hole location, and any starting configuration. We also determine an upper bound on the number of rounds that elapse before at least one agent has reported the black hole.
4
1.2
K. Bileski and A. Miller
Related Work
Black Hole Search was introduced in [10], assuming asynchronous agents in anonymous rings. Further results about Black Hole Search in static graphs under varying assumptions and graph classes appeared in [6,7,8,9,11,12,13,14,15]. For dynamic graphs, the problem was first studied for 1-bounded 1-interval connected time-varying graphs and assuming that the underlying graph belonged to specific graph classes [1,3,16,22,23]. When the underlying graph is an (a × b)torus, the authors of [4] studied Black Hole Search in (a + b)-bounded 1-interval connected time-varying graphs. Additional variants of the model and problem have been recently introduced, for example, when the black hole emerges after some unknown number of rounds [5,21], when the black hole can choose in each round whether or not a visiting agent will be destroyed [2,17], and under stronger agent capabilities such as global communication and 1-hop visibility [18]. Most relevant to our work are the previous results about Black Hole Search under the assumptions presented in Section 1.1. In [20], the authors considered the case where agents start in a rooted configuration, and provided a O(m2 )round 9-agent algorithm for 1-bounded 1-interval connected graphs. They also proved that at least 2δBH +1 agents are necessary for solving the task from every scattered initial configuration. For f -bounded 1-interval connected graphs, they provided an exponential-time algorithm using 6f agents starting in a rooted configuration, and proved that at least 2f + 2 agents are necessary (even for rooted initial configurations). In [19], the authors considered agents starting in a scattered configuration, and provided an algorithm that uses 2δBH + 17 agents. 1.3
Our Results and Approach
Consider any 1-bounded 1-interval connected time-varying graph G with underlying graph G consisting of n nodes and m edges. Exactly one node in G is designated as the black hole, whose degree in G is denoted by δBH . We provide an algorithm that solves 1-BHS using 2δBH + 3 agents, and at least one agent has reported the black hole within O(m2 · δBH ) rounds. Previous work [19] had each agent follow a depth-first search (DFS) strategy, with no two agents simultaneously using the same outgoing port at a node, and replacing each edge traversal of the DFS with several mini-steps: write the agent’s ID and its outgoing port to a whiteboard, traverse the edge, return back along the edge, delete its information from the whiteboard, then traverse the edge again. If the same outgoing port p appears twice on the same whiteboard, then it means two agents have exited the node via p and neither of them returned to erase their information. It follows that port p leads to the black hole, and any agent that sees this on a whiteboard terminates and reports the black hole. We adopt the same strategy, but we use a different approach to guarantee that some agent eventually sees such a whiteboard. In [19], if an agent attempts to traverse an edge that is inactive, it keeps trying the same edge until success, and if a large enough group of agents all become stuck trying the same port at some node, then they all simultaneously quit the current strategy and perform a
Black Hole Search in Dynamic Graphs with Fewer Agents
5
different algorithm, i.e., one designed to solve 1-BHS from a rooted configuration (i.e., in which all agents start at the same node). The key observation from [19] was that any rooted 1-BHS algorithm Arooted that works for a team of x agents can be used to create a scattered 1-BHS algorithm that works for a team of size 2δBH + 2x − 1: at most 2δBH of the agents will be destroyed, and if 2x − 1 agents become stuck trying to traverse the same inactive edge during their DFS, then at least x of them must be trying the edge from the same endpoint, and such a group successfully solves 1-BHS by switching to Arooted . In [19], they apply this observation using a 9-agent rooted 1-BHS algorithm to obtain a (2δBH + 17)agent scattered 1-BHS algorithm. In contrast, our approach is to never switch to an alternate strategy. It is based on the observation that, if 2δBH agents have already been destroyed by the black hole, then every node adjacent to the black hole has a whiteboard whose discovery immediately solves the task, so any remaining agents do not have to worry about being destroyed, i.e., they just have to solve graph exploration as if there is no black hole. Essentially, if an agent is destroyed by the black hole, they are contributing towards a future situation where the graph is safe to explore by all remaining agents. So, we create a scattered (2δBH +3)-agent 1-BHS algorithm by having all agents run a scattered graph exploration algorithm Aexplore that is designed for at least 3 agents in a 1-bounded 1-interval connected graph that has no black hole, and we observe that: if 2δBH agents haven’t been destroyed yet, then agents might visit the black hole and be destroyed; but, once 2δBH agents have been destroyed, at least one of the remaining agents running Aexplore will eventually visit a node adjacent to the black hole, see a whiteboard with the same outgoing port written twice on it, and correctly report the black hole. We emphasize that the agents do not detect when the 2δBH threshold has been reached, i.e., they run the same algorithm regardless of how many agents have been destroyed so far. The exploration algorithm Aexplore for 3 (or more) agents, similar to the one described in [20], is designed in such a way that at most two of the agents become stuck at ports trying to traverse an inactive edge (one from each endpoint) and all other agents will skip those ports. Since a 1-bounded 1interval connected time-varying graph stays connected despite an inactive edge, and at most two agents will be stuck in any round, it follows that at least one agent will make exploration progress in each round. Due to space constraints, the detailed proofs are omitted and will appear in the journal version of the paper.
2
Algorithm Description
The algorithm has several components, some of which are adapted from [19]. We describe them below along with the relevant agent variables and whiteboard variables. A summary of the variables is provided in Appendix A.
6
K. Bileski and A. Miller
2.1
Depth-First Search (DFS)
The basis of the algorithm is graph exploration, which is accomplished using a DFS. In this section, we describe how agents would carry out the search if there is no black hole and all edges are active in each round. We start by describing the single-agent version. The agent maintains an internal variable called state that keeps track of whether it is moving with the goal of discovering new nodes (a.state = explore) or it is moving back along a previously traversed edge (a.state = backtrack ). Initially, agent a begins in the explore state, and the node at which it starts the DFS is called its root node. In what follows, let v denote the agent’s current node. In the first step of the DFS, agent a writes the pair (a.ID, −1) to the DFSParent variable at wbv (the value −1 will be used later to detect when a is at its DFS root). The purpose of DFSParent at wbv is to remember where a came from when it first arrived at v so that it can later backtrack. So, after the first step of a DFS, if agent a arrives at node v at incoming port p in explore mode, and agent a hasn’t visited this node yet, then agent a writes the pair (a.ID, p) to the DFSParent variable at wbv . Next, agent a needs to decide where it will move next. The purpose of the DFSRecent variable on the whiteboard wbv is to remember how agent a exited the node the last time it was at v. There are several possible actions for agent a: – In the first step of the DFS, agent a enters explore mode, sets a.outPort = 0, writes the pair (a.ID, a.outPort) to wbv .DFSRecent, and exits v using the port a.outPort. – If a is in explore mode and wbv .DFSRecent is empty when a arrives at a node v, then a determines that this is the first time it has visited v. Denoting by inPort the incoming port that a arrived on, agent a sets a.outPort = (inPort + 1) mod δv , writes the pair (a.ID, a.outPort) to wbv .DFSRecent, stays in explore mode, and exits v using the port a.outPort. – If a is in explore mode and wbv .DFSRecent was not empty when a arrived at v, then a immediately recognizes that it has been at this node before and switches to backtrack mode. It sets a.outPort = a.inPort (i.e., goes back the way it came), and exits the node using a.outPort. – If a is in backtrack mode, then there are three subcases. Let p be the port number stored in wbv .DFSRecent. Then: • if a sees that the port number stored in wbv .DFSParent is equal to −1 and that (p + 1) mod δv is equal to 0, then a concludes that it is located at its DFS root and has explored all outgoing ports, so DFS is done. • if a sees that the port number stored in wbv .DFSParent is not −1 and not equal to (p + 1) mod δv , then there are further ports to explore from this node, so agent a sets a.outPort = (p + 1) mod δv , writes the pair (a.ID, a.outPort) to wbv .DFSRecent, switches to explore mode, and exits the node via the port a.outPort. • if a sees that the port number stored in wbv .DFSParent is equal to (p + 1) mod δv , then it means that a has explored all outgoing ports from this node, so it stays in backtrack mode, sets a.outPort = (p + 1) mod δv ,
Black Hole Search in Dynamic Graphs with Fewer Agents
7
writes the pair (a.outPort, a.ID) to wbv .DFSRecent, and exits the node via the port a.outPort. If a single agent a follows the above method of DFS on a static connected graph with no black hole, it will eventually try every port at every node in the graph, ensuring exploration of G. Next, we extend the DFS algorithm so that multiple agents can execute it starting at arbitrary nodes. If each whiteboard has unbounded memory, then each agent could execute the algorithm independently by reading and writing to its own dedicated part of each whiteboard. However, to limit the whiteboard memory to O(log n) bits, a different technique is used. At a high level, an agent performing DFS will abandon its own traversal if it ever sees DFS information written to a whiteboard by an agent with smaller ID, and instead follow that agent’s DFS traversal. In particular, at each step of each agent a’s DFS, there are two possible behaviours: we refer to the first possibility as “agent a performs its own DFS”, and we refer to the second possibility as “agent a follows another agent’s DFS”. These will be described in more detail below. To decide which of the two behaviours to perform, agent a starts each step by looking at wbv .DFSRecent at its current node v: if the ID stored in wbv .DFSRecent is smaller than agent a’s ID, then agent a abandons its own DFS and instead follows the DFS of the agent with this smaller ID (Behaviour 2); otherwise, if wbv .DFSRecent is empty, or, agent a’s ID is less than or equal to the ID stored in wbv .DFSRecent, then agent a performs its own DFS (Behaviour 1). – Behaviour 1: agent a performs its own DFS. This is nearly identical to the DFS described above for the case of a single agent. The only differences are when checking if a variable is empty or nonempty. The condition “if the variable is not empty” becomes “if the variable is storing an ID equal to a.ID”. The condition “if the variable is empty” becomes “if the variable is empty or is storing an ID strictly greater than a.ID”, and in this case agent a will overwrite the information in the variable with its own. If the agent whose information was overwritten returns to this node, it will see the DFS information belonging to a, who has a smaller ID, and it will instead follow agent a’s DFS. – Behaviour 2: agent a follows another agent’s DFS. The wbv .DFSRecent variable contains the information that a needs to know in order to follow the other agent. Agent a does not write any values to wbv .DFSRecent or wbv .DFSParent, and it exits node v using the port number stored in wbv .DFSRecent. Next, we modify the multi-agent DFS algorithm so that, if multiple agents are co-located at the same node v, then only the two agents with the two smallest IDs at v perform a step of their DFS. We will describe later how to ensure that the two agents attempt to exit the node using different ports. We want to restrict the number of agents at v that move simultaneously because, if an adjacent vertex is a black hole, we want to avoid the situation where a large number of agents are destroyed in a single step. On the other hand, we want
8
K. Bileski and A. Miller
more than one agent to attempt a move so that progress is guaranteed if one of the two agents is blocked by an inactive edge. In certain situations, we will want an agent to be able to stop or finish its execution of a DFS and start a new one. The potential issue is that, if an agent a visits a node and sees that wbv .DFSRecent contains a.ID (indicating a previous visit occurred), the agent should be able to differentiate whether the previous visit occurred during a previous DFS execution or during its current DFS. To do this, each DFS execution will be associated with its own integer: each agent a keeps an internal a.DFSnum value that it includes with wbv .DFSRecent when writing to the whiteboard, and the agent increments a.DFSnum whenever it starts a new DFS. Then, when checking a node v’s whiteboard for a previous visit, it also compares its current a.DFSnum value to what is written on the whiteboard. Further modifications to the DFS algorithm will be made in the following sections to handle the possibility of inactive edges and to enable the agents to determine the location of the black hole. 2.2
Even and Odd Rounds
In this section, we describe how we deal with the possibility of an unsuccessful edge traversal due to an inactive edge. Recall that an agent cannot detect whether an edge is active or inactive until it tries traversing the edge; instead, it gets the result of an attempted edge traversal at the start of the next round. So, our algorithm proceeds in pairs of consecutive rounds (and the first round in each pair is an even-numbered round). In each even round, the agents attempt to perform their movement. In each odd round, each agent finds out whether or not its move in the previous round was successful, and updates internal variables and whiteboard variables accordingly so that, in the next even round (i.e., the start of the next step of the algorithm), it can make decisions based on whether or not its previous attempted move was successful. 2.3
Individual Cautious Movement (ICM)
In this section, we describe how the agents will determine the location of the black hole. The agents move in a careful way and write appropriate information to the whiteboards so that, if an agent is destroyed by the black hole, it has left behind clues that allow other agents to deduce the black hole’s location. Consider an agent a at node v who wishes to perform a single step of its own DFS across an edge e = {v, u} in explore mode to reach node u. Every such DFS step will be replaced by an ICM, which consists of three stages corresponding to three movements across the edge (and recall, from the previous section, each movement starts in an even-numbered round and happens across two rounds). At the start of stage 0, agent a writes to wbv .DFSParent and wbv .DFSRecent as it would according to the DFS algorithm, however, it also writes to a whiteboard variable called wbv .marked the same values it wrote to wbv .DFSRecent (i.e., the pair (a.ID, a.outPort) consisting of a’s ID and the port it will try in this round).
Black Hole Search in Dynamic Graphs with Fewer Agents
9
The purpose of wbv .marked, which is also referred to as marked port information, is to provide a record that agent a has attempted to exit node v using a particular port (we can’t just use wbv .DFSRecent since it could be overwritten by another agent performing a DFS). At the end of stage 0, agent a attempts to move across edge e towards u. If the movement was unsuccessful due to e being inactive, then a deletes the whiteboard information that it wrote and then retries stage 0. If the movement was successful, then a recognizes that it is now at node u, sets a variable a.infoToDelete with its own ID, and it begins stage 1. In stage 1, at node u, agent a attempts to move back across e to node v. If this move is unsuccessful, then a retries stage 1 again. If the move is successful, then a sees that it is back at node v and it clears the wbv .marked variable corresponding to the ID stored in a.infoToDelete. To handle timing/concurrency issues around writing and reading whiteboards, the wbv .marked variable is cleared in the odd-numbered round of stage 1 (i.e., the whiteboard at v has been updated before agents read from it in the even-numbered round of stage 2). Agent a then begins stage 2, which is the third and final stage of the ICM. In stage 2, agent a attempts to move back across e to the node u, knowing that u is a safe node (and this time it does not write information to the whiteboard). If the movement is unsuccessful, then a retries stage 2 again. If the movement is successful, then a completes this ICM upon arrival at node u, and it has finished the DFS step. From here, agent a can start the next step of its DFS. Since several agents might have previously left a node v from different ports, and we don’t want an agent to inadvertently overwrite important clues left by them, it turns out that a single wbv .marked variable is not enough. However, six such variables are sufficient at each node v since, in any particular round: at most two agents are attempting to leave v in stage 0 of an ICM, at most two agents left marked information in the previous step and are trying to return to v in stage 1 of an ICM, and there are at most two ports from which agents might not have successfully returned to delete their marked port information (one due to the black hole, the other due to an inactive edge). We differentiate the six wbv .marked variables by appending the subscripts 1, . . . , 6. 2.4
Disperse and Ignore
In this section, we describe the main tools that will enable us to solve 1-BHS using fewer agents than in previous work. The first tool is called “disperse”. Suppose there are at least two agents at node v, let b denote the agent with smallest ID and let a denote the agent with second smallest ID. After each determines its next action according to the DFS/ICM procedures above, if both agents want to move using the same outgoing port p, then they disperse: agent b will attempt to move using outgoing port p, and, simultaneously, agent a will skip port p and continue its DFS elsewhere. Additionally, if it is the case that agent a was attempting to return to a node to delete whiteboard information, i.e., it was in ICM stage 1, then b has to remember to do this after exiting through port p on behalf of agent a, and it does so by copying over a.infoToDelete into its own b.infoToDelete. The purpose of dispersing is to avoid the situation
10
K. Bileski and A. Miller
where many agents get clumped together at the same node waiting to traverse the same edge. In particular, it follows that there can ever be at most 2 agents waiting to traverse an inactive edge (one from each endpoint), and so 3 agents performing DFS are sufficient to guarantee progress in each round. The second tool is called “ignore”. Suppose there are at least two agents at node v, let b denote the agent with smallest ID and let a denote the agent with second smallest ID. Moreover, suppose that both agents want to exit v via some port p. The agents will disperse as described in the previous paragraph, i.e., agent b will try to exit via port p and agent a will continue its DFS elsewhere. However, recall from the description of multi-agent DFS in Section 2.1 that, if agent a ever sees agent b’s information on a whiteboard, agent a will abandon its DFS and follow agent b because agent b’s ID is smaller. This could result in agent a getting stuck in a (possibly infinite) loop: suppose agent b is repeatedly trying an inactive edge at node v, agent a disperses to continue its DFS elsewhere, sees agent b’s information on a whiteboard and abandons its DFS to follow agent b’s DFS, arrives back at node v where agent b is still stuck, and so on. The purpose of the “ignore” list is to avoid such a situation: when agent a disperses, it adds b’s ID to its personal “ignore” list. Then, we modify the multi-agent DFS procedure as follows: if a arrives at a node v and sees that wbv .DFSRecent is storing a smaller ID belonging to some agent b, then a only chooses to abandon its own DFS to follow b if b does not appear on agent a’s “ignore” list. It is important to note that we can implement this idea using two variables, a.ignore1 and a.ignore2 , since at most 2 agents can be stuck trying ports on an inactive edge, i.e., to avoid an infinite loop without progress, an agent never has to ignore more than 2 other agents. So, if both of agent a’s “ignore” variables are already set, and agent a disperses with an agent with smaller ID that a isn’t currently ignoring, then agent a overwrites its least recently modified “ignore” variable. To implement the above ideas, we use several copies of some of the variables described earlier. For example, an agent a might want to ignore two other agents and continue along its own DFS instead, so we need multiple copies of DFSParent and DFSRecent on the whiteboard for a to use. Recall that, at any node v, at most two agents will attempt to move in the same round, and each is ignoring at most two smaller agent IDs. It follows that four copies of DFSParent and DFSRecent suffice, which we differentiate by appending subscripts 1,2,3,4. 2.5
Summary of the Algorithm
We describe our algorithm using a collection of agents denoted as a1 , . . . , ak , from the point of view of some fixed arbitrary agent ai at a fixed node v. A summary of the variables can be found in Appendix A, and the detailed pseudocode can be found in Appendix B. Initially, each agent starts in explore mode in ICM stage 0. Each step of the algorithm consists of a pair of consecutive rounds, starting with an even-numbered round. In each even-numbered round, the agents execute Algorithm 2, which proceeds as follows. First, each agent checks if there are two marked port variables at v that contain the same port number p, and if so, it reports that the black
Black Hole Search in Dynamic Graphs with Fewer Agents
11
hole is reached by exiting node v using port p and terminates its execution (since the task is solved). Otherwise, the agent with smallest ID at v will attempt to move, and, if there are at least two agents at v, then the agent with the second smallest ID at v will also attempt to move. All other agents at v wait and do nothing. In the rest of the description, suppose that ai is an agent with one of the two smallest IDs at node v. At the start of the round, ai sets its inPort variable to be the port number at v from which it last entered v, or −1 if it has never traversed an edge. Starting at line 1 of Algorithm 3, agent ai proceeds to decide which outgoing port to use when attempting to move in this round, i.e., by executing Algorithm 4: (1) If ai is in explore mode and in ICM stage 0, then ai first checks whether or not it sees DFS information written on the whiteboard wbv belonging to an agent with smaller ID. (a) If ai sees DFS information belonging to an agent with smaller ID that is not in ai ’s ignore list, then ai abandons its own DFS to follow the move made by the agent with the smallest such ID, i.e., it sets ai .outPort using the port from the wbv .DFSRecentj variable that contains the smallest ID that is not in ai ’s ignore list. (b) If ai does not see DFS information belonging to an agent with smaller ID, then ai follows its own DFS execution, and there are two sub-cases: if agent ai attempted to move in the previous even-numbered round and failed due to an inactive edge, then it attempts the same actions again (i.e., it does not modify any variables); otherwise, ai sets its variables to carry out the next step of its DFS as described in Section 2.1. (2) If ai is in explore mode and in ICM stage 1, then it should attempt to move back along the edge it most recently traversed (i.e., it sets ai .outPort using ai .inPort). Moreover, it sets ai .infoToDelete = ai .ID so that, after it returns back to its previous node, it will know to delete the marked port information that it wrote there in ICM stage 0. (3) If ai is in explore mode and in ICM stage 2, then it should attempt to move back along the edge it most recently traversed (i.e., it sets ai .outPort using ai .inPort). It does not write any DFS information or marked port information in this round. (4) If ai is in backtrack mode, then ai first checks the whiteboard wbv for DFS information belonging to an agent with smaller ID. (a) If ai sees the DFS information of an agent with smaller ID that is not in ai ’s ignore list, then ai abandons its DFS to follow the agent with the smallest such ID, i.e., it switches to explore mode, sets ICM stage to 0, and sets ai .outPort using the port from the wbv .DFSRecentj that contains the smallest ID that is not in ai ’s ignore list. (b) If ai does not see DFS information belonging to an agent with smaller ID, then ai will follow its own DFS execution, and there are two sub-cases: if agent ai attempted to move in the previous even-numbered round and failed due to an inactive edge, then it just attempts the same actions again (i.e., it does not modify any of its variables); otherwise, ai sets its
12
K. Bileski and A. Miller
variables to carry out the next step of its DFS as described in Section 2.1, with one modification: in the case where ai determines that its DFS is done, it restarts DFS by incrementing ai .DFSnum and then executing the instructions given for the first DFS step. After line 1 of Algorithm 3, agent ai has chosen which port it will use in its attempt to leave node v, but then agent ai does an additional check to see if there is another co-located agent ah at v that has chosen the same outgoing port p for the current round. If this is the case, then the two agents disperse, as described in Algorithm 8: (1) If ai .ID < ah .ID, then ai will continue as planned, i.e., it will attempt to exit v using port p. However, it also checks if agent ah is in stage 1 of an ICM, and if so, ai sets its own ai .infoToDelete variable to the value stored in ah .infoToDelete (and ah clears its own infoToDelete). (2) If ai .ID > ah .ID, then ai does not continue as planned, i.e., it will change its ai .outPort value before attempting to move. This change depends on various cases, as described in Algorithm 7: (i) If ai is in explore mode and not in ICM stage 1, then ai performs Algorithm 7: it skips over port p in its DFS by incrementing its outPort modulo the degree of v. This is sufficient in most cases, however, there are two special situations after performing the increment: (a) if outPort is now pointing to v’s parent in ai ’s DFS, then switch to backtrack mode; (b) if v is the root node of ai ’s DFS (i.e., its parent port is set to −1) and outPort is now 0, then ai has completed its DFS and should start a new one (it does this according to Algorithm 11: increment its DFSnum, set its inPort to −1, and write this information to wbv .DFSParent). (ii) If ai is in backtrack mode, or, in ICM stage 1 of explore mode, then notice that ai is trying to leave v to return to a specific node u and continue its DFS exploration from u. However, dispersing means that ai cannot return to node u, so instead, it just starts a new DFS with node v as its root. In particular, it executes Algorithm 11: it increments its DFSnum, sets its inPort to −1, writes this information to wbv .DFSParent, and sets its outPort to 0. There is one edge case to check: it is possible that ah also wants to leave using port 0, and in that case, agent ai ’s DFS will start at port 1 instead (see lines 18-19 of Algorithm 8). Moreover, in Case (2), ai also sets its least-recently modified ignore variable to ah .ID, as described in Algorithm 9. Finally, agent ai attempts to exit node v by moving through its chosen outgoing port, and this ends the description of the even-numbered round of the current algorithm step. In the odd-numbered round that immediately follows, agent ai executes Algorithm 13, which begins by checking whether or not the move it attempted in the previous round was successful. If the move was unsuccessful, then ai deletes all the whiteboard information that it wrote to wbv in the previous round (since,
Black Hole Search in Dynamic Graphs with Fewer Agents
13
in the next even-numbered round, it will retry the move and rewrite the information). If the move was successful, then if ai was performing an ICM (i.e., ai is in explore mode), then ai increments its ICMstage variable. Moreover, if ai is carrying information that should be deleted from the whiteboard at the node it has arrived at (i.e., if ai .infoToDelete is not empty), then ai performs the deletion during the current round. Doing this in the current odd-numbered round ensures that the information is deleted when agents read the whiteboard in the next even-numbered round.
3
Algorithm Analysis
In what follows, we use the term marked port information variables to refer to the wbv .markedq whiteboard variables for q ∈ {1, . . . , 6}. The first set of claims discuss the marked port information variables at each node v. The first result shows that most of these variables are immediately cleared, i.e., even if 3 or more of the markedq variables at v contain values at the start of some even-numbered round t, each will be cleared in round t + 1 except for perhaps two of them due to agents unable to return to v in round t: a markedq variable containing a port leading directly to the black hole, or, a markedq variable containing a port of an edge that is inactive during round t. Lemma 1. Consider any even-numbered round t and any node v. Suppose that there is a collection S of at least two marked port information variables on v’s whiteboard that are non-empty at the start of round t. Then, at most two of the variables in S are not cleared during round t + 1. Next, we observe that at most two agents modify information on v’s whiteboard in any particular even-numbered round, since only the agents with the two smallest ID’s at v perform any actions. Moreover, if two agents write to marked port information variables, then they will not write the same port number since the Disperse method ensures that they do not try to leave v via the same port. Lemma 2. In any particular even-numbered round t at any node v, at most two agents write to marked port information variables on v’s whiteboard in round t. Moreover, if exactly two agents write to marked port information variables on v’s whiteboard in round t, then they write different port numbers to these variables. We now show that there are always enough empty marked port information variables available at v, i.e., an agent will never overwrite important information left behind by other agents. More specifically, we prove that at least two such empty variables exist at the start of each even-numbered round t, which suffices since, by Lemma 2, at most two agents will attempt to write to marked port information variables during round t. The result follows from Lemmas 1 and 2: at most two of the marked port information variables that were non-empty at the start of round t − 2 are not cleared during round t − 1, and, at most two additional variables are written during round t − 2, which implies that at most 4 of the 6 marked port variables are non-empty at the start of round t.
14
K. Bileski and A. Miller
Lemma 3. Consider any even-numbered round t and any node v. At the start of round t, at least two marked port information variables are empty at wbv . The previous result guarantees that an agent never has to overwrite marked port information that is written by another agent. This implies our next result: if an agent is destroyed as soon at it leaves a node v, the information it left behind will always be visible to other agents that visit v in the future. Lemma 4. Consider any two nodes v, w adjacent in G. Let p be the port at v that leads to node w. If w is the black hole, and an agent α exits v using p in an even-numbered round t, then agent α wrote p along with α.ID to some wbv .markedq variable in round t, and that variable is not modified after round t. For any particular port number p, it follows directly from Lemma 2 that the number of marked port information variables at v that contain p can increase by at most one in any particular even-numbered round. Since an agent terminates its algorithm if it sees two marked port information variables at v containing the same port number p, we get the following result. Lemma 5. At the end of any even-numbered round t and for any node v, there are at most two marked port information variables on v’s whiteboard that contain the same port number. Recall that δBH is the degree of the black hole node. Since each agent destroyed by the black hole permanently writes the dangerous port at a node adjacent to the black hole (Lemma 4), and, this information is written to the node at most twice (Lemma 5), it follows that at most 2δBH agents are destroyed. Lemma 6. At most 2δBH agents visit the black hole. In our algorithm, an agent reports the black hole at the start of an evennumbered round when it sees two marked port information variables containing the same port. The next result shows there are no “false positives”, i.e., if a port p at node v does not directly lead to the black hole, then at most one markedq variable at wbv contains port p. The reason is: if there is an agent (in ICM stage 0) that writes p in a second marked variable at v and its movement is successful, then there is another agent (in ICM stage 1) that simultaneously returns to v along the same edge to clear the marked variable in which it wrote p. Lemma 7. Consider any two nodes v, w adjacent in G. Let p be the port at v that leads to node w. If node w is not the black hole, then at the start of any even-numbered round t, at most one marked port information variable contains p. We will make use of an upper bound on the number of edge traversals needed by a DFS before it has visited all nodes of the graph. More specifically, if there is a large sequence of movements made by a single agent, we can conclude that it must visit all nodes in the graph. The next result bounds the number of movements in a DFS traversal by noticing that each edge {v, w} can be visited at most twice in each direction: once from v to w in explore mode and subsequently
Black Hole Search in Dynamic Graphs with Fewer Agents
15
from w to v in backtrack mode, then, once from w to v in explore mode and subsequently from v to w in backtrack mode. In our algorithm, each DFS edge traversal proceeds in three ICM stages, so 12m is an upper bound on the number of movements that an agent could make during a single DFS traversal of G. Lemma 8. In a static connected graph with m edges, one execution of DFS (without ICM) performed by a single agent requires at most 4m edge traversals. The proof of correctness and running time proceeds as follows. Consider any maximal interval I of rounds in which no agent visits the black hole or reports the black hole. Our goal is to bound the length of I by O(m2 ). After doing so, we can use Lemma 6 to bound the number of such intervals by 2δBH + 1, and then conclude that the black hole is reported within O(m2 δBH ) rounds. Let a1 denote the agent with smallest ID during I. Agent a1 either follows the DFS of a dead agent with smaller ID (in which case, a1 will die or report within 3n ≤ 3m successful movements) or it follows its own DFS (in which case, a1 will die or report within 12m successful movements). However, the fact that a1 performs at most O(m) successful movements in I does not immediately give an upper bound on the length of I, since an inactive edge can impede a1 ’s progress. To prove that I consists of at most O(m2 ) rounds, it suffices to show that, after every successful movement by a1 during I, either a1 successfully moves again within O(m) rounds, or, otherwise, an agent other than a1 is destroyed within O(m) rounds. The idea is assume that the first situation does not occur, i.e., that a fixed inactive edge e prevents a1 ’s movement for at least c · m consecutive rounds for a very large constant c, and then consider the agents a2 and a3 with second smallest and third smallest ID’s during I, respectively. Note that the graph is static and connected during these c · m consecutive rounds. Agent a2 ’s progress cannot get stalled at the same port as a1 due to our Disperse subroutine and ignore variables, so, either a2 performs a complete DFS within the c · m rounds (i.e., dies or reports the black hole), or, a2 ’s progress gets stuck at the endpoint of e opposite from a1 and remains there. In the latter case, a3 ’s progress cannot get stalled at the same port as a1 or a2 due to our Disperse subroutine and ignore variables, so a3 performs a complete DFS within the c · m rounds (i.e., dies or reports the black hole), which concludes the argument. Theorem 1. 1-BHS can be solved using 2δBH + 3 agents in O(m2 δBH ) rounds. The memory requirements follow from the fact that each agent and each whiteboard stores a constant number of variables. For variables that store nonconstant values, these values are either bounded above by the maximum agent ID (assumed to be O(nc )) or the maximum port number at a node (which is O(n)) or the running time of the algorithm (which is O(m3 ) ⊆ O(n6 )). Lemma 9. Each agent uses O(log n) bits of internal memory, and each whiteboard uses O(log n) bits of storage.
16
K. Bileski and A. Miller
References 1. Balamohan, B., Flocchini, P., Miri, A., Santoro, N.: Time optimal algorithms for black hole search in rings. Discret. Math. Algorithms Appl. 3(4), 457–472 (2011). https://doi.org/10.1142/S1793830911001346 2. Bhattacharya, A., Goswami, P., Bampas, E., Mandal, P.S.: Perpetual exploration in anonymous synchronous networks with a byzantine black hole. In: Kowalski, D.R. (ed.) 39th International Symposium on Distributed Computing, DISC 2025, Berlin, Germany, October 27-31, 2025. pp. 16:1–16:17. LIPIcs, Schloss Dagstuhl - LeibnizZentrum für Informatik (2025). https://doi.org/10.4230/LIPICS.DISC.2025.16 3. Bhattacharya, A., Italiano, G.F., Mandal, P.S.: Black hole search in dynamic tori. In: Casteigts, A., Kuhn, F. (eds.) 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, Patras, Greece, June 5-7, 2024. pp. 6:1–6:16. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2024). https://doi.org/10.4230/LIPICS.SAND.2024.6 4. Bhattacharya, A., Italiano, G.F., Mandal, P.S.: Searching for a black hole in a dynamic cactus. J. Graph Algorithms Appl. 29(2), 127–166 (2025). https://doi.org/10.7155/JGAA.V29I2.3042 5. Bonnet, F., Bramas, Q., Lamani, A.: Brief announcement: Searching for an eventually-emerging black hole in rings. In: Bonomi, S., Mandal, P.S., Robinson, P., Sharma, G., Tixeuil, S. (eds.) Stabilization, Safety, and Security of Distributed Systems - 27th International Symposium, SSS 2025, Kathmandu, Nepal, October 9-11, 2025, Proceedings. pp. 82–87. Lecture Notes in Computer Science, Springer (2025). https://doi.org/10.1007/978-3-032-11127-2“˙8 6. Czyzowicz, J., Dobrev, S., Královic, R., Miklı́k, S., Pardubská, D.: Black hole search in directed graphs. In: Kutten, S., Zerovnik, J. (eds.) Structural Information and Communication Complexity, 16th International Colloquium, SIROCCO 2009, Piran, Slovenia, May 25-27, 2009, Revised Selected Papers. pp. 182–194. Lecture Notes in Computer Science, Springer (2009). https://doi.org/10.1007/978-3-64211476-2“˙15 7. Dobrev, S., Flocchini, P., Kralovic, R., Prencipe, G., Ruzicka, P., Santoro, N.: Black hole search by mobile agents in hypercubes and related networks. In: Bui, A., Fouchal, H. (eds.) Procedings of the 6th International Conference on Principles of Distributed Systems. OPODIS 2002, Reims, France, December 11-13, 2002. pp. 169–180. Studia Informatica Universalis, Suger, Saint-Denis, rue Catulienne, France (2002) 8. Dobrev, S., Flocchini, P., Kralovic, R., Ruzicka, P., Prencipe, G., Santoro, N.: Black hole search in common interconnection networks. Networks 47(2), 61–71 (2006). https://doi.org/10.1002/NET.20095 9. Dobrev, S., Flocchini, P., Kralovic, R., Santoro, N.: Exploring an unknown graph to locate a black hole using tokens. In: Navarro, G., Bertossi, L.E., Kohayakawa, Y. (eds.) Fourth IFIP International Conference on Theoretical Computer Science (TCS 2006), IFIP 19th World Computer Congress, TC-1 Foundations of Computer Science, August 23-24, 2006, Santiago, Chile. pp. 131–150. IFIP, Springer (2006). https://doi.org/10.1007/978-0-387-34735-6“˙14 10. Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Mobile search for a black hole in an anonymous ring. In: Welch, J.L. (ed.) Distributed Computing, 15th International Conference, DISC 2001, Lisbon, Portugal, October 3-5, 2001, Proceedings. pp. 166–179. Lecture Notes in Computer Science, Springer (2001). https://doi.org/10.1007/3-540-45414-4“˙12
Black Hole Search in Dynamic Graphs with Fewer Agents
17
11. Dobrev, S., Flocchini, P., Prencipe, G., Santoro, N.: Searching for a black hole in arbitrary networks: optimal mobile agent protocols. In: Ricciardi, A. (ed.) Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, PODC 2002, Monterey, California, USA, July 21-24, 2002. pp. 153– 161. ACM (2002). https://doi.org/10.1145/571825.571853 12. Dobrev, S., Flocchini, P., Santoro, N.: Cycling through a dangerous network: A simple efficient strategy for black hole search. In: 26th IEEE International Conference on Distributed Computing Systems (ICDCS 2006), 4-7 July 2006, Lisboa, Portugal. p. 57. IEEE Computer Society (2006). https://doi.org/10.1109/ICDCS.2006.25 13. Dobrev, S., Kralovic, R., Santoro, N., Shi, W.: Black hole search in asynchronous rings using tokens. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) Algorithms and Complexity, 6th Italian Conference, CIAC 2006, Rome, Italy, May 29-31, 2006, Proceedings. pp. 139–150. Lecture Notes in Computer Science, Springer (2006). https://doi.org/10.1007/11758471“˙16 14. Dobrev, S., Santoro, N., Shi, W.: Using scattered mobile agents to locate a black hole in an un-oriented ring with tokens. Int. J. Found. Comput. Sci. 19(6), 1355– 1372 (2008). https://doi.org/10.1142/S0129054108006327 15. Flocchini, P., Ilcinkas, D., Santoro, N.: Ping pong in dangerous graphs: Optimal black hole search with pebbles. Algorithmica 62(3-4), 1006–1033 (2012). https://doi.org/10.1007/S00453-011-9496-3 16. Flocchini, P., Kellett, M., Mason, P.C., Santoro, N.: Searching for black holes in subways. Theory Comput. Syst. 50(1), 158–184 (2012). https://doi.org/10.1007/S00224-011-9341-8 17. Goswami, P., Bhattacharya, A., Das, R., Mandal, P.S.: Perpetual exploration of a ring in presence of byzantine black hole. In: Bonomi, S., Galletta, L., Rivière, E., Schiavoni, V. (eds.) 28th International Conference on Principles of Distributed Systems, OPODIS 2024, Lucca, Italy, December 11-13, 2024. pp. 17:1–17:17. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2024). https://doi.org/10.4230/LIPICS.OPODIS.2024.17 18. Kaur, T., Saxena, A.: When agents are powerful: Black hole search in timevarying graphs. In: Chatterjee, B., Kothapalli, K., Mittal, N., Natarajan, A.M., Singh, D. (eds.) Distributed Computing and Intelligent Technology - 22nd International Conference, ICDCIT 2026, Bhubaneswar, India, January 16-19, 2026, Proceedings. pp. 3–18. Lecture Notes in Computer Science, Springer (2026). https://doi.org/10.1007/978-3-032-16632-6“˙1 19. Kaur, T., Saxena, A., Mandal, P.S., Mondal, K.: Black hole search by scattered agents on time-varying dynamic graphs. In: Bonomi, S., Mandal, P.S., Robinson, P., Sharma, G., Tixeuil, S. (eds.) Stabilization, Safety, and Security of Distributed Systems - 27th International Symposium, SSS 2025, Kathmandu, Nepal, October 9-11, 2025, Proceedings. pp. 309–324. Lecture Notes in Computer Science, Springer (2025). https://doi.org/10.1007/978-3-032-11127-2“˙25 20. Kaur, T., Saxena, A., Mandal, P.S., Mondal, K.: Black hole search in dynamic graphs. In: Korman, A., Chakraborty, S., Peri, S., Boldrini, C., Robinson, P. (eds.) Proceedings of the 26th International Conference on Distributed Computing and Networking, ICDCN 2025, Hyderabad, India, January 4-7, 2025. pp. 221–230. ACM (2025). https://doi.org/10.1145/3700838.3700869 21. Kaur, T., Saxena, A., Mandal, P.S., Mondal, K.: Black hole search: Dynamics, distribution, and emergence. CoRR abs/2603.00766 (2026). https://doi.org/10.48550/ARXIV.2603.00766
18
K. Bileski and A. Miller
22. Luna, G.A.D., Flocchini, P., Prencipe, G., Santoro, N.: Black hole search in dynamic rings: The scattered case. In: Bessani, A., Défago, X., Nakamura, J., Wada, K., Yamauchi, Y. (eds.) 27th International Conference on Principles of Distributed Systems, OPODIS 2023, Tokyo, Japan, December 6-8, 2023. pp. 33:1–33:18. LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023). https://doi.org/10.4230/LIPICS.OPODIS.2023.33 23. Luna, G.A.D., Flocchini, P., Prencipe, G., Santoro, N.: Locating a black hole in a dynamic ring. J. Parallel Distributed Comput. 196, 104998 (2025). https://doi.org/10.1016/J.JPDC.2024.104998
Black Hole Search in Dynamic Graphs with Fewer Agents
A
19
Summary of Variables
Variables in each agent a’s memory Description Stores the ID of the agent a. Stores value explore or backtrack . Denotes whether a’s DFS is a.state in an explore or backtrack mode. It is initialized to explore. Stores a positive integer c to represent that ai is executing its a.DFSnum c’th DFS. A boolean variable. This will be used to remember whether the attempted action of agent a in the previous even-numbered a.success round was successful, i.e., False if an attempted edge traversal failed, and True otherwise. It is initially set to True. Stores the port number that will be used by agent a if attempting to exit its current node v in the current round, or ⊥ if it a.outPort decides to stay. Can take values from {⊥, 0, 1, ..., δv −1}, where δv is the degree of v. Stores the port used by agent a to enter the current node, or −1 a.inPort at the start of a DFS. It can take values from {−1, 0, 1, ..., δv − 1}, where δv denotes the degree of the current node v. A variable denoting which ICM stage agent a is currently in. a.ICMstage It can take the value 0, 1, or 2. Stores the ID of an agent b such that a will be responsible for deleting b’s marked port information from the whiteboard at a’s next node u. Can occur if a is in stage 1 of its ICM (in which case b = a), or, agent b was unable to return to u where a.infoToDelete it started an ICM due to a missing edge e, and agent b stops trying to return to u due to dispersing, and agent a is later able to traverse edge e to reach u. In this case, the whiteboard at u still has b’s marked port information, and a will delete it. a.ignore1 Stores the ID of an agent b such that a will not follow b’s DFS, a.ignore2 even if b.ID < a.ID. Each is initialized to ⊥. A variable that stores i ∈ {1, 2} corresponding to the least a.oldestIgnore recent ignorei variable that was set by agent a. Boolean variables used to remember whether or not an agent a.writePort a.writeRecent should write its travel information and/or marked port infora.writeParent mation to the whiteboard in the current round. Variables in each node v’s whiteboard Variable Description wbv .DFSParent1 A triple (ID, p, DFSnum). The first entry is the ID of an agent a. wbv .DFSParent2 The second entry is the port p at v from which agent a entered wbv .DFSParent3 for the first time while running its DFS. The third entry stores wbv .DFSParent4 which DFS is being executed. Initially (⊥, ⊥, ⊥). wbv .DFSRecent1 A triple (ID, p, DFSnum). The first entry is the ID of an agent a. wbv .DFSRecent2 The second entry is the most recent port at v used by agent a wbv .DFSRecent3 to continue its DFS exploration. The third entry stores which wbv .DFSRecent4 DFS is being executed. Initially (⊥, ⊥, ⊥). wbv .marked1 wbv .marked2 A pair (ID, p). The first entry is the ID of an agent a. The wbv .marked3 second entry is the port used by agent a during stage 0 of its wbv .marked4 current ICM. Initially (⊥, ⊥). wbv .marked5 wbv .marked6 Variable a.ID
20
B
K. Bileski and A. Miller
Pseudocode for Aexplore
In the pseudocode, agent ai is running the code and is located at node v. Algorithm 1: Aexplore () ai .DFSnum ← 1; evenRound ← True; 3 while true do 4 ai .inPort ← port at v corresponding to the edge that ai last used to enter node v. In round 0, this is set to −1; 5 if evenRound then 6 Execute Aeven (); 7 evenRound ← False; 8 else if not evenRound then 9 Execute Aodd (); 10 evenRound ← True; 1 2
Algorithm 2: Aeven () if ∃x, y ∈ {1, . . . , 6}, wbv .markedx .p = wbv .markedy .p then Report that the black hole is through port wbv .markedx .p; 3 Terminate; 4 else if ai .ID is smallest or second smallest among agents at v then 5 Execute MovementSetup(); 6 Execute WriteWhiteboard(); 7 Attempt to move through port ai .outPort; 1
2
Algorithm 3: MovementSetup() Execute AICM (); /* Agents have set their outPort. Now, check if two of them intend to use the same port, and if so, make them disperse. */ 2 if (∃ah ̸= ai at v such that ah .outPort = ai .outPort) then 3 Execute Disperse(ai , ah ); 1
Black Hole Search in Dynamic Graphs with Fewer Agents
Algorithm 4: AICM () ai .writePort ← False; ai .writeParent ← False; 3 ai .writeRecent ← False; 4 if ai .state = explore and ai .ICMstage = 0 then 5 j ← CheckFollow(); // check wbv for agent to follow 6 if j ̸= ⊥ then // Follow agent with smallest ID I am not ignoring 7 ai .outPort ← wbv .DFSRecentj .p; 8 ai .writePort ← True; 9 else if ai .success = True then // Follow next step of my own DFS 10 Execute ADFS ; 11 else if ai .state = explore and ai .ICMstage = 1 then 12 ai .outPort ← ai .inPort; 13 ai .infoToDelete ← ai .ID; 14 else if ai .state = explore and ai .ICMstage = 2 then 15 ai .outPort ← ai .inPort; 16 else if ai .state = backtrack then 17 j ← CheckFollow(); // check wbv for agent to follow 18 if j ̸= ⊥ then // Follow agent with smallest ID I am not ignoring 19 ai .state ← explore; 20 ai .ICMstage ← 0; 21 ai .outPort ← wbv .DFSRecentj .p; 22 ai .writePort ← True; 23 else if ai .success = True then // Follow next step of my own DFS 24 Execute ADFS ; 1 2
Algorithm 5: CheckFollow() /* Find the DFSRecent variable containing the smallest ID that is smaller than ai .ID and that ai is not ignoring. Return ⊥ if no such variable exists. */ 1 j ← ⊥; 2 foreach z ∈ {1, 2, 3, 4} do 3 IDtoCheck ← wbv .DFSRecentz .ID; 4 if ((IDtoCheck < ai .ID) and (not Ignoring(IDtoCheck)) then 5 if (j = ⊥) or (IDtoCheck < wbv .DFSRecentj .ID) then 6 j ← z; 7 return j;
21
22
K. Bileski and A. Miller
Algorithm 6: ADFS () if ai .state = explore then if not ∃j ∈ {1, 2, 3, 4} such that (ai .ID = wbv .DFSRecentj .ID) and (ai .DFSnum = wbv .DFSRecentj .DFSnum) then // my current DFS hasn’t already visited this node 3 ai .outPort ← (ai .inPort + 1) mod δv ; 4 ai .writeRecent ← True; 5 ai .writeParent ← True; 6 if outPort = inPort then // v has degree 1 and ai has got here via port 0 7 ai .state ← backtrack ; 8 else 9 ai .writePort ← True; 10 else // my current DFS has already visited this node 11 ai .state ← backtrack ; 12 ai .outPort ← ai .inPort; 13 else if ai .state = backtrack then /* prev: which DFSRecent variable stores the last port I used to exit the current node */ 14 prev ← index j such that wbv .DFSRecentj .ID = ai .ID; 15 prevPort ← wbv .DFSRecentprev .p; 16 Execute DetermineNextPort(prevPort); 17 ai .writeRecent ← True; 1
2
Algorithm 7: DetermineNextPort(prevPort) outPort ← (prevPort + 1) mod δv ; /* par: which DFSParent variable stores the port I first arrived on at this node */ 2 par ← index j such that wbv .DFSParentj .ID = ai .ID; 3 if outPort = wbv .DFSParentpar .p then // Backtracking to parent node 4 ai .state ← backtrack ; 5 else // Not backtracking to parent of this node 6 ai .state ← explore; 7 ai .ICMstage ← 0; 8 ai .writePort ← True; 9 if wbv .DFSParentj .p = −1 and outPort = 0 then // v has no parent, so DFS is done, start a new DFS 10 Execute StartDFS(); 1
Black Hole Search in Dynamic Graphs with Fewer Agents
Algorithm 8: Disperse(ai , ah ) amin ← agent at v with smallest ID; anextmin ← agent at v with second smallest ID; 3 if ai = amin then 4 if ah .state = explore and ah .ICMstage = 1 then 5 ai .infoToDelete ← ah .infoToDelete; 6 else if ai = anextmin then 7 Execute StartIgnore(ah ); 8 if (ai .state = backtrack ) or (ai .state = explore and ai .ICMstage = 1) then // start a new DFS 9 Execute StartDFS(); 10 ai .state ← explore; 11 ai .ICMstage ← 0; 12 ai .writeRecent ← True; 13 ai .writePort ← True; 14 ai .infoToDelete ← ⊥ ; // only matters in ICM stage 1 15 else // skip to the next DFS port instead of using outPort 16 Execute DetermineNextPort(outPort); 17 ai .writeRecent ← True; /* Edge case: anextmin starts a new DFS and wants to use port 0, but amin also wants to use port 0 */ 18 if (ai .outPort = 0) and (amin .outPort = 0) then 19 ai .outPort ← ai .outPort + 1; 1 2
Algorithm 9: StartIgnore(ah ) if ai .ignore1 = ⊥ then ai .ignore1 ← ah .ID; 3 else if ai .ignore2 = ⊥ then 4 ai .ignore2 ← ah .ID; 5 ai .oldestIgnore ← 1; 6 else 7 if ai .oldestIgnore = 1 then 8 ai .ignore1 ← ah .ID; 9 ai .oldestIgnore ← 2; 10 else if ai .oldestIgnore = 2 then 11 ai .ignore2 ← ah .ID; 12 ai .oldestIgnore ← 1; 1
2
Algorithm 10: Ignoring(i) 1
return (ai .ignore1 = i) or (ai .ignore2 = i);
23
24
K. Bileski and A. Miller
Algorithm 11: StartDFS() ai .inPort ← −1; ai .DFSnum ← ai .DFSnum + 1; 3 ai .writeParent ← True; 4 ai .outPort ← 0;
1 2
Algorithm 12: WriteWhiteboard() /* If 2 agents want to write to wbv , have them execute the code below one at a time, with smaller ID going first */ 1 if ai .writePort = True then /* There are at least two empty markedj variables at the start of every even round, write to one of them. */ 2 dest ← index j such that wbv .markedj .ID = ⊥; 3 wbv .markeddest .ID ← ai .ID; 4 wbv .markeddest .p ← ai .outPort; 5 if ai .writeRecent = True then /* Find a variable to write to. First, prioritize overwriting my previously written info at this node. If none, then find an empty variable. If none, then overwrite info belonging to agent with largest ID */ 6 if ∃j ∈ {1, 2, 3, 4} such that wbv .DFSRecentj .ID = ai .ID then // overwrite my previously written travel information 7 dest ← j; 8 else if ∃j ∈ {1, 2, 3, 4} such that wbv .DFSRecentj .ID = ⊥ then 9 dest ← j; 10 else 11 dest ← index j such that wbv .DFSRecentj .ID is largest; 12 wbv .DFSRecentdest .ID ← ai .ID; 13 wbv .DFSRecentdest .p ← ai .outPort; 14 wbv .DFSRecentdest .DFSnum ← ai .DFSnum; 15 if ai .writeParent = True then /* Find a variable to write to. First, prioritize overwriting my previously written info at this node. If none, then find an empty variable. If none, then overwrite info belonging to agent with largest ID */ 16 if ∃j ∈ {1, 2, 3, 4} such that wbv .DFSParentj .ID = ai .ID then 17 dest ← j; 18 else if ∃j ∈ {1, 2, 3, 4} such that wbv .DFSParentj .ID = ⊥ then 19 dest ← j; 20 else 21 dest ← index j such that wbv .DFSParentj .ID is largest; 22 wbv .DFSParentdest .ID ← ai .ID; 23 wbv .DFSParentdest .p ← ai .inPort; 24 wbv .DFSParentdest .DFSnum ← ai .DFSnum;
Black Hole Search in Dynamic Graphs with Fewer Agents
Algorithm 13: Aodd () if ai attempted to move in the previous round but failed then ai .success ← False; 3 Execute UndoWhiteboard(); 4 else 5 ai .success ← True; 6 if ai attempted to move in the previous round and succeeded then 7 if ai .state = explore then 8 ai .ICMstage ← (ai .ICMstage + 1) mod 3; 9 if ai .infoToDelete ̸= ⊥ then /* Clear some marked port information at v */ 10 Find j ∈ {1, . . . , 6} where wbv .markedj .ID = ai .infoToDelete; 11 wbv .markedj .ID ← ⊥; 12 wbv .markedj .p ← ⊥; 13 ai .infoToDelete ← ⊥; 1
2
Algorithm 14: UndoWhiteboard() if ai .writePort then mine ← index j such that wbv .markedj .ID = ai .ID; 3 wbv .markedmine .ID ← ⊥; 4 wbv .markedmine .p ← ⊥; 5 if ai .writeRecent then 6 mine ← index j such that wbv .DFSRecentj .ID = ai .ID; 7 wbv .DFSRecentmine .ID ← ⊥; 8 wbv .DFSRecentmine .p ← ⊥; 9 wbv .DFSRecentmine .DFSnum ← ⊥; 10 if ai .writeParent then 11 mine ← index j such that wbv .DFSParentj .ID = ai .ID; 12 wbv .DFSParentmine .ID ← ⊥; 13 wbv .DFSParentmine .p ← ⊥; 14 wbv .DFSParentmine .DFSnum ← ⊥; 1
2
25