Safe Exploration of Arbitrary Dynamic Dangerous Networks Caterina Feletti # School of Computer Science, Carleton University, Ottawa, Canada School of Electrical Engineering and Computer Science, University of Ottawa, Canada
Paola Flocchini # School of Electrical Engineering and Computer Science, University of Ottawa, Canada
Giuseppe Prencipe # Department of Computer Science, Università di Pisa, Italy
arXiv:2609.19845v1 [cs.DC] 17 Sep 2026
Nicola Santoro # School of Computer Science, Carleton University, Canada
Abstract Given a team of agents on the nodes of a graph-based network, the exploration problem requires each node to be visited by at least one agent. In the classical distributed setting of static networks, agents do not know the topology of the network; in the more recently investigated setting of dynamic networks, they may have prior knowledge about the graph class (e.g., trees, tori, rings) or other parameters (e.g., number of nodes). Gotoh et al. (2021) are the first to study the exploration problem of arbitrary dynamic networks, under the necessary minimal assumption that any two nodes will be connected by a temporal path infinitely often (temporal connectivity assumption). In this paper, we extend their study of exploration under temporal connectivity by considering dangerous dynamic networks, i.e., containing possibly one or more black holes. Whenever an agent enters a black hole, it will be trapped forever. The safe exploration problem requires a team to explore all the safe nodes, ensuring that at least one agent will never be trapped in a black hole. We first prove that, given the necessary (and sufficient) number of agents, a team of oblivious agents can perpetually explore the safe nodes without any prior knowledge of the network or the team, without agent or node IDs, under semi-synchronous schedulers. Then, we provide an algorithm that enables agents to safely explore the network and terminate. In this case, agents are equipped with unique IDs and persistent memory, and they know the number of safe nodes. Yet, in both cases, we prove that it is impossible for a team of agents on dynamic networks to correctly mark only the ports leading to black holes. 2012 ACM Subject Classification Theory of computation → Distributed algorithms Keywords and phrases Mobile agents, Safe exploration, Black holes, Rotor-router, Port marking
1
Introduction
Exploration of networks is a fundamental problem in the field of distributed computing by mobile agents [4]. Indeed, the possibility for a team of agents—such as mobile sensors, software agents, robots—to visit all the nodes of a network is a key preliminary subroutine in various contexts: e.g., monitoring node status, maintaining the network, patrolling, and mapping the topology of an unknown network. Unsurprisingly, the exploration problem has been broadly studied from both theoretical and practical perspectives. Notably, the theoretical research has focused on algorithmic strategies and computational limits of different models of graph-based networked systems, which can vary both for the capabilities of mobile agents and for the network features. First and foremost, the underlying graph of a network must be connected in order to be explored. Besides this trivial assumption, much attention has been devoted to the memory and communication capabilities of the agents (through pebbles, tokens, whiteboard, personal memory, zero-memory), their synchronization (fully
2
Safe Exploration of Arbitrary Dynamic Dangerous Networks
synchronous FSYNCH, semi-synchronous SSYNCH, and asynchronous ASYNCH), the graph class of the network (e.g., arbitrary finite graphs [2, 14], cactus graphs [28], trees [2, 26], infinite graphs [26]), the presence/absence of IDs or local labels (on agents, on nodes, on the ports of the nodes), and the a priori knowledge the agents have about the network (e.g., graph topology [11, 12], graph class1 , number of nodes, unknown graph [14]) and on the other agents (e.g., how many they are, their initial positions). Deviating slightly from the traditional distributed setting, some works have investigated these problems for systems composed of a single agent, thus focusing on algorithmic strategies for individual graph navigation rather than agent cooperation [2, 7, 26]. The (im)possibility of exploring a network by a team of agents depends not only on the assumptions of the model, but also on the specific type of exploration problem, which is defined by the task to be accomplished and the initial configuration from which the agents start the exploration. Agents may be assumed to start from the same node, called home base, from distinct nodes, or from an arbitrary arrangement possibly containing multiplicities (i.e., agents on the same node). Also, the number of agents may play a crucial role in the problem’s solvability. According to the task, the Perpetual Exploration problem requires each node to be visited infinitely often; instead, the Finite Exploration (a.k.a. exploration with termination) requires the agents to stop moving after each node has been visited at least once. Further termination conditions may ask the agents to become aware of the exploration termination (explicit termination [22]), or, more specifically, to gather at the same node, possibly the initial home base, and terminate. In its most general variant, the Exploration problem simply asks that each node will eventually be visited, without further requests (e.g., in [26] for infinite graphs). Thus, depending on the exploration variant, the literature has provided algorithmic solutions including interesting subroutines for mobile agents: e.g., Gathering if agents must gather at the same node, or Map Construction if the agents have to construct the map of the topology of the unknown network [5]. The majority of the work assumes agents operate on static graphs, where the edges between the nodes are always present and fixed. Although reasonable, this assumption does not capture the manifold of realistic scenarios where links between nodes may be temporarily or permanently unavailable due to failures, downtime, or link reconfigurations. For this reason, temporal graphs have been used to investigate how the possible lack of edges affects the capability of agents to explore the network [10, 11, 12, 14]. An adversary decides at any discrete time step t the snapshot of the temporal graph, i.e., which edges are actually present at time t. An edge can stop appearing forever (transient edges) or appear infinitely often (recurrent edges) after periodic or unpredictable times. However, the power of the adversary must be restricted in order to avoid any non-trivial problem from becoming unsolvable. In this regard, the minimal property that the adversary must guarantee is temporal connectivity, i.e., starting from any time t, all the pairs of nodes will be eventually connected by a temporal path, namely a journey. Yet, the literature has often considered stronger assumptions: periodic connectivity requires that snapshots appear with a periodicity p > 1, T -interval connectivity for T ≥ 1 assumes that for every window of T time steps, a connected spanning subgraph persists for all the snapshots during this period [16, 21]. A special case is the 1-interval connectivity, which thus claims that each snapshot must be connected. A further restriction on the adversary’s power is given by the ℓ-bounded assumption, which requires that at most ℓ edges may be absent from any snapshot [14].
1
The topology of a graph G defines set of vertices V (G) and edges E(G); graphs may belong to different classes according to their structural properties (e.g., planar graphs, trees, tori, hypercubes).
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro
Another type of network failure or adversary attack to be considered is the possible presence of dangerous nodes, commonly called black holes after their ability to trap and destroy every agent that enters them. Networks with black holes have been widely studied in the literature with regard to the Black Hole Search (BHS) primitive [1, 8, 17, 18, 19, 24]: given a dangerous network (i.e., with a black hole), the agents must search for its location. This paper aims to study the (perpetual and finite) exploration problem, under the combined assumptions of temporal graphs and the presence of black holes: hence the name safe exploration of dynamic dangerous networks.
1.1
Related work and contribution
Background: exploration of dynamic networks Besides the traditional aspects, the key factors in the study of the exploration problems for temporal networks are (i) the class of the underlying graph, (ii) the connectivity assumption of the temporal graph, and (iii) the a priori knowledge that agents have of the network topology and the occurrences of the edges. Indeed, some exploration problems turn out to be unsolvable under certain dynamic settings, even by increasing the power of the agents [22]. Most of the work has been done considering only specific graph classes (e.g., dynamic tori, trees, cactus, rings), under the strong 1-interval or T-interval connectivity assumptions [10, 11, 12, 14, 15, 23, 25, 27]. Among these works, both known [10, 11, 12, 25, 27] and unknown [14, 15] topologies have been considered, provided they are finite. In some works, agents may have partial knowledge of the topology, e.g., in terms of bounds on the graph size [22].
Related work: unknown and arbitrary dynamic network Gotoh et al. [14] are the first to consider the exploration of unknown finite2 temporal networks whose graph class is arbitrary. In particular, they mainly consider the perpetual exploration problem under temporally connected graphs and 1-bounded 1-interval graphs. Under these settings, they analyze the number of agents necessary and sufficient for the exploration, and provide algorithmic solutions under SSYNCH schedulers (namely, where an arbitrary subset of agents is activated at each round) and FSYNCH schedulers (namely, where all agents are activated at each round). Note that, unlike most of the existing literature, their first algorithm works under the temporal connectivity assumption, namely the minimal (i.e., less restrictive) connectivity assumption that a temporal graph must hold so that a non-trivial problem, including exploration, can be solved. Despite this very limited model, the authors propose an elegant algorithm solving perpetual exploration with oblivious agents (no personal memory) starting from arbitrary nodes3 , no IDs on agents or nodes, under SSYNCH. Each node contains a whiteboard, i.e., a local persistent memory, initially blank, whose mutually exclusive read/write access is granted to any agent when activated in the node. The edge ports are labeled with local, permanent, and arbitrary IDs; agents know from which port they have just entered a node. The algorithm exploits the well-known collaborative rotor–router mechanism [6, 20]; this mechanism was developed as a deterministic counterpart to random walks on graphs by multiple agents, extending the original single-agent use developed by Fraenkel [13]. Basically, on each node, the port labels are ordered, and a pointer is maintained
2 3
In the remainder of the paper, we will always consider finite graphs; thus, we will omit this specification. This setting is also called the scattered setting.
3
4
Safe Exploration of Arbitrary Dynamic Dangerous Networks
so that it points to the next port to be visited, following a cyclic order. As soon as an agent decides to move along an edge, it increases the value of the pointer. The authors in [14] prove that, provided a sufficient number of agents, the collaborative rotor-router mechanism enables agents to solve perpetual exploration even if edges can unpredictably disappear for an unbounded, even infinite, time.
Contribution: safe exploration In this paper, we extend the study on exploration of unknown temporal graphs by assuming that the network is dangerous, i.e., with possibly one or more black holes. Now, the challenge gets harder: not only do agents have no knowledge about the graph, and the presence of the edges is subject to an adversary, but agents must avoid being trapped in black holes before accomplishing the task. We refer to these versions of the problem as safe exploration: a team is required to (perpetually or finitely) explore all the safe nodes, ensuring that at least one agent will never be trapped in a black hole. To this aim, concurrently with the exploration task, agents try to properly mark, on the whiteboard of each node, the ports as either SAFE or DANGEROUS: the final port marking will be used by the remaining agents to continue the exploration without falling into the black holes. Indeed, port marking is a task of independent interest. As in [14], we assume that agents start from arbitrary nodes and that they are activated by SSYNCH schedulers. Under these assumptions, the classical cautious walk technique for the BHS problem—firstly described in [9]—cannot correctly identify all edges leading to black holes. In fact, the classical cautious walk assumes the static FSYNCH setting where agents start from the same node, and makes agents proceed as a group as follows: one agent plays the role of the probe and explores an edge, while the others play the role of the guards and wait for the return of the probe; if the probe does not return in the next round, the guards mark the port as dangerous. If the network is dynamic, the cautious walk requires two probes to verify a single port [19]. However, starting from a scattered configuration, there is no guarantee that two agents will gather at the same node before starting to probe the adjacent nodes. To address this issue, in the recent work [18] on BHS in 1-bounded 1-interval connected networks, the authors adopt the individual cautious walk; this version of the cautious walk works for scattered agents, but it assumes FSYNCH schedulers and uses two agents as probes for each port. The technique in [18]—recently improved in [1] to reduce the number of required agents— becomes ineffective under SSYNCH: the guard agent may wait for the probe one for an unpredictable number of rounds, thus making it impossible to distinguish from an idle or a trapped agent. We therefore formally prove that, under our setting, the problem of correctly marking all the ports is unsolvable. We therefore introduce other weaker variants of the port marking problem. Some of these variants can be solved in our setting and serve as subroutines for our agents in the safe exploration of dynamic networks. Firstly, we focus on the Safe Perpetual Exploration (SE∞ ) problem: as in [14], we assume oblivious and anonymous agents without any prior knowledge of the network, which is anonymous and arbitrary, under the temporal connectivity assumption. In this very limited setting, we provide an algorithm that adopts the collaborative rotor-router mechanism and solves SE∞ provided a sufficient number of agents. Then, we consider the Safe Finite Exploration (SE⊥ ) problem: we adapt our first algorithm in order to make agents aware of the exploration termination, propagate the information along the network, and thus terminate. To this aim, we assume agents are equipped with a unique ID and a persistent memory (notebook). The only prior knowledge
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro
5
|B|
Synch
Initial
Params
NoteB
WhiteB
AgentId
{1, f }-bounded 1-interval
1
FSYNCH
Home
✗
log n
log ∆
✓
1-bounded 1-interval
1
FSYNCH
Any
✗
log n
log n
✓
[14] Perp. Explor.
Temp. conn.
0
SSYNCH
Any
✗
✗
log ∆
✗
Safe Perp. Explor.
Temp. conn.
[0, n)
SSYNCH
Any
✗
✗
∆
✗
Safe Finite Explor.
Temp. conn.
[0, n)
SSYNCH
Any
s
n log n
n log n
✓
Problem
Network
[19] BHS [18] BHS
Table 1 Related works vs. our contribution (yellow lines). |B| is the number of black holes, s is the number of safe nodes. Notebook and whiteboard sizes are expressed in O-notation w.r.t. n (number of nodes), and ∆ (degree of the network).
they have about the network is the number of safe nodes. Compared with existing studies, we highlight the key advances of our work: Problem combination. Existing studies address the problem of exploration or the search for black holes independently. Instead, our work combines the two problems, hence the name safe exploration. Beyond its intrinsic interest, this approach is in line with the broader aim to investigate the complexity of combining two distinct problems in a single one, thereby considering more elaborate scenarios within the area of dynamic networks; Zero or multiple black holes. In both our algorithms, agents do not know a priori the number of black holes, which may be 0 up to n − 1, where n is the number of nodes. To the best of our knowledge, the literature about dangerous networks and BHS assumes the presence of exactly one black hole, with the only exception of our work and [3]; More restricted assumptions: The existing algorithms for BHS for arbitrary dynamic networks work under the {1, f }-bounded4 1-interval connectivity assumption, which is stronger than our temporal connectivity assumption; moreover, these algorithms terminate as soon as one agent has found one of the ports leading to the (unique) black hole of the network [18, 19]. In contrast, here we investigate the computational power of a team of agents in marking all the ports leading to the (zero or multiple) black holes, under the (minimal) temporal connectivity assumption. Moreover, most previous work on BHS assumes fully synchronous agents; we consider the more adversarial case of SSYNCH, where a scheduler chooses which agents are active at each round. Sub-problem(s). This work formally introduces and analyses the sub-problem Port Marking—i.e., mark the ports as SAFE or DANGEROUS—in four different versions (namely, correct, highly reliable, reliable, and weakly reliable). Beyond its independent interest, this distinction allows for comparing the computational power of agents in the context of the safe exploration problem under different settings. For example, we will prove that the impossibility of achieving correct port marking under minimal assumptions does not prevent agents from safely exploring a network; yet, we will prove that agents can achieve a highly reliable (weakly reliable, resp.) port marking while solving SE∞ (SE⊥ , resp.). Table 1 compares our contribution with the related works. Due to lack of space, some proofs, figures, and tables are provided in the appendix.
4
They consider dynamic graphs where the number of missing edges at each time can be at most 1 [18, 19] or f > 1 [19].
6
Safe Exploration of Arbitrary Dynamic Dangerous Networks
2
Preliminaries
2.1
Networks
We now describe the network type within which a team of agents operates.
Temporal graphs A temporal graph G = (G, ϱ) is a graph where the presence of edges may vary over time. So, G = (V, E) is an undirected simple finite graph with |V | = n nodes and |E| = m edges; ϱ : E × N0 → {0, 1} defines the presence (when 1) or absence (when 0) of edge e at time t, where the time domain is N0 = 0, 1, 2 . . . . We call the graph G the underlying graph of G. Note that, if ϱ = 1, then G is a common static graph. Let Et = {e ∈ E s.t. ϱ(e, t) = 1}. A temporal graph G can be written also as the infinite sequence {Gt }t∈N0 where each Gt = (V, Et ) is the snapshot of G at time t and contains only the present edges at time t. An edge e in G is called recurrent if, for any t ∈ N0 , there exists a time t′ > t such that ϱ(e, t′ ) = 1. Otherwise, (i.e., if there exists a time t ∈ N0 such that ϱ(e, t′ ) = 0 for any t′ > t), then e is called transient. A journey in G is a sequence J = ((e1 , t1 ), . . . , (ek , tk )) such that (e1 , . . . , ek ) defines a walk in G, and it holds that ti < ti+1 and ϱ(ei , ti ) = 1 for any i ∈ [1, k]. In other words, a journey defines a temporal walk for an agent on the nodes of G. We denote with J (v, w, t) the set of all the journeys from v to w starting at time t′ ≥ t. A temporal graph is temporally connected if J (v, w, t) ̸= ∅ for any pair of nodes v, w and any time t ∈ N0 . Indeed, for G to be temporally connected, the underlying graph G must be connected; yet, the connectivity of G is not sufficient to have temporal connectivity in G due to the presence of transient edges.
Nodes, edges and (sub-)ports. Given a temporal graph G = (G = (V, E), ϱ), we assume that the nodes are anonymous, i.e., without IDs. However, each node v contains a local persistent memory called whiteboard, i.e., a variable whiteboardv . This variable has R/W access in mutual exclusion, and it is initially blank. Given a node v ∈ V , we denote with E(v) ⊆ E the set of edges in G that are incident to v in G, and we denote the degree of v as δ(v) = |E(v)|. We denote with ∆(G) := ∆(G) = maxv∈V {δ(v)}. When no ambiguity occurs, we will simply use ∆. For any incident edge, v contains a port, labeled by a bijection λv : E(v) → [0, δ(v) − 1]. This labeling is fixed (i.e., it does not change), local (i.e., it can be seen only in v), and arbitrary (i.e., it has no dependencies with other elements of G). We indicate with p(v, w) the port at node v from which the edge {v, w} starts. For convenience, we will use λv (p(v, w)) in place of λv ({v, w}). We can construct the global labeling function Λ for G such that Λ(v, w) = λv (p(v, w)). We refer to G = (G = (V, E), ϱ, Λ) as a port-labeled temporal graph. Generally, an edge {v, w} ∈ E can be traveled in both senses at time t ∈ N0 , if ϱ({v, w}, t) = 1. To distinguish the two senses, we say that each edge has two channels that we denote with the ordered notation (v, w) and (w, v). Thus, for a port p(v, w), there are two sub-ports: the ingoing one pin (v, w) (i.e., the endpoint of channel (w, v)) and the outgoing one pout (v, w) (i.e., the endpoint of channel (v, w)). Note that, if {v, w} ∈ E, then p(v, w) (p(w, v), resp.) and the related sub-ports are always present in v (w, resp.) independently from the temporary presence of the edge {v, w}.
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro Dangerous networks Given a port-labeled temporal graph G = (G = (V, E), ϱ, Λ), we consider the dangerous version G = (G = (V, E), ϱ, Λ, B) where B ⊂ V represents the subset of nodes for which there exist no outgoing ports. In other words, if an agent enters a node b ∈ B, it will stay there forever (we can assume the agent is destroyed as soon as it enters b). For this reason, such nodes are called black holes. On the contrary, the nodes in V \ B are called safe nodes; they always contain both the ingoing and the outgoing sub-port for each incident edge. Extending the terminology, we will say that an edge {v, w} and the corresponding ports p(v, w) and p(w, v) are safe (dangerous, resp.) if both v and w are safe nodes (if v or w is a black hole, resp.)5 . In the remainder, we will consider a team of agents operating on a network defined as the port-labeled temporal dangerous graph G = (G = (V, E), ϱ, Λ, B). For convenience and w.l.o.g., we always assume that E does not contain any edge between black holes (such edges, in fact, will never be traveled and are irrelevant for any task on dangerous networks). Moreover, since the black holes may prevent agents from reaching some safe nodes of the graph, for exploring a temporal dangerous network G = (G = (V, E), ϱ, Λ, B) it is necessary that for each pair of nodes v, w ∈ V and any time t ∈ N0 , J (v, w, t) contains at least one journey which does not contain black holes except possibly for the endpoints v or w. In the following, we will make such an assumption6 . Temporal models. We consider a hierarchy of temporal models to analyze the computational power of agents. Given a temporally connected network G, we say that G belongs to: TRANSIENT (transient model): when ϱ allows transient edges; RECURRENT (recurrent model): when ϱ only allows recurrent edges; STATIC (static model): when ϱ = 1 (i.e., the network is static). By default, we consider the TRANSIENT model.
2.2
Agents
A team of agents is a set A = {a1 , . . . , ak } of k computational entities operating on a network G = (G, ϱ, Λ, B). Agents are externally indistinguishable. Considered settings. We will consider both the setting where agents are anonymous and the setting where each agent has an internal unique ID. Moreover, we consider both the setting where agents are oblivious (i.e., devoid of any personal persistent memory), and the setting where each agent a has a personal persistent memory, called notebook, and denoted with notebooka . Generally, agents do not have any prior knowledge of the network (graph class, topology, number of black holes, recurrent edges, etc.) or of the team (size, initial positions, etc.). We can only assume that agents know the number of safe nodes |V \ B| = s. Positions and visibility. At time 0, the agents are arranged at the center of some arbitrary nodes of G (multiplicities are allowed). During the evolution of the algorithm, each agent
5 6
For the sake of completeness, all the ports within a black hole are considered dangerous. Note that a network with |B| > 1 black holes can be seen as a network with a unique black hole to which all the dangerous edges are incident. However, in this case, we should assume that the underlying graph G contains multiple edges (since a safe node v may contain multiple dangerous ports). For consistency with the existing literature, we prefer assuming that G is simple and thus that |B| can be any.
7
8
Safe Exploration of Arbitrary Dynamic Dangerous Networks
can be located in the center of a node (denoted with ⊙), on its ingoing or outgoing sub-ports, or traveling along the present edges. An agent a has only local visibility, i.e., it can only see the content of the node v where a is located at a given time. In particular, a can see the content of the whiteboard (in mutual exclusion), the labels of the ports, how many agents there are on v, and if these agents are on some sub-ports or on the center of the node. Yet, an agent cannot see if the edge of a port is present or not at a given time. Activation in mutual exclusion. Time is divided into discrete time steps t ∈ N0 called rounds. Agents are activated by semi-synchronous schedulers (SSYNCH): at any time t ∈ N0 , an arbitrary subset of robots is activated according to the fairness condition (each agent is activated infinitely often). We can formalize a SSYNCH scheduler as a function S : N0 → 2A such that ∀a ∈ A, t ∈ N0 there exists a time t′ > t such that a ∈ S(t′ ). Since agents operate on temporal graphs whose edge presence is decided by an adversary, it is necessary to assume another “fairness” condition on agents’ activation: we assume the eventual transport condition, which states that an agent located in an outgoing port of a recurrent edge will be eventually activated when the edge is present [14, 22]. Within each round, the activated robots perform each one a Look-Compute-Move (LCM) cycle. Since in the Look and Compute steps agents read and write on the whiteboard, and the access to the whiteboard is in mutual exclusion, we can describe the sequential access to the whiteboard at round t as a nested level of scheduling within each S(t). So, we define Sk S : N0 → i=1 P erm(A, i) where P erm(S, i) represents the set of all the permutations obtained with i elements taken from a set S. For example, if S(3) = a2 a9 a1 a0 , then at round 3 the agents a2 , a9 , a1 , a0 will be activated and will access the whiteboard in this order. Computation. Let S(t) = ai1 , . . . , aih(t) be the sequence of activated agents at time t. All the agents in S(t) execute the following steps (refer to Algorithm 1 in Section B): Look: Let a be an agent in S(t). Let v be the node where agent a is located. Then a observes and takes these data: pos(a), i.e., its position within v (center or a sub-port), and the content of notebooka . Compute: In this step, agents take access to the whiteboard in mutual exclusion. Thus, this step is executed in sequence, starting from ai1 to aih(t) . Let a be an agent among them during its turn. Then, a grants access to whiteboardv , and reads its content. Let ϕv : {⊙}∪{in, out}×[0, δv −1] → [0, k] be the agents’ arrangement7 on v during the Compute step of a. Let σ = ⟨pos(a), notebooka , whiteboardv , ϕv ⟩ be the tuple containing all the data got during the Look and Compute steps. Now, a executes A(σ) = (p, χ) where A is the deterministic algorithm shared by all the agents, and where p ∈ [0, δ(v) − 1] ∪ {⊙, NaN} and χ ∈ {0, 1}∗ ∪ {NaN} is a binary word or undefined8 . If χ is defined (i.e., χ = ̸ NaN), then a writes χ on whiteboardv . Then, if p is defined (i.e., p = ̸ NaN), then a moves to the outgoing port labeled as p (if p ∈ [0, δ(v) − 1]) or at the center of v (if p = ⊙); otherwise, a stays still. Move: Once all the agents in S(t) have completed the Compute step, then each agent a ∈ S(t) executes its movement in parallel with the other agents. In particular, if a is at an outgoing port of some channel (v, w), and ϱ({v, w}, t) = 1, then a travels along the channel (v, w) and reaches the ingoing port of w. Otherwise, a does nothing. Through the infinite repetition of LCM cycles and execution of the algorithm A, the team aims to solve a common problem.
7 8
Indicating how many agents there are on the center ⊙ or on each sub-port of v. We use the value NaN (not a number) to indicate that a function is not definited for that input.
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro
2.3 2.3.1
Problems Safe exploration
A node v is visited at time t if at least one agent is located in v (in its center or in one of its sub-ports). As soon as an agent a visits a black hole, we say that a gets trapped in that node since it will no longer move to another node. Conversely, a is free as long as it is not trapped. For a dangerous network G = (G = (V, E), Λ, ϱ, B), we consider the following problems: ▶ Definition 1 (SE∞ ). Given k agents arranged on nodes of G, the Safe Perpetual Exploration (SE∞ ) problem requires each safe node of G to be visited infinitely often. ▶ Definition 2 (SE⊥ ). Given k agents arranged on nodes of G, the Safe Finite Exploration (SE⊥ ) problem requires the agents to reach a configuration in finite time where: at least an agent is free; each safe node of G has been previously visited at least once; each free agent is located at the center of a node, not necessarily the same; each agent will do nothing in the next time steps. We are interested in the following further properties: Loss-minimizing: for both SE∞ and SE⊥ , we are interested in solutions that minimize the number of trapped agents. Explicit termination: for SE⊥ , in addition to exploration completion (i.e., all nodes have been visited) and the termination of the algorithm (i.e., agents will no longer move), we require this information to be propagated to all safe nodes so that all agents get aware of the problem termination. We say that an agent gets aware of the termination of the problem if it writes TERMINATION in its notebook9 . To avoid falling into trivial conditions, the awareness must be reached by the free agents only after solving SE⊥ .
2.3.2
Port marking
Safely exploring a dangerous network requires agents to probe and mark (in the best case, all) the ports as SAFE or DANGEROUS, thereby preventing all agents from being trapped in the black holes. We generally refer to this sub-routine as port marking (PM). As we will see, some ports may remain unmarked. Specifically, a correct port marking of a dangerous network G = (G = (V, E), Λ, ϱ, B) is achieved when a team of agents reaches a configuration in a finite time t ∈ N0 where: at least one agent is free; all ports are correctly marked. Namely, if p(v, w) is dangerous, it must be marked in whiteboardv as DANGEROUS; otherwise (i.e., p(v, w) is safe), it must be marked as SAFE; these values cannot be changed in the next time steps t′ ≥ t. Thus, a correct PM presents neither false positives (i.e., safe ports marked as DANGEROUS), nor false negatives (i.e., dangerous ports marked as SAFE). Note that this does not preclude the possibility that, before t, some ports were incorrectly classified by the agents. However, once the correct marking is reached at time t, it remains invariant thereafter and can be used by the free agents to safely explore the network. As we will see in the next sections, it is not always possible to achieve a correct PM in the TRANSIENT setting. Therefore, we define the following three weaker variants.
9
Oblivious agents can write TERMINATION on the whiteboard of the safe nodes to explicitly terminate.
9
10
Safe Exploration of Arbitrary Dynamic Dangerous Networks
A highly reliable port marking of G is achieved when a team of agents reaches a configuration in a finite time t ∈ N0 where: at least one agent is free; if {v, w} is recurrent, then p(v, w) and p(w, v) are correctly marked as SAFE or DANGEROUS; all the dangerous ports are correctly marked as DANGEROUS; these values cannot be changed in the next time steps t′ ≥ t. Thus, a highly reliable PM differs from a correct one only in that it admits false positives only for ports belonging to transient edges; consequently, the set of the SAFE ports is a subset of the actual safe ports in G. Yet, this fact does not prevent the agents from reaching all the safe nodes of G. In fact, let GSAFE be the network obtained by removing from G all the black nodes and all the edges with at least one port not marked as SAFE in G. Since GSAFE contains all the safe recurrent edges of G, we can conclude that GSAFE is temporally connected as G. A reliable port marking of G allows false positives regardless of the nature of the edge, but with the constraint that GSAFE must be temporally connected. Formally, the achieved configuration must have: at least one agent is free; all the dangerous ports are correctly marked as DANGEROUS; GSAFE must be temporarily connected; these values cannot be changed in the next time steps. Lastly, a weakly reliable port marking of G is reached when: at least one agent is free; if a port is SAFE-marked, it is truly safe; these values cannot be changed in the next time steps. A correct PM is highly reliable, which is, in turn, reliable, which is, in turn, weakly reliable.
2.4
Basic impossibilities
We now define a property of networks which will be used to prove some impossibility results on the port marking problem (in Theorem 4 and later in Theorem 12). ▶ Definition 3 (Network indistinguishability). Given two networks G = (G = (V, E), Λ, ϱ, B) and G ′ = (G′ = (V ′ , E ′ ), Λ′ , ϱ′ , B ′ ), we say that G during the period [ta , tb ] is indistinguishable from G ′ during the period [t′a , t′b ], and we denote this as G[ta , tb ] ∼ G ′ [t′a , t′b ], if tb − ta = t′b − t′a and if there exists a bijection h : V → V ′ such that: b ∈ B ⇐⇒ h(b) ∈ B ′ ; for any v ∈ V \ B, δ(v) = δ(h(v)); for any t ∈ [0, tb − ta ], it holds that {v, w} ∈ E(Gta +t ) ⇐⇒ {h(v), h(w)} ∈ E(G′t′a +t ); if {v, w} ∈ E(Gt ) for some t ∈ [ta , tb ], then λv (p(v, w)) = λh(v) (p(h(v), h(w))). Refer Figure 1 for an example. A direct consequence of this property is that the same team of oblivious agents will have identical behavior when deployed on indistinguishable graphs if they start from indistinguishable configurations. Formally, let A be a group of k oblivious agents deployed on G, A be the deterministic algorithm they execute, S be the scheduler activating A. Let G[ta , tb ] ∼ G ′ [t′a , t′b ] for some G ′ graph according to some bijection h. Now, suppose A is arranged on G ′ so that, for all v ∈ V \ B: whiteboardv at time ta is equal to whiteboardh(v) at time t′a ; φv (ta ) = φh(v) (t′a ), where φv (t) defines the position of all the agents within v at time t. Suppose that, while on G ′ , agents are activated by a scheduler S′ so that S′ (t′a +t) = S(ta +t) for t ∈ [0, tb − ta ]. Then, during [t′a , t′b ], A performs on G ′ the same actions as on G.
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro
b
b
v
u
11
w
H
(a) G, where {v, u} is always absent.
v
u
w
H
(b) G ′ , where {v, b} and {u, b} are absent during the period [0, t].
Figure 1 Two indistinguishable networks G[0, t] ∼ G ′ [0, t] with the same static subgraph H, but different edges among v, u, and the black hole. Solid (dashed, resp.) straight lines represent recurrent (transient, resp.) edges.
▶ Theorem 4. It is impossible to achieve a correct port marking under the TRANSIENT model even when agents know |V |, |B|, k, have infinite memory, and are activated under FSYNCH. Proof. The claim derives from the impossibility of correctly marking transient edges. Let us proceed by contradiction, and let A be an algorithm providing a correct port marking in the FSYNCH-TRANSIENT model. Let G be the dangerous network depicted in Figure 1a where the two safe nodes v and u are connected by a transient edge. Suppose the edge {v, u} permanently disappears at time 0. Since A correctly marks the ports, let t be the finite time when both p(v, u) and p(u, v) will be permanently marked as SAFE in G. Now assume the same team is arranged on a graph G ′ (depicted in Figure 1b) which is identical to G, except that the edge {v, u} is replaced with two transient edges {v, b} and {u, b}. Suppose that the edges {v, b} and {u, b} are always absent. Then, since G[0, ∞] ∼ G ′ [0, ∞], we have that A marks p(v, b) and p(u, b) in G ′ as SAFE at time t, and such marking will remain invariant forever: this contradicts the fact that A provides a correct port marking. ◀
3
Safe Perpetual Exploration
3.1
Assumptions and limits
We study the SE∞ problem for a team of anonymous and oblivious agents, under the SSYNCH setting, arbitrarily deployed on the safe nodes of a dangerous, anonymous, and TRANSIENT network G = (G = (V, E), Λ, ϱ, B) with |V | = n nodes and 0 ≤ |B| < n black holes. Agents do not have any prior knowledge about the network or the team. Under these assumptions, we first observe that it is impossible to explore (perpetually or finitely) the network with P fewer than b∈B δ(b) agents. In fact, since agents do not know the size of the network, any unexplored edge may lead to an unexplored leaf safe node; thus, each edge must be traversed at least once in order to explore all the nodes. It follows that any algorithm solving SE∞ P under these assumptions will have at least b∈B δ(b) trapped agents, one for each dangerous port. This also defines the lower bound on the loss of any exploration solution. Moreover: ▶ Theorem 5 ([14]). There exists a network G = (G = (V, E), Λ, ϱ, B) with B = ∅ and η transient edges for which it is impossible to solve SE∞ with fewer than 2η agents. Informally, the former lower bound derives from the fact that 2 agents are needed to “deal with” the two endpoints of each transient edge. However, since in our case B may be non-empty and some transient edges may be dangerous, we can combine the two lower
12
Safe Exploration of Arbitrary Dynamic Dangerous Networks
P bounds (i.e., b∈B δ(b) to explore the dangerous ports and 2η to deal with the transient edges) by considering the parameter η ′ , i.e., the number of transient edges which are not dangerous. Thus, we will always assume that any instance G = (G = (V, E), Λ, ϱ, B) of the P SE∞ problem starts with at least 2η ′ + b∈B δ(b) + 1 agents arranged on V \ B.
3.2
Algorithm for SE∞
Under the above assumptions, we provide an algorithm, called A∞ , which solves SE∞ by combining the rotor-router mechanism with a cautious walk technique. A∞ needs a O(∆)-size whiteboard10 . By Theorem 4, the final port marking provided by A∞ may not be correct; yet, it is always highly reliable. Algorithm A∞ – Safe Perpetual Exploration, SE∞ Network
Synch
Initial
Params
Mem
WhiteB
AgentId
Port marking
TRANSIENT
SSYNCH
Any
✗
✗
∆
✗
Highly reliable
Initialization. Each agent a ∈ A is initially located at the center of an arbitrary safe node. The whiteboard whiteboardv of each safe node v ∈ V \ B contains the following variables: the pointer rotorv ∈ [0, δ(v) − 1] which points to one port, 0 by default. This pointer will be used to implement the rotor-router mechanism; the array portsv ∈ {SAFE, UNEXPLORED, DANGEROUS}δ(v) which contains the state of each port. Namely, ports[i] indicates the state of port i. This array will be used to implement the port marking. At time 0, each port is marked as UNEXPLORED. Thus, the size of whiteboardv is Θ(δv ) bits. Strategy. From a high-level perspective, our algorithm follows this scheme: unexplored ports are first explored cautiously, and, if safe and recurrent, they will eventually be marked as such; the rotor-router mechanism guarantees a complete exploration of all the nodes of the network, and eventually a perpetual exploration of all and only the safe nodes. Let us now give the details of our algorithm. The choice of the next edge to be traversed for an agent a at a node v is computed by the utility next_candidate(), which locally computes the next candidate port for exploration within a node v (refer to Algorithm 3 for the pseudocode). A candidate port must be empty (i.e., without any agent on its sub-ports) and not marked as DANGEROUS. Thus, next_candidate() returns the first empty port marked as SAFE or UNEXPLORED within v, starting from the port pointed by rotorv , or NaN if no candidate exists. In the first case, a positions itself on the outgoing sub-port returned by next_candidate() and increments the value of rotorv by one. Otherwise, it does nothing and waits for a candidate. Before the exploration of an UNEXPLORED port p(v, w), the agent a marks it as DANGEROUS in portsv ; if the agent will eventually reach pin (w, v), it marks such a port as SAFE in portsw if it was marked otherwise. Then, the agent could be required to go back along the channel (w, v) to mark p(v, w) as SAFE as well; this happens only if p(w, v) was marked as UNEXPLORED before the arrival of a. Let us now describe in detail the algorithm.
10
ˆ where ∆ ˆ corresponds to the maximal degree of the safe The precise upper bound is given by O(∆) nodes in G. Yet, we use ∆ for consistency with the literature.
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro Algorithm scheme. Let S(t) be the set of agents activated at time t. We now describe A∞ by defining the actions made sequentially by each agent a ∈ S(t) during its Compute step. Refer to Algorithm 4 for the pseudocode of A∞ . Let v be the node where a lies at the beginning of the round t: if v is a black hole, a does nothing (w.l.o.g., we can assume that a is destroyed once in a black hole). Otherwise, the actions of a depends on pos(a) as follows, where pos(a) is the relative position of a within v: if pos(a) = ⊙ (i.e., the center), then a reads from whiteboardv the value of rotorv , and computes the value j = next_candidate(). Then, a behaves as follows: if j = NaN (i.e., there are no candidate ports in v), then a does nothing; otherwise (i.e., j ∈ [0, δv − 1]), a acts as follows: ∗ a moves to the outgoing sub-port λ−1 (j); ∗ a updates the value of rotorv so that now it points to j + 1 mod δv ; ∗ if portsv [j] = UNEXPLORED, then a locks the port λ−1 v (j) by updating the corresponding state portsv [j] ← DANGEROUS. if pos(a) = pin (v, w) (i.e., a is activated after its Move along the channel (w, v)), then: if portsv [λv (w)] = UNEXPLORED, then a updates the state of the port to SAFE and moves to the outgoing port pout (v, w) in order to go back to the node w; if portsv [λv (w)] = DANGEROUS, then a updates the state of the port to SAFE and moves to the center of v. In this case, a does not need to go back to w since there is already an agent (the one which has marked the port as DANGEROUS) that is moving/has moved along the channel (v, w) and it will mark the port p(w, v) as SAFE. if portsv [λv (w)] = SAFE, then a moves to the center of v. Even in this case, a does not need to go back to w since there is already an agent (the one that has marked the port as SAFE) that is moving/has moved along the channel (v, w), and that will mark the port p(w, v) as SAFE in case. if pos(a) = pout (v, w), it does nothing. During the Move step, each agent in S(t) that is located in an outgoing sub-port of a safe node will travel along the corresponding edge if such an edge is present at time t. In particular, if a is located at pout (v, w) during the Move step of round t, and if ϱ({v, w}, t) = 1, then a will be located at pin (w, v) at the beginning of round t + 1.
3.3
Analysis of A∞
We here prove the properties and the correctness of A∞ in solving SE∞ (proofs in Section A.1). ▶ Lemma 6. If a port p(v, w) is marked as SAFE at round t, then w is truly a safe node and p(v, w) permanently remains marked as SAFE thereafter. ▶ Lemma 7. If a port p(v, w) is marked as DANGEROUS at round t and node w is truly a black hole, then such a port will be permanently marked as DANGEROUS. ▶ Lemma 8. If a port p(v, w) is marked as DANGEROUS at round t and node w is safe and {v, w} is recurrent, then p(v, w) will be eventually and permanently marked as SAFE. P ▶ Lemma 9. Consider a team of at least 2η ′ + b∈B δ(b) + 1 agents executing A∞ on a network G = (G = (V, E), Λ, ϱ, B). Then, for each round t, there exists a time t′ ≥ t where at least one agent travels along an edge. ▶ Lemma 10. If a safe node v is visited by an incoming agent an infinite number of times, then each safe node w connected to v through a recurrent edge will be visited an infinite number of times.
13
14
Safe Exploration of Arbitrary Dynamic Dangerous Networks P ▶ Theorem 11. A∞ ensures a team of at least 2η ′ + b∈B δ(b) + 1 oblivious and anonymous agents arranged on the anonymous nodes of a temporally connected network G under the SSYNCH-TRANSIENT model to solve SE∞ without any prior knowledge of G. Eventually, A∞ provides a highly reliable port marking on G.
4
Safe Finite Exploration
4.1
Assumptions and limits
We now extend the previous algorithm so that agents can detect when every node has been visited and terminate. To prevent agents from perpetually exploring the same indistinguishable nodes, we now assume that (i) nodes have IDs, or (ii) there is a way to assign IDs to the nodes. To remain consistent with the existing literature, we choose the second approach: we assume each agent has its own ID, say ai with i ∈ [0, k − 1]. As soon as ai visits a not-yet-named node v, it will assign a distinct ID to v (by composing its agent ID and a progressive value), and it will write this ID on whiteboardv . Note that assumptions (i) and (ii) are equivalent: even assuming (i), each agent can use the ID of the node where it is initially arranged as its own ID. In case of multiplicity, the mutually exclusive access to the whiteboards can provide a simple mechanism for assigning IDs to co-located agents [8]. Moreover, we assume that agents have a notebook and know |V \ B| = s; no other information is needed. The notebook of each agent is used to maintain and disseminate the list of the already-visited nodes. Such lists are copied onto the whiteboards or merged with the existing ones. As soon as a list contains s IDs, the agent knows that all the safe nodes have been visited. We now observe the main computational difference between SE⊥ and SE∞ . ▶ Theorem 12. Any solution for SE⊥ under the TRANSIENT model cannot achieve a reliable port marking, even assuming agents/nodes with IDs and infinite memory, FSYNCH schedulers, and the knowledge of k, |V |, and |B|. Proof. The impossibility derives from the fact that agents cannot distinguish between a transient and a recurrent edge in finite time. Suppose by contradiction that there exists a solution A for SE⊥ . Assume A is run on the network in Figure 2a where, from time 0, the recurrent edge {v, u} is absent for an unpredictable but finite amount of time, while the transient edge {v, h} is always present in that period. Since this network is indistinguishable from the network in Figure 2b where the dangerous edges {v, b} and {u, b} are absent for an unpredictable amount of time, eventually A must terminate and so permanently mark the ports p(v, h) and p(h, v) as SAFE and the ports p(v, u) and p(u, v) as DANGEROUS in a finite t. However, the sub-network GSAFE obtained by keeping only the ports marked as SAFE has {{v, h}, {u, h}, {w, h}} as edge-set; indeed, GSAFE is not temporally connected (in fact, the edge {v, h} will permanently disappear at time t + 1, so that the safe node v will remain indefinitely isolated). This contradicts the fact that A provides a reliable port marking. ◀ However, we will show that it is possible to provide a port marking that is weakly reliable.
4.2
Algorithm for SE⊥
Under the above assumptions, we now describe our algorithm, called A⊥ , for solving SE⊥ . As we will see, A⊥ uses A∞ as a subroutine. Algorithm A⊥ – Safe Finite Exploration, SE⊥ Network
Synch
Initial
Params
Mem
WhiteB
AgentId
Port marking
TRANSIENT
SSYNCH
Any
s
n log n
n log n
✓
Weakly reliable
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro
15
b v
b u
w
v
u
w
h
h
(a) {v, h} always appears in [0, t] and it permanently disappears at time t+1; {v, u} never appears in [0, t].
(b) {v, b} and {u, b} are absent for an unpredictable time.
Figure 2 Solid (dashed, resp.) straight lines represent recurrent (transient, resp.) edges. Thick solid lines represent static edges (i.e., always present).
Initialization: As for A∞ , we assume that the whiteboard of each safe node v contains the variables portsv and rotorv . Moreover, each whiteboardv contains three variables: nodeStatusv , nodeIDv and nodeListv . In particular, nodeStatusv will be used to contain the value EXPL_COMPLETE only when the exploration of all the safe nodes has been completed; nodeIDv will contain the ID of the node, which is given by the first agent accessing whiteboardv ; nodeListv will contain a cumulative list of the already-visited node IDs. Each agent executes the algorithm (A⊥ , s, a) where A⊥ is the same deterministic algorithm parametrized w.r.t. s = |V \ B| and the personal agent ID a. Each agent maintains in its notebook a variable agentStatusa ∈ {EXPLORATION, PROPAGATION, TERMINATION}— initialized to EXPLORATION—which will be used to determine the action to be performed, a variable agentNodeLista containing the list—initially empty—of the node IDs encountered during the exploration, and an integer variable countera —initialized to 0—which will be used to provide IDs to the nodes. The items of the lists nodeListv and agentNodeLista will be in the form (x, bool) where x = (a, j) defines a node ID, while bool is a boolean (false by default) which will be set to true only during the propagation phase. Table 2 summarizes the variables used in A⊥ . Algorithm scheme: The algorithm is composed of three subsequent phases: exploration, propagation, and termination. During the exploration phase, the agents continue exploring the nodes of the network essentially by executing the same strategy as in A∞ . In addition, the agents provide nodes with IDs: such IDs are collected in the agentNodeList variables and distributed along the network in the nodeList variables. This phase ends as soon as an agent has collected all the s node IDs. At this point, the agents that have detected that all safe nodes have been visited at least once (since these agents have already collected all the s node IDs) must propagate this information to all other nodes. To keep track of the nodes on which the information has already been propagated, the agents set the corresponding bool value to true in the lists nodeList and agentNodeList. Eventually, all the other nodeList variables will contain all the s nodes in the form (x, true): then, the agents will be aware of the algorithm termination. More formally, let a be an agent activated in a safe node v. We now describe in detail the actions of a when executing (A, m, a) in one LCM cycle. Refer to Algorithm 5 in Section B. Exploration. (case agentStatusa = EXPLORATION) if nodeStatusv ̸= EXPL_COMPLETE, then ∗ if nodeIDv is undefined, then a gives a name to v by updating the variable nodeIDv . In particular, a writes nodeIDv ← (a, j) on whiteboardv where j = 0, 1, 2, . . . is
16
Safe Exploration of Arbitrary Dynamic Dangerous Networks
the value of countera . After that, a increases the value of the counter by one, and adds to agentNodeLista the value (a, j, false). ∗ a computes ℓ = nodeListv ∪ agentNodeLista (i.e., the comprehensive list of all the distinct node IDs appearing in the two variables) and updates the two lists: nodeListv ← ℓ and agentNodeLista ← ℓ. ∗ if ℓ contains s node IDs, then a updates agentStatusa ← PROPAGATION; at this point, the propagation phase starts. Otherwise (i.e., ℓ contains fewer than s node IDs), the algorithm executes A∞ to continue the exploration. otherwise (i.e., if nodeStatusv = EXPL_COMPLETE), a sets agentStatusa ← PROPAGATION. Propagation: (case agentStatusa = PROPAGATION) a writes nodeStatusv ← EXPL_COMPLETE and sets bool ← true for the entry of node v in agentNodeLista . Then, a computes ℓ as the merge of agentNodeLista and nodeListv . If the same node ID appears in both lists with two different bool values, that node ID is copied in ℓ only with the true entry; a writes agentNodeLista ← ℓ and nodeListv ← ℓ; if all the s entries of agentNodeLista have bool=true, then a sets agentStatusa ← TERMINATION; otherwise a executes A∞ to continue the propagation. Termination: (case agentStatusa = TERMINATION) Agent a is aware that all the nodes have been visited at least once and are marked as EXPL_COMPLETE. So, a goes to the center of v and terminates. Eventually, all free agents will set agentStatus ← TERMINATION and will terminate at the center of some safe nodes. The problem is solved.
4.3
Analysis of A⊥
We prove the properties and the correctness of A⊥ in solving SE⊥ (proofs in Section A.2). P ▶ Lemma 13. Consider a team of at least 2η ′ + b∈B δ(b) + 1 agents executing A⊥ on a network G = (G = (V, E), Λ, ϱ, B). Then, the Exploration phase is finite and ensures that all safe nodes are visited at least once and that at least one agent remains free. ▶ Lemma 14. The Propagation phase is finite, ensures that all safe nodes have nodeStatus marked as EXPL_COMPLETE and that at least one agent remains free. ▶ Lemma 15. The Termination phase is finite and ensures that all free agents, of which are at least one, are at the center of a safe node. P ▶ Theorem 16. A⊥ ensures a team of at least 2η ′ + b∈B δ(b) + 1 agents with IDs arranged on the anonymous nodes of a temporally connected network G under the SSYNCH-TRANSIENT model to solve SE⊥ with explicit termination, only knowing s = |V \ B|. Eventually, A⊥ provides a weakly reliable port marking on G.
5
Conclusions
In this paper, we have extended the existing study on exploration of arbitrary and unknown dynamic networks by considering the possibility that the network is dangerous, namely, it may contain black holes. In particular, we have studied the capability of a team of semi-synchronous agents to solve the Safe Perpetual Exploration (SE∞ ) and the Safe Finite Exploration (SE⊥ ) problems, under the temporal connectivity assumption, i.e., the minimal connectivity condition such that a non-trivial problem in a temporal graph can be solved. Interestingly, SE∞ can be solved under a very weak setting (anonymous nodes and agents, oblivious agents starting from any initial configuration, no prior knowledge of
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro the team or the network). For SE⊥ , we propose an algorithm that makes agents explicitly terminate the exploration by assuming agents have IDs and a limited personal memory, only knowing the number of safe nodes. A first future work may investigate whether SE⊥ can be solved under weaker assumptions. Another interesting research direction is to consider more adversarial settings of dynamic networks; e.g., settings in which some edges may dynamically change one of their endpoint ports. References 1 2
3
4
5
6
7 8
9
10
11
12
13 14
Kass Bileski and Avery Miller. Don’t be afraid to die: Black hole search in dynamic graphs with fewer agents, 2026. URL: https://arxiv.org/abs/2609.06850, arXiv:2609.06850. Hans-Joachim Böckenhauer, Fabian Frei, Walter Unger, and David Wehner. Zero-memory graph exploration with unknown inports. In Procs. of the 30th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 246–261. Springer, 2023. doi:10.1007/978-3-031-32733-9_11. Jérémie Chalopin, Shantanu Das, and Nicola Santoro. Rendezvous of mobile agents in unknown graphs with faulty links. In Procs. of the 21st International Symposium on Distributed Computing (DISC), pages 108–122. Springer, 2007. doi:10.1007/978-3-540-75142-7_11. Shantanu Das. Graph explorations with mobile agents. In Distributed Computing by Mobile Entities, Current Research in Moving and Computing, Lecture Notes in Computer Science, pages 403–422. Springer, 2019. doi:10.1007/978-3-030-11072-7_16. Shantanu Das, Paola Flocchini, Shay Kutten, Amiya Nayak, and Nicola Santoro. Map construction of unknown graphs by multiple agents. Theoretical Computer Science, 385(13):34–48, 2007. doi:10.1016/J.TCS.2007.05.011. Dariusz Dereniowski, Adrian Kosowski, Dominik Pajak, and Przemyslaw Uznansk. Bounds on the cover time of parallel rotor walks. In Procs. of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), pages 263–275. LIPIcs, 2014. doi: 10.4230/LIPIcs.STACS.2014.263. Stéphane Devismes, Yoann Dieudonné, and Arnaud Labourel. Graph exploration: The impact of a distance constraint. Algorithmica, 88(2):24, 2026. doi:10.1007/S00453-026-01378-4. Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Searching for a black hole in arbitrary networks: optimal mobile agents protocols. Distributed Computing, 19(1):1–35, 2006. doi:10.1007/S00446-006-0154-Y. 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. Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. In Procs. of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP), pages 444–455. Springer, 2015. doi:10.1007/978-3-662-47672-7_36. Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T. Spooner. Two moves per time step make a difference. In Procs. of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pages 141:1–141:14, 2019. doi:10.4230/ LIPICS.ICALP.2019.141. Thomas Erlebach and Jakob T. Spooner. Faster exploration of degree-bounded temporal graphs. In Procs. of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS), 2018. doi:10.4230/LIPICS.MFCS.2018.36. Aviezri S. Fraenkel. Economic traversal of labyrinths. Mathematics Magazine, 43(3):125–130, 1970. doi:10.1080/0025570X.1970.11976025. Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro. Exploration of dynamic networks: Tight bounds on the number of agents. Journal of Computer and System Sciences, 122:1–18, 2021. doi:10.1016/J.JCSS.2021.04.003.
17
18
Safe Exploration of Arbitrary Dynamic Dangerous Networks 15
Tsuyoshi Gotoh, Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Group exploration of dynamic tori. In Procs. of the 38th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 775–785. IEEE Computer Society, 2018. doi:10.1109/ICDCS.2018.00080.
16
David Ilcinkas and Ahmed Mouhamadou Wade. Exploration of the t-interval-connected dynamic graphs: the case of the ring. Theory of Computing Systems, 62(5):1144–1160, 2018. doi:10.1007/S00224-017-9796-3.
17
Tanvir Kaur and Ashish Saxena. When agents are powerful: Black hole search in timevarying graphs. In Procs. of the 22nd International Conference on Distributed Computing and Intelligent Technology (ICDCIT), volume 16420, pages 3–18. Springer, 2026. doi:10.1007/ 978-3-032-16632-6_1.
18
Tanvir Kaur, Ashish Saxena, Partha Sarathi Mandal, and Kaushik Mondal. Black hole search by scattered agents on time-varying dynamic graphs. In Procs. of the 27th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 309–324. Springer, 2025. doi:10.1007/978-3-032-11127-2_25.
19
Tanvir Kaur, Ashish Saxena, Partha Sarathi Mandal, and Kaushik Mondal. Black hole search in dynamic graphs. In Procs. of the 26th International Conference on Distributed Computing and Networking (ICDCN), pages 221–230. ACM, 2025. doi:10.1145/3700838.3700869.
20
Adrian Kosowski and Dominik Pajak. Does adding more agents make a difference? A case study of cover time for the rotor-router. Journal of Computer and System Sciences, 106:80–93, 2019. doi:10.1016/J.JCSS.2019.07.001.
21
Fabian Kuhn, Nancy A. Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Procs. of the 42nd ACM Symposium on Theory of Computing (STOC), pages 513–522. ACM, 2010. doi:10.1145/1806689.1806760.
22
Giuseppe Antonio Di Luna, Stefan Dobrev, Paola Flocchini, and Nicola Santoro. Distributed exploration of dynamic rings. Distributed Computing, 33(1):41–67, 2020. doi:10.1007/ S00446-018-0339-1.
23
Subhrangsu Mandal, Anisur Rahaman Molla, and William K. Moses Jr. Efficient live exploration of a dynamic ring with mobile robots. Theoretical Computer Science, 980:114201, 2023. doi:10.1016/J.TCS.2023.114201.
24
Euripides Markou and Wei Shi. Dangerous graphs. In Distributed Computing by Mobile Entities, Current Research in Moving and Computing, pages 455–515. Springer, 2019. doi: 10.1007/978-3-030-11072-7_18.
25
Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1–23, 2016. doi:10.1016/J.TCS.2016.04.006.
26
Debasish Pattanayak and Andrzej Pelc. Graph exploration by a deterministic memoryless automaton with pebbles. Discrete Applied Mathematics, 356:149–160, 2024. doi:10.1016/J. DAM.2024.05.024.
27
Ashish Saxena, Anisur Rahaman Molla, Kaushik Mondal, and Gokarna Sharma. Semisynchronous exploration in dynamic graphs, 2026. URL: https://arxiv.org/abs/2605.14375, arXiv:arXiv:2605.14375.
28
Kohei Shimoyama, Yuichi Sudo, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles. In Procs. of the 24th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 19–34. Springer, 2022. doi:10.1007/978-3-031-21017-4_2.
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro
A
Proofs
A.1
Proofs for A∞
▶ Lemma 6. If a port p(v, w) is marked as SAFE at round t, then w is truly a safe node and p(v, w) permanently remains marked as SAFE thereafter. Proof. According to A∞ , a port p(v, w) is marked as SAFE as soon as an agent located in the ingoing sub-port pin (v, w) is activated. In fact, by construction, an agent can be located on pin (v, w) only if it has traversed the channel (w, v): this proves the fact that w is safe. According to our algorithm, this mark will never be updated. ◀ ▶ Lemma 7. If a port p(v, w) is marked as DANGEROUS at round t and node w is truly a black hole, then such a port will be permanently marked as DANGEROUS. Proof. According to A∞ , the only case in which a port p(v, w) marked as DANGEROUS is then marked with another value occurs when an agent enters node v through the ingoing port pin (v, w). In this case, the port will be marked as SAFE. However, since w is a black hole, this case can never happen. ◀ ▶ Lemma 8. If a port p(v, w) is marked as DANGEROUS at round t and node w is safe and {v, w} is recurrent, then p(v, w) will be eventually and permanently marked as SAFE. Proof. According to A∞ , if an agent a marks p(v, w) as DANGEROUS and {v, w} is recurrent, then, eventually, a will travel along the edge {v, w}. As soon as a enters w through pin (w, v), it understands w is safe. A∞ makes an agent mark as SAFE any UNEXPLORED or DANGEROUS port from which it has just entered (except for the ports on the black holes). If p(w, v) was marked as UNEXPLORED, then a positions itself on pout (w, v) and returns to v along the same (recurrent) edge: as soon as it will go back to p(v, w), a will mark this port as SAFE. However, if p(w, v) was already marked as SAFE or it was marked as DANGEROUS, then it means that at least one agent has already moved or is going to move along the channel (w, v). Such agents will be responsible for marking p(v, w) as SAFE. By Lemma 6, the mark SAFE on p(v, w) is permanent. ◀ P ▶ Lemma 9. Consider a team of at least 2η ′ + b∈B δ(b) + 1 agents executing A∞ on a network G = (G = (V, E), Λ, ϱ, B). Then, for each round t, there exists a time t′ ≥ t where at least one agent travels along an edge. P Proof. Let t ∈ N0 . At time t, at most b∈B δ(b) agents may be trapped in the black holes or located in the outgoing dangerous sub-ports of transient dangerous edges, waiting indefinitely for their reappearance; moreover, at most 2η ′ agents may be located at the 2η ′ outgoing sub-ports of the transient safe edges, also waiting in vain for their reappearance. Note, in fact, that the rotor-router mechanism ensures that at most one agent may be located on an outgoing sub-port at each time. Thus, at least one agent, say a, is located in some safe node, say v, not on the outgoing sub-port of a transient edge. Note that, since G is temporally connected, each safe node has at least one incident edge which is both safe and recurrent. According to A∞ , if a is activated and there is a candidate port (i.e., not marked as DANGEROUS and not occupied by other agents), then it moves to the corresponding outgoing sub-port. Eventually, either a or one agent that occupies the recurrent outgoing sub-ports of v will be activated when the corresponding edge is present, and it will travel along it (thanks to the eventual transportation condition). Instead, suppose all the ports of v are marked as DANGEROUS at time t. Among them, at least one port, say p(v, w), is truly safe and recurrent;
19
20
Safe Exploration of Arbitrary Dynamic Dangerous Networks
thus there is an agent on p(w, v) that will eventually come back to v through the port p(v, w) and will mark it as SAFE. In any case, at least one agent travels along an edge at a time t′ ≥ t. ◀ ▶ Lemma 10. If a safe node v is visited by an incoming agent an infinite number of times, then each safe node w connected to v through a recurrent edge will be visited an infinite number of times. Proof. When an agent enters v through a port pin (v, w), after possibly marking it as SAFE, it has two options: (i) go back through pout (v, w) to mark p(w, v) as SAFE, or (ii) use the rotor-router mechanism to find the next candidate port to be explored. Yet, note that (i) can be done at most one time for a given port (i.e., only if the agent finds the port still UNEXPLORED). Thus, after a finite number of visits, agents must use the rotor-router mechanism to choose the next node to visit. So, assume we always apply (ii), where rotorv simply cycles over all the ports: in this case, the agent selects the first candidate port (i.e., empty from agents and not marked as DANGEROUS) starting from the port pointed by rotorv . Thus, all the SAFE and UNEXPLORED ports will be explored at least once. In particular, all the dangerous UNEXPLORED ports will be marked as DANGEROUS and no longer explored. On the contrary, all the safe and recurrent UNEXPLORED ports will be marked as DANGEROUS for the first exploration, and then marked as SAFE as soon as an agent comes back from the same port. All the safe and transient UNEXPLORED ports will be marked as DANGEROUS, and possibly they will remain DANGEROUS forever. Thus, eventually, all the safe and recurrent ports of v will be marked as SAFE, and they will be cyclically visited by the agents. ◀ P ▶ Theorem 11. A∞ ensures a team of at least 2η ′ + b∈B δ(b) + 1 oblivious and anonymous agents arranged on the anonymous nodes of a temporally connected network G under the SSYNCH-TRANSIENT model to solve SE∞ without any prior knowledge of G. Eventually, A∞ provides a highly reliable port marking on G. Proof. By Lemma 9, it follows that there exists an agent a that will never be trapped by a black hole, and continues to move along recurrent edges. This means that there exists at least one node that is visited infinitely often by a. By Lemma 10, if a reaches v infinitely often, then it will travel along the adjacent safe and recurrent edges infinitely often. Thus, all the safe and recurrent adjacent nodes of v will be visited infinitely often. Recursively, since G is temporally connected, each safe node (and each safe recurrent edge) will be visited infinitely often. Since an agent marks a port as SAFE as soon as it enters it, it follows that all the ports of safe and recurrent edges will be marked as SAFE. Moreover, the rotor-router mechanism ensures all the dangerous edges incident to v are permanently marked as DANGEROUS; while all the transient edges incident to v are permanently marked as either SAFE (when truly safe) or as DANGEROUS. These claims, together with Lemmas 6–8, prove that the final port marking is highly reliable. ◀
A.2
Proofs for A⊥
P ▶ Lemma 13. Consider a team of at least 2η ′ + b∈B δ(b) + 1 agents executing A⊥ on a network G = (G = (V, E), Λ, ϱ, B). Then, the Exploration phase is finite and ensures that all safe nodes are visited at least once and that at least one agent remains free. Proof. The Exploration phase exploits A∞ as a subroutine and ends as soon as one agent has collected all s = |V \ B| node IDs and has set its agentStatus to PROPAGATION. Since it uses
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro A∞ , we know that at least one agent will never be trapped in a black hole. Hence, we need to prove that there exists at least one agent that will collect all the node IDs. An agent a cumulatively collects node IDs in two possible ways: (i) by directly visiting a not-yet-named node or (ii) by visiting an already-visited node v and merging its own agentNodeLista with nodeListv . By contradiction, let us suppose that there will never be an agent that collects all the node IDs. As a consequence, the Exploration phase will never end: agents will indefinitely execute A∞ , and all the safe nodes will be explored infinitely often. This means that there will be a partition of V (G) = {V1 , V2 } and a partition of A = {A1 , A2 } such that the sub-team A1 (A2 , resp.) will be forever visiting only the nodes in V1 (V2 , resp.). However, the induced subgraphs of G[V1 ] and G[V2 ] are connected by at least one recurrent edge in G; otherwise G would not be temporally connected. By Lemma 10, we know that all the safe recurrent edges will be traveled infinitely often by executing A∞ . Yet, this contradicts the hypothesis that there cannot exist a node in G that will be visited by both A1 and A2 . ◀ ▶ Lemma 14. The Propagation phase is finite, ensures that all safe nodes have nodeStatus marked as EXPL_COMPLETE and that at least one agent remains free. Proof. The Propagation phase starts as soon as an agent sets agentStatus ← PROPAGATION and ends as soon as an agent has s node IDs in its agentNodeList set to true, and thus all the s safe nodes have been marked as EXPL_COMPLETE in their whiteboard. By Lemma 13, we know that this phase eventually starts; we have to prove that this phase stops only after all safe nodes have been visited at least once after the Exploration phase. According to A⊥ , in this phase the free agents with agentStatus = PROPAGATION will navigate on the network still using A∞ to set the EXPL_COMPLETE value in the whiteboard of each safe node. Since the agents have used and still use A∞ for navigating the network, we know by Lemma 6 that a SAFE-marked port is truly safe: this ensures that the final port marking is at least weakly reliable. The use of A∞ ensures that at least one agent (those with agentStatus = PROPAGATION) will never fall into a black hole. With the same argument as in Lemma 13, we can claim that the free agents will mark all the s nodes as EXPL_COMPLETE, and they will collect the list of all the s nodes which have been marked. ◀ ▶ Lemma 15. The Termination phase is finite and ensures that all free agents, of which are at least one, are at the center of a safe node. Proof. The Termination phase starts as soon as a free agent sets agentStatus ← TERMINATION; by Lemma 14, we know that eventually this phase starts with all the safe nodes marked as EXPL_COMPLETE. So, as soon as a free agent is activated, it sees that the node in which it is positioned is marked as EXPL_COMPLETE and contains the list of all the s safe nodes marked as true; so, it understands that it has to move to the center of the node and terminates. No other action will be performed. ◀ P ▶ Theorem 16. A⊥ ensures a team of at least 2η ′ + b∈B δ(b) + 1 agents with IDs arranged on the anonymous nodes of a temporally connected network G under the SSYNCH-TRANSIENT model to solve SE⊥ with explicit termination, only knowing s = |V \ B|. Eventually, A⊥ provides a weakly reliable port marking on G. Proof. By Lemma 13, we know that all the nodes are visited at least once in finite time and that at least one agent remains free. By Lemma 14, we know that the information about the exploration termination is explicitly propagated in all the s safe nodes by writing the value
21
22
Safe Exploration of Arbitrary Dynamic Dangerous Networks
EXPL_COMPLETE on their whiteboards; even in this phase, at least one agent remains free. During the propagation, the free agents use—and possibly continue to expand—a spanning subgraph GSAFE of G, which guarantees that each SAFE-marked port is truly safe; thus, the final port marking is weakly reliable. However, GSAFE may not be temporally connected (as proved in Theorem 12, some transient edges of GSAFE may disappear after the propagation phase and leave some safe nodes isolated). By Lemma 15, we know that eventually all the free agents will move permanently to the center of some safe nodes and set agentStatus to TERMINATION. This establishes the explicit termination. ◀
B
Pseudocodes, tables and figures
Algorithm 1 shows the Look-Compute-Move cycle executed by each agent. Algorithm 4 and Algorithm 5 present the pseudocodes of the algorithm A∞ for SE∞ (explained in Section 3) and of the algorithm A⊥ solving SE⊥ (explained in Section 4), respectively. Table 2 lists the variables used by A∞ and A⊥ . Memories
whiteboardv
notebooka
Variables
Usages
portsv rotorv nodeIDv nodeStatusv nodeListv agentStatusa agentNodeLista countera
Array in the form {UNEXPLORED, SAFE, DANGEROUS}δ(v) Pointer containing an integer in [0, δ(v) − 1] Contains a pair x = (a, j) with j ∈ N0 Blank or EXPL_COMPLETE List of entries in the form (x, bool) where bool is a boolean Contains a value in {EXPLORATION, PROPAGATION, TERMINATION} As nodeListv Contains an integer
Table 2 Variables used in A⊥ . The gray-colored variables are also adopted in A∞ .
start
UNEXPLORED
a tries the ingoing port
a is trapped in a black hole
DANGEROUS
a reaches the outgoing port
a comes back
SAFE
Figure 3 Diagramm for the Cautious Walk technique.
Algorithm 2 Utility to check if a port is empty. Function is_empty(x: int) : int is w ← λ−1 v (x); if ∃a ∈ A on pin (v, w) or pout (v, w) then return 0; return 1;
Algorithm 3 Utility for computing the next candidate port to traverse. Function next_candidate() : int is foreach i ∈ [0, δv − 1] do j ← (rotorv + i) mod δv ; if portsv [j] ̸= DANGEROUS and is_empty(j) then return j; return NaN;
C. Feletti, P. Flocchini, G. Prencipe, and N. Santoro
23
Algorithm 1 LCM cycles executed by the agents in S(t). ai1 , . . . , aih(t) ← S(t); a ← aij ; /* Executed in parallel by all the agents in S(t) Look: σ ← ⟨pos(a), notebook(a)⟩ ; /* Executed in sequence by all the agents in S(t) foreach aih in S(t) do Compute: σ ← σ + ⟨whiteboardv , ϕv ⟩ ; (p, χ) ← A(σ); if χ ̸= NaN then whiteboardv ← χ;
*/
*/
if p ∈ [0, δ(v) − 1] then a moves to the outgoing port p; else if p = ⊙ then a moves to the center of v; /* Executed in parallel by all the agents in S(t) Move: if a is located on an outgoing port p then e ← edge at port p; if ϱ(e, t) = 1 then a moves along e and reaches the other node;
Algorithm 4 Algorithm A∞ solving SE∞ . // Compute step of an agent a activated at a node v. pos(a) ← relative position of a within v; if pos(a) = ⊙ then j ← next_candidate(); if j ̸= NaN then rotorv ← j + 1 mod δv ; w ← λ−1 (j); a moves to pout (v, w); if portsv [j] = UNEXPLORED then portsv [j] ← DANGEROUS; else if pos(a) = pin (v, w) then if portsv [λv (w)] = SAFE then a moves to ⊙; else if portsv [λv (w)] = UNEXPLORED then a moves to pout (v, w); else a moves to ⊙; portsv [λv (w)] ← SAFE; else // If pos(a) = pout (v, w), a does nothing.
*/
24
Safe Exploration of Arbitrary Dynamic Dangerous Networks
Algorithm 5 Algortihm A⊥ solving SE⊥ . // Compute step of an agent a activated at a node v. s, a are the parameters of the algorithm; switch nodeStatusv do case EXPLORATION do if nodeStatusv ̸= EXPL_COMPLETE then if nodeIDv is NaN then j ← counterv ; nodeIDv ← (a, j); counterv + +; agentNodeLista ← agentNodeLista ∪ {(a, j, false)}; ℓ ← nodeListv ∪ agentNodeLista ; agentNodeLista ← ℓ; nodeList ← ℓ; if len(ℓ) = s then agentStatusa ← PROPAGATION; else executes A∞ ; else agentStatusa ← PROPAGATION; return; case PROPAGATION do nodeStatusv ← EXPL_COMPLETE; nid ← nodeIDv ; sets true the entry of nid in agentNodeLista ; ℓ ← []; foreach (x, bool) ∈ agentNodeLista do if ∃(x, bool′ ) ∈ nodeListv then ℓ ← ℓ.append((x, bool ∨ bool′ )); else ℓ ← ℓ.append((x, bool)); agentNodeLista ← ℓ; nodeLista ← ℓ; if agentNodeLista has s true entries then agentStatusa ← TERMINATION; else executes A∞ ; return; case TERMINATION do a moves to ⊙ of v; return;