Semi-Synchronous Exploration in Dynamic Graphs Ashish Saxenaa , Anisur Rahaman Mollab , Kaushik Mondala , Gokarna Sharmac a
arXiv:2605.14375v1 [cs.DC] 14 May 2026
b
Indian Institute of Technology Ropar, Rupnagar, 140001, Punjab, India Indian Statistical Institute Kolkata, Kolkata, 700108, West Bengal, India c Kent State University, Kent, 44242, Ohio, USA
Abstract We study the fundamental problem of graph exploration in dynamic graphs using mobile agents. We consider 1-interval connected dynamic graphs, where the topology may change arbitrarily from round to round as long as the graph remains connected, and edges are assigned with the dynamic port labeling at each round. The execution follows a semisynchronous scheduler, under which an adversary may deactivate an arbitrary subset of agents in each round. For a graph with n nodes and k agents, we show that exploration k is impossible if the adversary can deactivate at least n−2 − 1 agents per round, even when agents are equipped with unbounded memory, have global communication and full visibility. This yields an upper bound, k implying that exploration is solvable only when the adversary deactivates at most n−2 − 2 agents per round. We further establish that achieving exploration at this threshold requires agents to have both 1-hop visibility and 1-hop communication. Finally, we present k the exploration algorithm using k agents when − 2 agents, assuming agents are equipped with the adversary deactivates at most n−2 1-hop visibility and global communication, and matches the adversarial deactivation bound implied by the impossibility results. Keywords. Mobile agents, Anonymous graphs, Exploration, Dynamic graphs, Semisynchronous scheduler, Deterministic algorithm. 1. Introduction The exploration of graphs by mobile agents is a fundamental problem in distributed computing. Since the early work of Shannon [1], the goal has been to design algorithms that enable agents to collectively visit all nodes of a network. This problem arises in autonomous systems such as mobile robots, software agents, and vehicular networks, where agents must gather information, detect faults, or disseminate data. Graph exploration has been extensively studied under a variety of assumptions (for a survey, see [2]), predominantly in static graphs where the topology remains fixed. In many modern systems, however, network topologies evolve over time (dynamic graphs), motivating the study of exploration in dynamic graphs. In such settings, maintaining connectivity is essential, as isolated nodes cannot be reached by any agent. Several models have been proposed to capture connectivity in dynamic graphs [3, 4, 5, 6].
A graph G is port-labeled if each edge incident to a node u is assigned a locally unique port number from the set {0, 1, . . . , deg(u) − 1}, where deg(u) is the degree of node u in G. An undirected edge {u, v} thus has two independent port numbers, one at each endpoint. The question of how port numbers behave across rounds becomes even more critical in dynamic graphs. In the literature on dynamic graphs involving mobile agents, mainly two port-labeling models have been studied. The first, we call as fixed port labeling [7, 8, 9, 10, 11], the network has a static footprint graph G, and each Gr is a subgraph of G. The outgoing ports at node u in Gr are the same as the outgoing ports of node u in G. Specifically, if port λ at node u leads to node v in the footprint G, then whenever that edge corresponding port appears in any Gr , it always leads to node v. This provides local stability in the network. The second is referred to as dynamic port labelling [6, 12, 13], where there is no footprint. Therefore, the degree of each node can change arbitrarily in each round, and port numbers are reassigned dynamically based on the current degree. As a result, the port λ at node u may lead to different nodes at different rounds. Dynamic port labeling models networks such as wireless or mobile ad hoc networks, where no persistent underlying structure can be assumed and the neighborhood of a node may change arbitrarily between rounds. Since port numbers are reassigned independently in each round based on the current local topology, port λ at node u may lead to different neighbors in different rounds, providing no consistency across rounds to a traversing agent. Thus, dynamic port labeling captures a strictly more adversarial and general setting than fixed port labeling. In particular, any algorithm correct under dynamic port labeling is also correct under fixed port labeling, whereas the converse does not necessarily hold. Our work studies the exploration problem in a 1-interval connected n-node dynamic network with dynamic port labeling, where 1-interval connected means that Gr is connected in every round r. We consider the semi-synchronous (Ssync) scheduler, in which an adversary may deactivate an arbitrary subset of agents in each round. In the next section, we present the model and the formal problem definition. 1.1. Model and problem definition Dynamic graph: We consider a dynamic network modeled as a sequence of undirected graphs G = (V, E), where the node set V remains fixed over time and satisfies |V | = n. Define S = {u, v} | u, v ∈ V as the set of all possible edges, and let P(S) denote its power set. The function E : N → P(S) maps each round number r ∈ N ∪ {0} to the set of edges E(r) present at that round, yielding the snapshot graph Gr = (V, E(r)). The dynamic graph G is thus given as a sequence ⟨G0 , G1 , G2 , . . .⟩. We assume the presence of a dynamic adversary that may insert or delete any edge at the beginning of each round. For a node v ∈ V , the degree of node v in Gr is defined as degr (v), which we call dynamic degree. We define dynamic diameter D̂ := maxr≥0 Dr , where Dr is the diameter of Gr . Each snapshot graph Gr is unweighted, undirected, and anonymous. Moreover, the graph is port-labelled: for any node v ∈ Gr , the incident edges are assigned distinct local port numbers in the range [0, degr (v) − 1]. For an edge {u, v}, the port numbers at u and v are independently assigned and unrelated. Port labellings can differ across rounds; i.e., port numbers at a node in Gr may not match those in Gr′ for r ̸= r′ . Nodes do not have any 2
storage capability. In this work, the graph G(= ⟨G0 , G1 , G2 , . . .⟩) maintains the 1-interval connectivity, which says that Gr is connected at every round r. Agent, cycle, hole, multinode: We consider k agents initially placed at nodes. Each agent has a unique identifier from the range [1, nc ], for a constant c. An agent knows only its own ID, and is unaware of the values of n, k, and c. Agents are equipped with memory. An agent at node v in round r knows the set of ports incident to v in Gr . The algorithm proceeds in synchronous rounds. In each round r, every agent executes one Communicate– Compute–Move cycle. During the communicate, an agent exchanges information with other agents according to its communication capability. In the compute, it computes based on the available information. Finally, in the move, the agent either moves to a neighboring node or remains at its current node according to the computed decision. A node v ∈ Gr is called a hole in round r if it contains no agent, and a multinode if it contains two or more agents. Activation, fairness, move complexity: We consider the Ssync scheduler, where in each round an arbitrary subset of agents is activated. The activation pattern is controlled by an adversary with full knowledge of the agents’ algorithm and unbounded computational power, subject to the fairness condition, i.e., every agent is activated infinitely often. An agent not activated in round r is said to be inactive in that round. While each deactivation period is finite, its duration is unbounded, and an active agent has no information about its previous activations or events during inactivity. Due to unbounded deactivation periods, we measure time complexity using move complexity rather than round complexity. A move is the traversal of an edge by an agent during a round, and the move complexity is the total number of such moves made by all agents until task completion. Communication: In the ℓc -hop communication model, where ℓc ∈ [0, D̂], an agent at a node v can communicate to all agents located within ℓc hops from v. When ℓc = 0, this corresponds to face-to-face (f-2-f ) communication. When ℓc = D̂, the model corresponds to global communication. Visibility: We consider an ℓv -hop visibility model, where ℓv ∈ [0, D̂]. An agent located at a node w ∈ Gr can observe all nodes at distance at most ℓv from w in round r. In particular, it sees the subgraph of Gr induced by these nodes, along with the identifiers of the agents located at them. However, an agent cannot access the internal memory of other agents nor determine whether they are active or inactive. When ℓv = D̂, the model corresponds to full visibility. Problem definition: (Exploration) A node v is said to be visited by round r if there exists a round t ∈ [0, r] such that at least one agent is located at v in round t. An algorithm achieves exploration if every node is visited at least once. 1.2. Technical challenges, ideas and contributions The Ssync setting in dynamic graphs allows both agent activity and network structure to be controlled adversarially, making coordination and progress detection inherently difficult. Assume that the adversary can deactivate at most p(≥ 1) agents per round. 3
Consider a system with (n − 2)(p + 1) agents. If there is a hole vh at round r, then among the remaining n − 1 nodes, either there exists another hole, or there are at least two nodes that contain at most p agents. If the adversary may choose Gr arbitrarily in each round, it can always attach vh as a pendant to such a node. If this node is a hole, it is at least two hops away from the active agents; if it contains at most p agents, the adversary can deactivate all agents at that node, ensuring that vh remains unreachable by active agents. Thus, in every round, the adversary can maintain a node which remains unvisited. Based on this, we have the following result. Result 1. (refer to Theorem 2.1 and Observation 2.1) If the adversary can deactivate at most p agents per round, exploration is impossible with k ≤ (n − 2)(p + 1) agents, even with full visibility, unbounded node storage, unique identifier to the nodes, global communication, unbounded memory, and complete k parameter knowledge. Equivalently, for a given k, exploration is impossible if p ≥ n−2 −1. Hence, exploration with k agents k is solvable only when p ≤ n−2 − 2. Due to Result 1, if the adversary can deactivate at most p agents per round, at least (p + 1)(n − 2) + 1 agents are necessary. Consider a special configuration in which exactly (n − 2) nodes each contain (p + 1) agents and exactly one node contains a single agent; we denote this configuration by C ∗ . Suppose that at some round r the agents are in C ∗ and are equipped with 1-hop visibility. There is exactly one hole, vh . If at some round r1 ≥ r the hole vh is adjacent to a node containing p + 1 agents, then since the adversary can deactivate at most p agents, at least one agent at that node is active and can observe the hole using 1-hop visibility and move to vh . If vh is never adjacent to a node containing p + 1 agents, then in every round it is adjacent to the node containing the single agent. Due to the fairness, the agent is eventually activated in some round and can move to vh using its 1-hop visibility. Hence, in all cases, the hole is eventually visited. If an algorithm does not reach C ∗ , the adversary can always select a node containing at most p agents and deactivate all agents at that node. This shows that C ∗ is necessary to achieve the exploration using (p + 1)(n − 2) + 1 agents. Consider agents equipped with 1-hop visibility and f-2-f communication. If the initial configuration is not C ∗ , the adversary can prevent the system from ever reaching C ∗ . The idea is as follows. The adversary maintains a path P = v1 ∼ v2 ∼ · · · ∼ vn such that vn is unvisited by round r − 1 and α(vi ) ≥ α(vi+1 ) for all i ∈ [1, n − 2], where α(vi ) is the number of agents at vi at r. Knowing P , if the adversary pre-computes that agents would reach C ∗ at the end of round r, it modifies the graph by deleting and adding a single edge while preserving 1-interval connectivity. Since agents have only 1-hop visibility, this modification affects the decisions of only a constant number of nodes. A careful analysis shows that agents fail to reach the C ∗ configuration. We have the following result. Result 2. (refer to Theorem 2.2) Exploration is impossible to solve using (n − 2)(p + 1) + 1 agents in 1-interval connected graphs when agents have 1-hop visibility and f-2-f communication, even if nodes have unbounded storage, unique identifiers, agents have unbounded memory and complete parameter knowledge. 4
Consider agents equipped with global communication and 0-hop visibility. Suppose that at some round r there is a hole vh . With (p + 1)(n − 2) + 1 agents on the remaining nodes, either the agents are in configuration C ∗ or they are not. If the agents are not in configuration C ∗ , then regardless of how the agents are distributed over the remaining n−1 nodes, there exist at least two nodes, say v1 and v2 , each containing at most p agents. In this case, the adversary can select one such node, say v1 , attach vh as a pendant to v1 , and deactivate all agents at v1 . Consequently, no active agent can reach vh . If the agents are in configuration C ∗ , the adversary attaches vh as a pendant to the node v that contains exactly one agent. Even if all agents are active, the adversary, knowing the agents’ algorithm, can precompute the movement of the agent at node v and modify the port labeling so that the port chosen by the agent does not lead to vh . Since agents are equipped with 0-hop visibility and global communication, they cannot detect such a change in ports, and the agent at node v follows the same computation. In this way, the adversary can prevent exploration even when all agents are active. Based on this, we have the following result. Result 3. (refer to Theorem 2.3) Exploration is impossible to solve using (n − 2)(p + 1) + 1 agents in 1-interval connected graphs when agents have 0-hop visibility and global communication, even if nodes have unbounded storage, unique identifiers, agents have unbounded memory and complete parameter knowledge. Since Fsync is stronger than Ssync, the lower bound on k under Fsync also applies to Ssync. In [6], the model is the same as ours, and it is shown that exploration is impossible with n − 2 agents under Fsync, even with full visibility, global communication, unique node identifiers, unbounded memory, unbounded node storage, and complete knowledge of parameters. Hence, k ≥ n − 1 under Ssync. Using Results 1, 2, 3 and k ≥ n − 1, we obtain the following. Result 4. (refer to Observation 2.2) To solve exploration with (p + 1)(n − 2) + 1 agents, 1-hop visibility and 1-hop communication are necessary. Consequently, if exploration is solvable with k agents under an adversary deactivating at most p agents k per round, k−1 then k−1 − 1. Note that n−2 − 1 = n−2 for k ≥ (p + 1)(n − 2) + 1, which implies p ≤ n−2 A A+1 k ≥ n − 1 and n ≥ 3 as equality B = B − 1 is valid for natural numbers A, B. Thus, the bound matches Result 1. Further, we present an algorithm for exploration when agents are equipped with 1-hop visibility and global communication, and when k agents are present while the adversary can k−1 deactivate at most p = n−2 − 1 agents per round. Recall the pipeline strategy: if agents have complete knowledge of the snapshot Gr , a multinode w can push an agent along a shortest path to a hole v by simultaneously moving one agent along each edge of the path, thereby filling the hole without creating new ones. This strategy has been used under the Fsync scheduler [14, 12, 6, 13]; however, it becomes challenging under the Ssync scheduler. In particular, if all agents at some intermediate node are inactive in a round, progress toward the hole is blocked. To overcome this difficulty, our algorithm estimates p progressively. Agents are initially unaware of the parameters k, n, and p. Using 1-hop visibility, an agent can observe the number of agents at its neighboring nodes, although it 5
cannot distinguish active agents from inactive ones. Through global communication, agents broadcast their 1-hop information. If an agent observes that a neighboring node of some node containing an active agent has c agents but receives no message from any of them in a given round, it can infer that all c agents are inactive. Whenever c exceeds the agent’s current estimate of p, the estimate is updated. Using this estimate, agents repeatedly apply the pipeline strategy to fill either a hole or a node containing only inactive agents. Once agents observe that every node contains at most p + 1 agents, they fix a source node. Whenever at least one agent at the source is active, it initiates a pipeline toward a hole or a node with no active agents. We show that this process eventually leads the system either to configuration C ∗ or to a configuration in which every node contains at least one agent. Moreover, the algorithm can distinguish between these two situations. Based on this, we have the following algorithmic result. k−1 − 1 and agents have 1-hop visibility and Result 5. (refer to Theorem 3.1) If p ≤ n−2 global communication, we present an algorithm that solves exploration under the Ssync scheduler. The move complexity is O(k D̂), and each agent uses O(max{log n, log p}) memory. The algorithm requires no prior knowledge of the parameters. In the next section, we compare our results with the existing literature on dynamic graphs. 1.3. Related work Under fixed port labeling, the Ssync scheduler is introduced in [10]. Under the Ssync scheduler, an agent that attempts to move through a port whose corresponding edge is absent in a given round becomes inactive and remains so until reactivated in a later round. This behavior gives rise to the notion of an agent sleeping at a port, which leads to several variants of the model: (i) no simultaneity (NS), where a sleeping agent cannot move and has no guarantee of activation when the edge reappears; (ii) passive transport (PT), where a sleeping agent is automatically transported if the edge is present in the same round; and (iii) eventual transport (ET), where a sleeping agent cannot move but is guaranteed to be activated in a round in which the edge is present. In the dynamic port-labeling model considered in this work, the edge corresponding to each port is always present. Consequently, the notion of sleeping agents and sleep-based transport models is not applicable. We therefore adopt the Ssync model as used for static graphs, treating each snapshot Gr as a port-labeled static graph. In this setting, in each round r, an arbitrary subset of agents is active. To the best of our knowledge, there is no prior work that considers the Ssync scheduler in the dynamic port-labeling model. Graph exploration has been extensively studied in the literature [15, 16, 17, 18, 19, 11, 10, 7, 9, 13, 6]. Exploration in general dynamic graphs has been studied under various connectivity models, including 1-interval connected graphs [6], ℓ-bounded 1-interval connected graphs and temporally connected graphs [9], and connectivity time dynamic graphs [13]. Among these, ET-based Ssync is considered in [9]. Since our focus is on 1-interval connected graphs and the Ssync scheduler, we discuss in detail the results of [6, 9]. The dynamic graph model of [6] is identical to ours except that agents operate 6
under the Fsync scheduler. They show that n − 2 agents are insufficient for exploration and provide an algorithm that succeeds with n − 1 agents under 1-hop visibility and global communication. In [9], exploration is studied under the ET-based Ssync scheduler with fixed port labeling, assuming anonymous agents and node storage. In ℓ-bounded 1-interval connected graphs, they provide a tight analysis by proving that 2ℓ agents are insufficient while 2ℓ + 1 agents suffice, where ℓ is the maximum number of edge deletions per round. Since ℓ ≤ m − n + 1, O(n2 ) agents are always enough for exploration. In contrast, our results apply to any number of agents k and provide a tight threshold on the adversary’s deactivation power as a function of k and n. Specifically, given any O(nc ) agents for c ≥ 1, there exists a value of p such that exploration becomes impossible beyond that value. Moreover, the approach in [9] relies on fixed port labeling and node storage: one agent waits for a missing edge while the others execute a rotor-router strategy. Because at most ℓ edges can be deleted, at most 2ℓ agents become stuck, and one extra agent guarantees exploration due to the ET model. Such a strategy does not apply in our setting due to the dynamic port labeling and the lack of node storage. 2. Impossibility results In this section, we present the impossibility results. The high-level approach is outlined in Section 1.2. Theorem 2.1. (n ≥ 3, p ≥ 1) If the adversary deactivates at most p agents per round, exploration is impossible with (n−2)(p+1) agents in 1-interval connected graphs, even with full visibility, unbounded node storage, unique identifier to the nodes, global communication, unbounded memory, and complete parameter knowledge. Proof. Let v be a hole initially. If no hole existed initially, exploration would already be complete. We show that v remains a hole forever. For every round r ≥ 0, we construct a dynamic graph Gr from G so that all active agents are always at a distance of at least two from v. The construction of Gr based on the number of holes is as follows. Case 1 (At least two holes at the beginning of round r): Let w1 , w2 , . . . , wn be nodes at the beginning of round r. Assume that wn−1 and wn are holes. Without loss of generality, let wn = v. The adversary forms a clique from nodes w1 , w2 , . . . , wn−1 , and attach node wn as a pendant node to node wn−1 . In this case, the adversary does not deactivate any agent. In this case, all active agents are at a distance of at least two from wn . Case 2 (Exactly one hole at the beginning of round r): Let w1 , w2 , . . . , wn be nodes at the beginning of round r. Assume that wn−1 and wn are holes. Without loss of generality, let wn = v. In this case, all agents are at n − 1 nodes. Since (p +1)(n − 2) agents are present, there are at least two nodes which have ≤ p agents. Without loss of generality, let nodes wn−2 and wn−1 have at most p agents. For r ≥ 1, let w ∈ {wn−2 , wn } such that every agent was active at round r − 1. If r = 0, then let w = wn−2 . The adversary forms a clique from nodes w1 , w2 , . . . , wn−1 , and attach node wn as a pendant node to node wn−2 . 7
In this case, the deactivates all agents at node wn−2 . In this case, all active agents are at a distance of at least two from wn . We now show by induction that v remains a hole for all r ≥ 0. Base case r = 0. In both cases above, no active agent is adjacent to v. Thus v is still empty at the end of round 0. Induction step. Assume v is a hole at the end of round r. At the start of round r + 1, if there is another hole, we apply Case 1; otherwise, we apply Case 2. In both constructions, every active agent remains at a distance of at least two from v, so v remains a hole at the end of round r + 1. Fairness. Whenever the adversary deactivates agents at some node, these agents are reactivated in the following round. Thus, every agent is active infinitely often, and the schedule is fair. Since the proof does not rely on any limitations, it remains valid even if nodes have unbounded storage and unique identifiers, and agents have unbounded memory, full visibility, global communication and complete parameter knowledge. This completes the proof. Observation 2.1. If the adversary deactivates at most p agents per round, exploration is impossible to solve with kk ≤ (n − 2)(p + 1) agents. Equivalently, for a given k, exploration is impossible if p ≥ n−2 − 1. Hence, exploration with k agents is solvable only when k p ≤ n−2 − 2. By Theorem 2.1, at least (p + 1)(n − 2) + 1 agents are required when the adversary can deactivate at most p agents per round. We now study the necessary assumptions with (p + 1)(n − 2) + 1 agents. The proof of the following theorem is non-trivial, lengthy, and relies on extensive case analysis. Theorem 2.2. (n ≥ 9, p ≥ 1) If the adversary deactivates at most p agents per round, exploration is impossible with (n−2)(p+1)+1 agents in 1-interval connected graphs with 1hop visibility and f-2-f communication, even if nodes have unique identifiers and unbounded storage, and agents possess unbounded memory and complete parameter knowledge. Proof. Let G be a clique of size n. Consider any initial configuration with at least one hole, and agents are not in a C ∗ configuration. Label the nodes v1 , . . . , vn such that α(vi ) ≥ α(vi+1 ) for all i ∈ [1, n − 1], where α(vj ) denotes the initial number of agents at vj . As discussed in Section 1.2, if agents are in C ∗ configuration, agents can explore G using 1-hop visibility within finite but unbounded time. Therefore, we construct Gr so that the agents never reach configuration C ∗ at the end of round r, which leads exploration to fail. We use two notations for nodes. Let Hr be a graph at round r. For any node v ∈ Hr , let SHr (v) and EHr (v) denote the number of agents at the beginning and end of round r at v, respectively. Graph Cr at round r ≥ 0:
8
v1
v2
vn−4
vn−3
vn−2
vn−1
vn
wn−1
wn
Figure 1: The construction of C0 .
w1
w2
wn−4
wn−3
wn−2
Figure 2: The construction of Cr when EGr−1 (wn−1 ) = 0.
• r = 0 : Initial configuration is not C ∗ , and there is at least one hole. Without loss of generality, let vn be a hole at the beginning of round r = 0. Consider a path P0 := v1 ∼ v2 ∼ v3 ∼ . . . vn−1 ∼ vn . In this case, C0 = P0 (refer to Fig. 1). The adversary deactivates the agents as follows. – If there are at least one agent at node vn−1 , the adversary deactivates all agents at node vn−1 , and all other agents are active. – If there is no agent at node vn−1 , then it deactivates one agent at node vn−2 . • r ≥ 1 : At the end of round r − 1, let w1 , w2 , . . . ,wn−1 , wn (= vn ) be nodes. In Gr−1 , agents do not achieve C ∗ . Note that in Gr−1 , the value of degr (wn ) is 1 (we observe this fact after completing the construction of Gr ). We denote the neighbour of wn by wn−1 in Gr−1 . There are two possible cases: Case 1 (EGr−1 (wn−1 ) = 0): Without loss of generality, let w1 , w2 , . . . ,wn−2 be nodes such that EGr−1 (wi ) ≥ EGr (wi+1 ) for every i ∈ [1, n − 3]. Consider a path, Pr := w1 ∼ w2 ∼ w3 ∼ . . . wn−1 ∼ wn . In this case, Cr = Pr (refer to Fig. 2). In this case, the adversary deactivates agents as follows. – If EGr (wn−2 ) ≤ p, then it does not deactivate any agent. – If EGr (wn−2 ) ≥ p + 1, then it deactivates one agent at node wn−2 which was not deactivated in round r − 1. Such agent always exists as EGr (wn−2 ) ≥ p + 1. Case 2 (EGr−1 (wn−1 ) ̸= 0): Since agents do not achieve C ∗ at the end of round r−1, there is at least one node from set {w1 , w2 , . . . , wn−2 } which has ≤ p agents. Without loss of generality, let EGr−1 (wn−2 ) ≤ p. Consider w1 , w2 , . . . ,wn−3 , wn−1 be nodes such that EGr−1 (wi ) ≥ EGr (wi+1 ) for every i ∈ [1, n − 4] and EGr−1 (wn−3 ) ≥ EGr−1 (wn−1 ). Consider a path, Pr := w1 ∼ w2 ∼ w3 ∼ . . . wn−3 ∼ wn−1 ∼ wn−2 ∼ wn . In this case, Cr = Pr (refer to Fig. 3). The adversary deactivates all the agents at node wn−1 .
w1
w2
wn−4
wn−3
wn−1
wn−2
Figure 3: The construction of Cr when EGr−1 (wn−1 ) ̸= 0.
9
wn
γ2
γ1 X3
u1
u2
un−5
δ1
α2 X2
α1 X1
un−4 β2 un−3 β1 un−2
Y un−1
un
Y un−1
un
Figure 4: The pre-computation of agents in Cr .
γ2 u1
u2
un−5
δ1
α′2
γ1 X3
X2
X1 ′ ′ un−4 β2 un−3 β1 un−2
Figure 5: The construction of Cr′ when 2 ≤ Y ≤ p.
As per the aforementioned construction of Cr for round r ≥ 0, the graph is a path P = u1 ∼ u2 ∼ . . . ∼ un−2 ∼ un−1 ∼ un (= vn ). The values SCr (ui ) do not increase as we move from ui to ui+1 for every i ∈ [1, n − 3], and the agents are not in configuration C ∗ . Since the adversary knows the agents’ algorithm and the structure of Cr , it can precompute the agents’ movement and determine whether they would reach configuration C ∗ when Gr = Cr at the end of round r. If they do not reach C ∗ , the adversary simply forms Cr at the beginning of round r. If they would reach C ∗ , then the adversary instead forms Cr′ at the beginning of round r. We show that whenever the agents would reach C ∗ under Cr , they fail to reach C ∗ under Cr′ at the end of the same round. The construction of Cr′ depends on the value of SCr (u n−1 ). The reason why the agents fail to reach configuration C ∗ when Gr = Cr′ is described below. Let SCr (un−1 ) = Y , SCr (un−2 ) = X1 , SCr (un−3 ) = X2 , and SCr (un−4 ) = X3 . Based on the pre-computation of agent movements in Cr is as follows (refer to Fig. 4): • From node un−2 : α1 agent(s) move to un−1 , and α2 agent(s) move to un−3 . • From node un−3 : β1 agent(s) move to un−2 , and β2 agent(s) move to un−4 . • From node un−4 : γ1 agent(s) move to un−3 , and γ2 agent(s) move to un−5 . • From node un−5 : δ2 agent(s) move to un−4 . Case 1 (2 ≤ Y ≤ p): In this case we have α1 = p + 1 − Y , because all agents at node un−1 are deactivated in Cr . Thus, the only way to reach configuration C ∗ at the end of round r is to increase the number of agents at un−1 to exactly p + 1. Due to 2 ≤ Y ≤ p, the following inequality holds. 1 ≤ α1 ≤ p − 1
(1)
As per pre-computation, the following equations should hold at the end of round r in Cr . X1 − (α1 + α2 ) + β1 = 1 or p + 1 X2 − (β1 + β2 ) + (α2 + γ1 ) = 1 or p + 1 10
(2) (3)
The adversary constructs Cr′ as follows. In path P = u1 ∼ u2 ∼ . . . ∼ un−2 ∼ un−1 ∼ un (= vn ), the adversary removes edge between node un−2 and un−1 , and add an edge between node u1 and un−1 . In configuration Cr′ , the adversary deactivates exactly the same agents that were deactivated in Cr . This new graph is Cr′ , and constructed as Gr at the beginning of round r. In this graph, the 1-hop view of agents at node u1 , u2 , un−3 , un−2 , un−1 is changed, and the remaining agents at nodes ui , i ∈ [3, n − 4] have the same 1-hop view as in Cr as we consider n ≥ 9. Since agents are equipped with 1-hop visibility and f-2-f communication, the movement of agents at nodes u1 , u2 , un−3 , un−2 , un−1 in Cr′ may not be the same as Cr , and other remaining agent’s movement in Cr′ remains the same as in Cr . Therefore, let α2′ agent(s) move from node un−2 to un−3 , and from node un−3 , let β1′ agent(s) move to un−2 and β2′ agent(s) move to un−4 . We can see this in Fig. 5. • Case 1.1: As per pre-computation in Cr , the following equations hold. X1 − (α1 + α2 ) + β1 = 1 X2 − (β1 + β2 ) + (α2 + γ1 ) = p + 1
(4) (5)
After taking the sum of Eq. 4 and Eq. 5, we get the following equation. X1 + X 2 − β 2 − α 1 + γ 1 = p + 2
(6)
The agent’s movement in Cr′ leads to the following equations. X1 − α2′ + β1′ = 1 or p + 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = 1 or p + 1
(7) (8)
We show in each case that movement of agents in Cr′ does not lead to C ∗ . – Case 1.1.1: Consider the following equations hold. X1 − α2′ + β1′ = p + 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = 1
(9) (10)
Since in Cr we have ECr (un−4 ) = p + 1, and in Cr′ we have ECr′ (un−2 ) = 1 and ECr′ (un−3 ) = p + 1, the only way to reach C ∗ in Cr′ that ECr′ (un−4 ) also becomes p + 1 is to keep β2 = β2′ as n ≥ 8. Hence, after taking the sum of Eq. 9 and Eq. 10, we get the following equation. X1 + X 2 − β 2 + γ 1 = p + 2
(11)
From Eq. 6 and Eq. 11, we have the following. X1 + X2 − β2 − α1 + γ1 = X1 + X2 − β2 + γ1 =⇒ α1 = 0 Eq. 1 and Eq. 12 lead to the contradiction. 11
(12)
– Case 1.1.2: Consider the following equations hold. X1 − α2′ + β1′ = p + 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = 1
(13) (14)
Since in Cr we have ECr (un−4 ) = p + 1, and in Cr′ we have ECr′ (un−2 ) = 1 and ECr′ (un−3 ) = p + 1, the only way to reach C ∗ in Cr′ that ECr′ (un−4 ) also becomes p + 1 is to keep β2 = β2′ as n ≥ 8. Hence, after taking the sum of Eq. 13 and Eq. 14, we get the following equation. X1 + X 2 − β 2 + γ 1 = p + 2
(15)
From Eq. 6 and Eq. 15, we have the following. X1 + X2 − β2 − α1 + γ1 = X1 + X2 − β2 + γ1 =⇒ α1 = 0
(16)
Eq. 1 and Eq. 16 lead to the contradiction. – Case 1.1.3: Consider the following equations hold. X1 − α2′ + β1′ = p + 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = p + 1
(17) (18)
Since in Cr we have ECr (un−4 ) = p + 1, and in Cr′ we have ECr′ (un−2 ) = p + 1 and ECr′ (un−3 ) = p + 1, the value of ECr′ (un−4 ) is either p + 1 or 1. The value of ECr′ (un−4 ) = 1 if β2′ = β2 − p, and the value of ECr′ (un−4 ) = p + 1 if β2′ = β2 as the view of node un−5 and un−4 are the same in Cr′ . Hence, after taking the sum of Eq. 17 and Eq. 18, we get the following equation. X1 + X2 − β2′ + γ1 = 2p + 2
(19)
From Eq. 6 and Eq. 19, we have the following. p + X1 + X2 − β2 − α1 + γ1 = X1 + X2 − β2′ + γ1 =⇒ α1 = p − β2 + β2′ =⇒ α1 = 0 if β2′ = β2 − p and α1 = p if β2′ = β2
(20)
Eq. 1 and Eq. 20 lead to the contradiction. – Case 1.1.4: Consider the following equations hold. X1 − α2′ + β1′ = 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = 1
(21) (22)
This case shows that agents are not in C ∗ form at the end of round r. As in C ∗ , there is exactly one node with one agent. 12
• Case 1.2: As per pre-computation in Cr , the following equations hold. X1 − (α1 + α2 ) + β1 = p + 1 X2 − (β1 + β2 ) + (α2 + γ1 ) = 1 In this case, the analysis is analogous to Case 1.1. • Case 1.3: As per pre-computation in Cr , the following equations hold. X1 − (α1 + α2 ) + β1 = p + 1 X2 − (β1 + β2 ) + (α2 + γ1 ) = p + 1
(23) (24)
After taking the sum of Eq. 23 and Eq. 24, we get the following equation. X1 + X2 − β2 − α1 + γ1 = 2p + 2
(25)
In this sub-case, the following equality holds at node un−4 in Cr . X3 − (γ1 + γ2 ) + δ2 + β2 = 1 or p + 1
(26)
The agent’s movement in Cr′ leads to the following equations. X1 − α2′ + β1′ = 1 or p + 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = 1 or p + 1
(27) (28)
– Case 1.3.1: Consider the following holds. X3 − (γ1 + γ2 ) + δ2 + β2 = 1
(29)
In this case, the value of β2′ is either β2 or β2 + p as n ≥ 8; otherwise the number of agents at un−4 would be neither p + 1 nor 1 in Cr′ . ∗ Case 1.3.1.1: Consider the following equations hold. X1 − α2′ + β1′ = 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = p + 1
(30) (31)
If the value of β2′ = β2 , there will be two nodes (node un−4 and node un−2 ) in Cr′ which have only one agent, which is not a C ∗ . If the value of β2′ = β2 + p, then due to the following reasoning, we have a contradiction. After taking the sum of Eq. 30 and Eq. 31, we get the following equation. X1 + X2 − β2′ + γ1 = p + 2 =⇒ X1 + X2 − β2 + γ1 = 2p + 2 as β2′ = β2 + p (32) Due to Eq. 25 and Eq. 32, we have the following equation. X1 + X2 − β2 − α1 + γ1 = X1 + X2 − β2 + γ1 =⇒ α1 = 0 Due to Eq. 1 and Eq. 33, we have a contradiction. 13
(33)
∗ Case 1.3.1.2: Consider the following equations hold. X1 − α2′ + β1′ = p + 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = 1
(34) (35)
If the value of β2′ = β2 , there will be two nodes (node un−4 and node un−3 ) in Cr′ which have only one agent, which is not a C ∗ . If the value of β2′ = β2 + p, then due to the following reasoning, we have a contradiction. After taking the sum of Eq. 34 and Eq. 35, we get the following equation. X1 + X2 − β2′ + γ1 = p + 2 =⇒ X1 + X2 − β2 + γ1 = 2p + 2 as β2′ = β2 + p (36) Due to Eq. 25 and Eq. 36, we have the following equation. X1 + X2 − β2 − α1 + γ1 = X1 + X2 − β2 + γ1 =⇒ α1 = 0
(37)
Due to Eq. 1 and Eq. 37, we have a contradiction. ∗ Case 1.3.1.3: Consider the following equations hold. X1 − α2′ + β1′ = p + 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = p + 1
(38) (39)
After taking the sum of Eq. 38 and Eq. 39, we get the following equation. X1 + X2 − β2′ + γ1 = 2p + 2
(40)
Due to Eq. 25 and Eq. 40, we have the following equation. X1 + X2 − β2 − α1 + γ1 = X1 + X2 − β2′ + γ1 =⇒ α1 = β2′ − β2
(41)
In Eq. 41, if β2′ = β2 (resp. β2′ = β2 + p), then α1 = 0 (resp. α1 = p). This leads to a contradiction due to Eq. 1. ∗ Case 1.3.1.4: Consider the following equations hold. X1 − α2′ + β1′ = 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = 1
(42) (43)
This case shows that agents are not in C ∗ form at the end of round r. As in C ∗ , there is exactly one node with one agent. – Case 1.3.2: If the following holds. X3 − (γ1 + γ2 ) + δ2 + β2 = p + 1
(44)
In this case, the value of β2′ is either β2 or β2 − p as n ≥ 8; otherwise the number of agents at un−4 would be neither p + 1 nor 1 in Cr′ . 14
∗ Case 1.3.2.1: Consider the following equations hold. X1 − α2′ + β1′ = 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = p + 1
(45) (46)
If the value of β2′ = β2 − p, there will be two nodes (node un−4 and node un−2 ) in Cr′ which have only one agent, which is not a C ∗ . If the value of β2′ = β2 , then due to the following reasoning, we have a contradiction. After taking the sum of Eq. 45 and Eq. 46, we get the following equation. X1 + X2 − β2′ + γ1 = p + 2 =⇒ X1 + X2 − β2 + γ1 = p + 2 as β2′ = β2 (47) Due to Eq. 25 and Eq. 47, we have the following equation. X1 + X2 − β2 − α1 + γ1 = p + X1 + X2 − β2 + γ1 =⇒ α1 = −p
(48)
Due to Eq. 1 and Eq. 48, we have a contradiction. ∗ Case 1.3.2.2: Consider the following equations hold. X1 − α2′ + β1′ = p + 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = 1
(49) (50)
If the value of β2′ = β2 − p, there will be two nodes (node un−4 and node un−3 ) in Cr′ which have only one agent, which is not a C ∗ . If the value of β2′ = β2 , then due to the following reasoning, we have a contradiction. After taking the sum of Eq. 49 and Eq. 50, we get the following equation. X1 + X2 − β2′ + γ1 = p + 2 =⇒ X1 + X2 − β2 + γ1 = p + 2 as β2′ = β2 (51) Due to Eq. 25 and Eq. 51, we have the following equation. X1 + X2 − β2 − α1 + γ1 = p + X1 + X2 − β2 + γ1 =⇒ α1 = −p
(52)
Due to Eq. 1 and Eq. 52, we have a contradiction. ∗ Case 1.3.2.3: Consider the following equations hold. X1 − α2′ + β1′ = p + 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = p + 1
(53) (54)
After taking the sum of Eq. 53 and Eq. 54, we get the following equation. X1 + X2 − β2′ + γ1 = 2p + 2
(55)
Due to Eq. 25 and Eq. 55, we have the following equation. X1 + X2 − β2 − α1 + γ1 = X1 + X2 − β2′ + γ1 =⇒ α1 = β2′ − β2
(56)
In Eq. 56, if β2′ = β2 (resp. β2′ = β2 − p), then α1 = 0 (resp. α1 = −p). This leads to a contradiction due to Eq. 1. 15
γ2′
γ1′ X3
u1
u2
un−5
δ1
α′1 X2
X1
un−4 β2 un−3
un−2
′
Y un−1
un
Figure 6: The construction of Cr′ when Y = 1.
∗ Case 1.3.2.4: Consider the following equations hold. X1 − α2′ + β1′ = 1 X2 − (β1′ + β2′ ) + (α2′ + γ1 ) = 1
(57) (58)
This case shows that agents are not in C ∗ form at the end of round r. As in C ∗ , there is exactly one node with one agent. Case 1.4: As per pre-computation in Cr , the following equations hold. X1 − (α1 + α2 ) + β1 = 1 X2 − (β1 + β2 ) + (α2 + γ1 ) = 1
(59) (60)
This case shows that agents are not in C ∗ form at the end of round r. As in C ∗ , there is exactly one node with one agent. Case 2 (Y = 1): In this case, 0 ≤ X1 ≤ p as if X1 ≥ p + 1, every node ui , i ∈ [1, n − 3] has at least p + 1. Since agents are not in C ∗ configuration at the beginning of round r, the total number of agents becomes more than (n − 2)(p + 1) + 1, which is not possible. Therefore, the value of X1 belongs to [0, p]. The adversary constructs Cr′ as follows. In path P = u1 ∼ u2 ∼ . . . ∼ un−2 ∼ un−1 ∼ un (= vn ), the adversary removes edge between node un−3 and un−2 , and add an edge between node u1 and un−1 . In configuration Cr′ , the adversary deactivates exactly the same agents that were deactivated in Cr . This new graph is Cr′ , and constructed as Gr at the beginning of round r. In this graph, the 1-hop view of agents at node u1 , u2 , un−4 , un−3 , un−2 , un−1 is changed, and the remaining agents at nodes ui , i ∈ [3, n − 5] have the same 1-hop view as in Cr . Since agents are equipped with 1-hop visibility and f-2-f communication, the movement of agents at nodes u1 , u2 , un−4 , un−3 , un−2 , un−1 in Cr′ may not be the same as Cr , and other remaining agent’s movement in Cr′ remains the same as in Cr . Therefore, let α1′ agent(s) move from node un−2 to un−1 , from node un−3 , let β2′ agent(s) move to un−4 , and from node un−4 , let γ1′ agent(s) move to un−3 and γ2′ agent(s) move to un−5 . We can see this in Fig. 6. If X1 = 0, then no matter how agents move, node un−2 remains a hole as the agent at node un−1 is not active. Therefore, at the end of round r, nodes un−2 and un remain the hole. The number of agents at node un−2 in Cr′ has to become 1 at the end of round r as node un−2 cannot have p + 1 agents due to the fact agent at node un−1 is deactivated. Therefore, in Cr′ , the following equality should hold. X2 − β2′ + γ1′ = p + 1 X3 − (γ1′ + γ2′ ) + δ1 + β2′ = p + 1 16
(61) (62)
After taking the sum of Eq. 61 and Eq. 62, we get the following equation. X2 + X3 − γ2′ + δ1 = 2p + 2
(63)
• Case 2.1 (X1 ∈ [1, p − 1]): Since one agent is deactivated at node un−1 and 1 ≤ X1 ≤ p − 1, therefore the number of agents at node un−1 in Cr cannot be p + 1 at the end of round r. If agents achieve C ∗ at the end of round r when Gr = Cr , then the value of α1 is 0, and the following equations hold at the end of round r in Cr (refer to Figure 4). X1 − α 2 + β 1 = p + 1 X2 − (β1 + β2 ) + (α2 + γ1 ) = p + 1 X3 − (γ1 + γ2 ) + δ1 + β2 = p + 1
(64) (65) (66)
After taking the sum of Eq. 65 and Eq. 66, we get the following equation. X2 + X3 − γ2 − β1 + δ1 + α2 = 2p + 2
(67)
In this case, the value of γ2′ = γ2 as in Cr (resp Cr′ ), node un−1 (resp. un−2 ) becomes a node with 1 agent at the end of round r. Therefore, from Eq. 67 and Eq. 63, we have β1 = α2 using γ2′ = γ2 . If we put β1 = α2 in Eq. 64, we get X1 = p + 1. This leads to a contradiction as X1 ∈ [1, p − 1] in this case. • Case 2.2 (X1 = p): In this case, the value of α1 = 0 or p due to the following reason. Since agents achieve C ∗ at the end of round r and one agent at node un−1 is deactivated, the ECr (un−1 ) is either 1 or p + 1 which is possible when α1 = 0 and α1 = p, respectively. – Case 2.2.1 (α1 = 0): In this case, the number of agents at node un−1 in Cr is 1 at the end of round r. If agents achieve C ∗ at the end of round r when Gr = Cr , then the following equations hold at the end of round r in Cr . X1 − α2 + β 1 = p + 1 X2 − (β1 + β2 ) + (α2 + γ1 ) = p + 1 X3 − (γ1 + γ2 ) + δ1 + β2 = p + 1
(68) (69) (70)
After taking the sum of Eq. 69 and Eq. 70, we get the following equation. X2 + X3 − γ2 − β1 + δ1 + α2 = 2p + 2
(71)
In this case, the value of γ2′ = γ2 as in Cr (resp Cr′ ), node un−1 (resp. un−2 or un−1 ) becomes a node with 1 agent at the end of round r. Therefore, from Eq. 63 and Eq. 71, we have β1 = α2 using γ2′ = γ2 . If we put β1 = α2 in , we get X1 = p + 1. This leads to a contradiction as X1 = p in this case. 17
– Case 2.2.2 (α1 = p): In this case, the number of agents at node un−1 in Cr is p + 1 at the end of round r. Since X1 = p and α1 = p, the value of α2 = 0. If agents achieve C ∗ at the end of round r when Gr = Cr , then the following equations hold at the end of round r in Cr . X1 − (α1 + α2 ) + β1 = 1 or p + 1 X2 − (β1 + β2 ) + (α2 + γ1 ) = 1 or p + 1 X3 − (γ1 + γ2 ) + δ1 + β2 = 1 or p + 1
(72) (73) (74)
∗ Case 2.2.2.1: Consider the following holds: X1 − (α1 + α2 ) + β1 = 1 =⇒ β1 = 1 as X1 = α1 = p, α2 = 0
(75)
Therefore, the following equation holds in Cr at the end of round r. X2 − (β1 + β2 ) + (α2 + γ1 ) = p + 1 X3 − (γ1 + γ2 ) + δ1 + β2 = p + 1
(76) (77)
After taking the sum of Eq. 76 and Eq. 77, we get the following equation using α2 = 0. X2 + X3 − γ2 − β1 + δ1 = 2p + 2
(78)
In this case, the value of γ2′ = γ2 in Cr′ as the number of agents at node un−5 in Cr and Cr′ is p + 1; otherwise there will be two nodes with one agent in Cr′ . Using Eq. 63 and Eq. 78, we have β1 = 0, which leads to a contradiction due to Eq. 75. ∗ Case 2.2.2.2: Consider the following holds: X1 − (α1 + α2 ) + β1 = p + 1 =⇒ β1 = p + 1 as X1 = α1 = p, α2 = 0 (79) Therefore, the following equation holds in Cr at the end of round r. X2 − (β1 + β2 ) + (α2 + γ1 ) = 1 or p + 1 X3 − (γ1 + γ2 ) + δ1 + β2 = 1 or p + 1 → Case 2.2.2.2.1: Consider the following holds. X2 − (β1 + β2 ) + (α2 + γ1 ) = 1 X3 − (γ1 + γ2 ) + δ1 + β2 = p + 1
(80) (81)
After taking the sum of Eq. 80 and Eq. 81, we have the following using α2 = 0. X2 + X 3 − γ 2 − β 1 + δ 1 = p + 2 18
(82)
γ2′
γ1′ X3
u1
u2
un−5
δ1
α′1 X2
X1
un−4 β2 un−3
un−2
′
un−1
un
Figure 7: The construction of Cr′ when Y = 0.
In this case, the value of γ2′ = γ2 in Cr′ as the number of agents at node un−5 in Cr and Cr′ is p + 1; otherwise there will be two nodes with one agent in Cr′ . Therefore, using Eq. 63 and Eq. 82, we have β1 = p, which leads to a contradiction due to Eq. 79. → Case 2.2.2.2.2: Consider the following holds. X2 − (β1 + β2 ) + (α2 + γ1 ) = p + 1 X3 − (γ1 + γ2 ) + δ1 + β2 = 1
(83) (84)
After taking the sum of Eq. 83 and Eq. 84, we have the following. X2 + X 3 − γ 2 − β 1 + δ 1 = p + 2
(85)
In this case, the value of γ2′ = γ2 in Cr′ as the number of agents at node un−4 in Cr and Cr′ is p + 1; otherwise there will be two nodes with one agent in Cr′ . Therefore, using Eq. 63 and Eq. 85, we have β1 = p, which leads to a contradiction due to Eq. 79. → Case 2.2.2.2.3: Consider the following holds. X2 − (β1 + β2 ) + (α2 + γ1 ) = p + 1 X3 − (γ1 + γ2 ) + δ1 + β2 = p + 1
(86) (87)
After taking the sum of Eq. 86 and Eq. 87, we have the following using α2 = 0. X2 + X3 − γ2 − β1 + δ1 = 2p + 2
(88)
In this case, the number of agents at node un−5 at the end of round r is either 1 or p + 1 in Cr . Since at the end of round r, the number of agents at node un−2 is 1 in Cr′ , the number of agents at node un−5 has to be p + 1 at the end of round r in Cr′ . Hence, γ2′ = γ2 (resp. γ2′ = γ2 + p) if the number of agents at the node un−5 at the end of round r is p + 1 (resp. 1) in Cr . In both cases, the value of β1 ̸= p + 1 using Eq. 63 and Eq. 88 leads to a contradiction due to Eq. 79 Case 3 (Y = 0): In this case, X1 ≥ p+2 is not possible as this leads to at least (n−2)(p+2) agents in the system but we have total (p + 1)(n − 2) + 1 many agents. Also, X1 = 0 is not possible as no matter how agents move in Cr , there will be at least two holes as all 19
agents are deactivated at node un−2 . Therefore, the value of X1 is in [1, p + 1]. If the value of X1 is from [1, p], and agents achieve C ∗ at the end of round r in Cr , then node un−1 has to become a node with one agent at the end of round r, i.e., α1 = 1. If the value of X1 is p + 1, then the adversary deactivates 1 agent at node un−2 in Cr (which was not deactivated earlier). In this case, if agents achieve C ∗ at the end of round r in Cr , node un−1 has to become a node with one agent, i.e., α1 = 1. Therefore, the following holds in Cr at the end of round r when 1 ≤ X1 ≤ p + 1. X1 − (α1 + α2 ) + β1 = p + 1 X2 − (β1 + β2 ) + (α2 + γ1 ) = p + 1 X3 − (γ1 + γ2 ) + δ1 + β2 = p + 1
(89) (90) (91)
After taking the sum of Eq. 90 and Eq. 91, we get the following equation. X2 + X3 − γ2 − β1 + δ1 = 2p + 2
(92)
The adversary constructs Cr′ as follows. In path P = u1 ∼ u2 ∼ . . . ∼ un−2 ∼ un−1 ∼ un (= vn ), the adversary removes edge between node un−3 and un−2 , and add an edge between node u1 and un−2 . In configuration Cr′ , the adversary deactivates exactly the same agents that were deactivated in Cr . This new graph is Cr′ , and constructed as Gr at the beginning of round r. In this graph, the 1-hop view of agents at nodes u1 , u2 , un−4 , un−3 , un−2 , un−1 are changed, and the remaining agents at nodes ui , i ∈ [3, n − 5] have the same 1-hop view as in Cr . Since agents are equipped with 1-hop visibility and f-2-f communication, the movement of agents at nodes u1 , u2 , un−4 , un−3 , un−2 , un−1 in Cr′ may not be the same as Cr , and other remaining agent’s movement in Cr′ remains the same as in Cr . Therefore, let α1′ agent(s) move from node un−2 to un−1 , from node un−3 , let β2′ agent(s) move to un−4 , and from node un−4 , let γ1′ agent(s) move to un−3 and γ2′ agent(s) move to un−5 . We can see this in Fig. 7. In Cr′ , the number of agents at node un−1 has to become 1; otherwise, at the end of round r in Cr′ , node un−1 is either a hole or has agents between 2 and p. Therefore, the following inequality must hold. X2 − β2′ + γ1′ = p + 1 X3 − (γ1′ + γ2′ ) + δ1 + β2′ = p + 1
(93) (94)
After taking the sum of Eq. 93 and Eq. 94, we get the following equation. X2 + X3 − γ2′ + δ1 = 2p + 2
(95)
In this case, the value of γ2′ = γ2 as in Cr and Cr′ , node un−1 becomes a node with 1 agent at the end of round r. Therefore, from Eq. 92 and Eq. 95, we have β1 = 0 using γ2′ = γ2 . Since β1 = 0, α1 = 1 and X1 ∈ [1, p + 1], therefore, X1 − (α1 + α2 ) + β2 ≤ p. This leads to a contradiction due to Eq. 89. 20
Fairness. The set of deactivated agents remains identical in Cr and Cr′ for every r ≥ 0. Moreover, Gr is defined to be either Cr or Cr′ . By construction, when forming Cr + 1 from Gr , every agent that was deactivated in round r becomes activated in round r + 1. Therefore, no agent remains deactivated forever, which ensures fairness. It is clear to observe that in construction Cr and Cr′ , the degree of node wn (= vn ) remains one. Further, since the proof does not rely on any limitation on node storage, agent memory, or agent knowledge, it remains valid even if nodes are equipped with unbounded storage and agents have unbounded memory and complete parameter knowledge. This completes the proof. Theorem 2.3. (n ≥ 3, p ≥ 1) If the adversary deactivates at most p agents per round, exploration is impossible with (n−2)(p+1)+1 agents in 1-interval connected graphs with 0-hop visibility and global communication, even if nodes have unique identifiers and unbounded storage, and agents possess unbounded memory and complete parameter knowledge. Proof. Let G be a clique of size n. Consider any initial configuration with at least one hole. Label the nodes v1 , . . . , vn such that α(vi ) ≥ α(vi+1 ) for all i ∈ [1, n − 1], where α(vj ) denotes the initial number of agents at vj . We construct Gr such that vn remains a hole forever. We use two notations. Let Hr be a graph at round r. For any node v ∈ Hr , let SHr (v) and EHr (u) denote the number of agents at the beginning and end of round r in Hr , respectively. Graph C0 : Consider a path P0 := v1 ∼ v2 ∼ v3 ∼ . . . vn−1 ∼ vn . In this case, C0 = P0 . The adversary deactivates the agents as follows. • If there are at least two agents at node vn−1 , the adversary deactivates all agents at node vn−1 , and all other agents are active. The adversary can deactivate all agents, since node vn−1 can contain at most p agents. If not, α(vi ) ≥ p + 1, i ∈ [1, n − 1], as α(vi ) ≥ α(vi+1 ) for every i ∈ [1, n − 1]. In this case, the total number of agents is at least (n − 1)(p + 1), which is more than (n − 2)(p + 1) + 1. • If there is at most one agent at node vn−1 , it does not deactivate any agent in C0 . Graph Cr at round r ≥ 1: At round r − 1, let w1 , w2 , . . . ,wn−1 , wn (= vn ) be nodes in Gr−1 . Note that in Gr−1 , the value of degr (wn ) is 1 (we observe this fact after completing the construction of Gr ). Without loss of generality, let wn−1Sbe the neighbour Gr−1 . Sn of wn in n ′ ′ ′ ′ ′ Let w1 , w2 , . . . , wn be an ordering of the nodes such that i=1 {wi } = i=1 {wi }, wn = wn ′ and EGr−1 (wi′ ) ≥ EGr−1 (wi+1 ) for every i ∈ [1, n − 1]. There are two possible cases: ′ • Case 1 ∃ w ∈ {w1′ , w2′ , . . . , wn−1 } such that EGr−1 (w) ≤ 1 : In this case, ′ ′ EGr−1 (wn−1 ) ≤ 1. Consider a path, Pr := w1′ ∼ w2′ ∼ w3′ ∼ . . . wn−1 ∼ wn′ (= wn = vn ). In this case, Cr = Pr , and the adversary does not deactivate any agent in Cr . ′ • Case 2 ∄ w ∈ {w1′ , w2′ , . . . , wn−1 } such that EGr−1 (w) ≤ 1 : The value of ′ EGr−1 (wn−1 ) is at most p. If not, we have EGr−1 (wi′ ) ≥ p + 1 for every i ∈ [1, n − 1], 21
implying that the total number of agents is at least (p + 1)(n − 1), which is greater ′ ′ ) ∈ [2, p], ) ∈ [2, p]. Since EGr−1 (wn−1 than (p + 1)(n − 2) + 1. Therefore, EGr−1 (wn−1 ′ ′ the value of EGr−1 (wn−2 ) is at most p. If wn−1 ̸= wn−1 , then the adversary defines the ′ ∼ wn′ (= wn = vn ), and deactivates all agents path Pr := w1′ ∼ w2′ ∼ w3′ ∼ · · · ∼ wn−1 ′ ′ at node wn−1 , while keeping all other agents active. Otherwise, if wn−1 = wn−1 , the ′ ′ ′ ′ ′ ′ adversary defines Pr := w1 ∼ w2 ∼ w3 ∼ · · · ∼ wn−1 ∼ wn−2 ∼ wn (= wn = vn ), and ′ deactivates all agents at node wn−2 , keeping all other agents active. In both cases, Cr = Pr . As per the construction of Cr for round r ≥ 0, the graph is a path P = u1 ∼ u2 ∼ . . . ∼ un−2 ∼ un−1 ∼ un (= vn ). The values SCr (ui ) do not increase as we move from ui to ui+1 for every i ∈ [1, n − 3], and SCr (un−1 ) ≤ p. Since the adversary knows the agents’ algorithm and the structure of Cr , it can pre-compute the agents’ movement and determine whether one of the agents visits node vn when Gr = Cr at the end of round r. If not, the adversary simply forms Gr = Cr at the beginning of round r. Otherwise, the adversary instead forms Cr′ at the beginning of round r. We show that whenever one of the agents visits node vn under Cr , node vn is not visited by any agent under Cr′ at the end of round r. The construction of Cr′ depends on the value of SCr (u n−1 ). Let SCr (un−1 ) = Y . Since SCr (un−1 ) ≤ p, it follows that Y ∈ [0, p]. λ1 u1
u2
un−2
Y un−1
λ2
λ2 u1
un
Figure 8: The construction of Cr when Y = 1.
u2
un−2
Y un−1
λ1 un
Figure 9: The construction of Cr′ when Y = 1.
• Y ∈ [0, p] \ {1}: Since either no agent is present at node un−1 or all agents at node un−1 are not active in configuration Cr , node un is at a distance of at least two from every active agent in Cr . • Y = 1: In this case, all agents are active. If node un is to be visited by some agent, then the agent located at node un−1 must move to un . Let λ1 denote the outgoing port at node un−1 leading to node un−2 , and let λ2 denote the outgoing port at node un−1 leading to node un (refer to Fig. 8). We now describe the construction of the configuration Cr′ . Agents are equipped with global communication and 0-hop visibility; hence, an agent can sense only the outgoing ports of the node it currently occupies. The adversary constructs Cr′ so that the 0-hop visibility view of every agent in Cr′ is identical to that in Cr . Consequently, even with global communication, agents cannot detect that the configuration has changed. Therefore, any port choice made by an agent in Cr is also made in Cr′ . Let Pr′ = u1 ∼ u2 ∼ · · · ∼ un−2 ∼ un−1 ∼ un (= vn ), where, in Cr′ , the outgoing port λ1 at node un−1 leads to node un , and the outgoing port λ2 leads to node un−2 (refer to Fig. 9). Thus, Cr′ is the path Pr′ , and the adversary forms Cr′ as the snapshot Gr instead of Cr . Since the 0-hop visibility of every agent is identical in Cr and Cr′ , the agents compute the same port choices in 22
both configurations. As a result, if an agent at node un−1 selects port λ2 in Cr to move to node un , it selects the same port in Cr′ and instead moves to node un−2 . Consequently, node un is not visited by any active agent at the end of round r. Since this argument is valid for every r ≥ 0, no active agent visits node vn at any round r. Fairness. The way we construct Cr from Gr−1 , it is trivial that those agents which were deactivated in round r − 1 are activated in round r. This guarantees fairness. Since the proof does not rely on any limitations except 0-hop visibility and global communication, it remains valid even if nodes have unbounded storage and unique identifiers, and agents have unbounded memory and complete parameter knowledge. This completes the proof. Due to Theorem 2.2 and Theorem 2.3, we have the following observation. Observation 2.2. For 1-interval connected graphs on n nodes, exploration against an adversary that can deactivate at most p agents per round might be possible using (n−2)(p+ 1) + 1 agents when agents have 1-hop visibility and 1-hop communication. Consequently, if exploration is solvable with k agents under an adversary deactivating at most p agents k−1 per round, then k ≥ (p + 1)(n − 2) + 1, which implies p ≤ n−2 − 1. 3. Exploration in 1-interval connected graphs In this section, we present Ssync_EX PO for exploration in 1-interval connected graphs under the Ssync scheduler. The high-level idea of our approach is in Section 1.2. Let Gr = (V, E(r)) denote the graph at round r. In the graph, there are k agents, and the k−1 − 1 agents per round. Agents are equipped adversary can deactivate at most p = n−2 with 1-hop visibility and global communication1 . Based on the active agents in Gr , we introduce the following notion. Definition 1. (Connected components of active agents in Gr ) The graph Gr can be partitioned into subgraphs Gr1 , Gr2 , . . . , Grℓ , where each Grj = (Vj , Ej ) for 1 ≤ j ≤ ℓ, such that: (i) For every u ∈ Vj , at least one active agent is present at u, (ii) For all j ̸= i, Vj ∩ Vi = ∅, and (iii) There is no edge e = (u1 , u2 ) ∈ E(r) with u1 ∈ Vj and u2 ∈ Vi for j ̸= i. We denote by CCA(Gr ) the collection of all such subgraphs. Intuitively, CCA(Gr ) represents the connected components of the subgraph of Gr induced by nodes that host at least one active agent. Notation and parameters: Each agent A maintains the following parameters. The variable A.ID denotes the unique identifier of agent A. The counter A.p stores the number of inactive agents observed by A; it takes non-negative integer values and is initially set to 1
A discussion on the technical difficulty with weaker communication is discussed in the conclusion (refer to Section 4).
23
0. The boolean variable A.EXP indicates whether exploration has been achieved, where value 1 denotes success and 0 otherwise; initially, A.EXP = 0. The variable A.srcID stores the identifier currently considered as the source and is initially set to ⊥. The boolean variable A.phase indicates whether the source identifier has been fixed, where 0 denotes not fixed, and 1 denotes fixed; initially, A.phase = 0. For any two adjacent nodes v1 and v2 , π(v1 , v2 ) denotes the port label at node v1 leading to its neighbor v2 . Finally, for any set S, we denote by |S| the cardinality of S, that is, the number of elements in S. The execution of Ssync_EX PO proceeds in three phases in each round r. Let an active agent A be located at node v ∈ Gr . In round r, an active agent A executes these three phases. Phase 1 (1-hop view collection): For each port q 1 ∈ {0, 1, . . . , degr (v) − 1}, agent A performs the following steps. • Let u be the neighbor of v reachable via port q 1 . Let ID(v) and ID(u) denote the sets of identifiers of agents located at v and u, respectively. q
• If ID(u) ̸= ∅, then define Cv 1 = (ID(v), q 1 , ID(u)). q
• Otherwise, if ID(u) = ∅, define Cv 1 = (ID(v), q 1 , ∅)., where ∅ indicates that u is a hole. Let Cv = (Cv0 , Cv1 , . . . , Cvd ) denote the 1-hop view of agent A at node v, where d = degr (v) − 1. And, let Info(A) = (A.ID, A.p, A.EXP, A.srcID, A.phase). Agent A broadcasts Info(A), Cv . Phase 2 (Graph reconstruction): S Let v1 , v2 , . . . , vℓ be nodes with at least one active agent at round r, and note that v ∈ ℓi=1 {vi }. Since each active agent broadcasts its 1-hop view, the 1-hop view of a node vi may be broadcast by multiple agents in the same round. Let bi1 , bi2 , . . . , biℓi be the active agents present at node vi , for every i ∈ [1, ℓ]. Each agent bij at node vi broadcasts Info(bij ), Cvi . From Cvi , the set ID(vi ) can be extracted, and using ID(vi ) together with the identifiers of agents bij , the minimum active agent at node vi can be determined; without loss of generality, let bi1 be this agent. Let xi = |ID(vi )| − ℓi denote the number of inactive agents at node vi . If there exists a port q at node vi leading to a node w with at least one agent, then ID(w) can be obtained from Cvi ; if no agent from w broadcasts its 1-hop view, it follows that all agents at w are inactive. Let Sℓ w1 , w2 , . . . , wτ be such nodes which have only inactive agents, identifiable from i=1 {Cvi }. P P Define X = τj=1 |ID(wj )| + ℓi=1 xi , and Y = max{bij .p | j ∈ [1, ℓi ], i ∈ [1, ℓ]}. Here, X represents the number of inactive agents at round r which active agents can observe, and Y is the maximum p value among all active agents. Based on the gathered knowledge using global communication, it can define the above notations. It forms the map G′ = (V ′ , E ′ ) as follows. • The node set is defined as V ′ = {IDvi | i ∈ [1, ℓ]}, where IDvi is the ID of minimum active agent (i.e., bi1 .ID) at node vi . 24
• The edge set E ′ is constructed as follows. For every pair of tuples (ID(u1 ), q1 , ID(u2 )) and (ID(u2 ), q2 , ID(u1 )), agent A adds an undirected edge (IDu1 , IDu2 ) with port labels π(IDu1 , IDu2 ) = q1 and π(IDu2 , IDu1 ) = q2 . • For each tuple (ID(u1 ), q1 , ID(u2 )), if no view is received from any agent at u2 , agent A marks port q1 at node IDu1 as leading to a node containing only inactive agents. It stores set ID(u2 ) corresponding port q1 . • For each tuple (ID(u1 ), q1 , ∅), agent A marks port q1 at node IDu1 leads to a hole. Phase 3 (Move): In the second phase, agent A constructs a map G′ . If there is an agent bij at node vi such that bij .EXP = 1, it sets A.EXP = 1. Otherwise, it does the following. If G′ is disconnected, it considers the connected component G′′ of G′ in which node v (location of agent A at round r) is present. There are two cases based on bij .phase = 1, which are as follows. Case 1 (there is no agent bij with bij .phase = 1): It sets A.p = max{X , Y}. There are two sub-cases which are as follows. • Sub-case 1 (at least one node in G′ has A.p + 2 or more agents): If agent A is not the minimum active agent at node v, it stays idle; otherwise, based on G′ , it proceeds as follows. Let w1 , w2 , . . . , wλ1 be the nodes in G′ that have at least A.p + 2 agents. Let bj be the minimum ID active agent at node wj . Without loss of generality, let b1 .ID = min{bj .ID | j ∈ [1, λ1 ]}. Consider the active connected component (say H) of G′ where node w1 is present. If H ̸= G′′ , agent A stays idle at round r. Otherwise, it does the following. A port in G′′ that leads to a hole: Let w′1 , w′2 , . . . , w′λ2 be the nodes in G′′ that have ′ at least one port leading to a hole. Let bj be the minimum ID active agent at node ′ ′ w′j . Without loss of generality, let b1 .ID = min{bj .ID | j ∈ [1, λ2 ]}. Since agent A is aware of G′′ , it considers a shortest path P between w1 and w′1 . If there are multiple shortest paths between w1 and w′1 , it selects the lexicographically smallest among them. Let P = u1 (= w1 ) ∼ u2 ∼ . . . ∼ uλ (= w′1 ) be this lexicographically shortest path in G′′ . If v = uj for some 1 ≤ j < λ, agent A moves to node uj+1 . Otherwise, if agent A is at node uλ , it moves through the minimum available port that leads to a hole. In all other cases, agent A remains at node v. This is the pipeline approach. No port in G′′ that leads to a hole: If no port in G′ leads to a node which has only inactive agents, it updates A.EXP = 1. Otherwise, it does the following. Let w′1 , w′2 , . . . , w′λ2 be the nodes in G′′ that have at least one port leading to a node ′ where all agents are inactive. Let bj be the minimum ID active agent at node w′j . ′ ′ Without loss of generality, let b1 .ID = min{bj .ID | j ∈ [1, λ2 ]}. Since agent A is aware of G′′ , it considers a shortest path P between w1 and w′1 . If there are multiple shortest paths between w1 and w′1 , it selects the lexicographically smallest among 25
them. Let P = u1 (= w1 ) ∼ u2 ∼ . . . ∼ uλ (= w′1 ) be this lexicographically shortest path in G′′ . If v = uj for some 1 ≤ j < λ, agent A moves to node uj+1 . Otherwise, if agent A is at node uλ , it moves through the minimum available port that leads to a node which has only inactive agent(s). In all other cases, agent A remains at node v. • Sub-case 2 (no node in G′ has A.p + 2 or more agents): In the analysis, we show that at most one hole remains (refer to observation 3.3). If only one hole exists, then τ , the number of nodes containing only inactive agents that are visible to at least one active agent, is at most 1 (refer to Lemma 3.5). Agent A updates A.phase = 1. Further, if agent A finds that τ ̸= 1, it updates A.EXP = 1. Otherwise, let x = min min{|ID(vi )| : i ∈ [1, ℓ]}, |ID(w1 )| , where x denotes the minimum number of agents present at any node in G′ , including nodes that contain only inactive agents (i.e., w1 ). Agent A selects a node u containing x agents; if multiple choices exist among the nodes vi and w1 , it selects the node containing the minimum ID agent and stores this identifier in A.srcID. In this round, agent A remains at its current position in this round. Case 2 (there is an agent bij with bij .phase = 1): It sets A.phase = 1, A.srcID = bij .srcID, and A.p = max{X , Y}. There are two sub-cases. • Sub-case 1 (a port in G′ leads to a hole): Without loss of generality, one of the port of v2 leads to a hole. If A is at node v2 , it set A.EXP = 1, and moves to the hole. Otherwise, it sets A.EXP = 1, and stays at its position. • Sub-case 2 (no port in G′ leads to a hole): If there is no port in G′ that leads to a node containing only inactive agents, agent A updates A.EXP = 1. Otherwise, the behavior of A depends on the value of A.srcID. If A.srcID ∈ / ID(vi ) for every i ∈ [1, ℓ] and A.srcID ∈ / ID(w1 ), then A sets A.EXP = 1. If A.srcID ∈ ID(w1 ), then A stays at its current position. Otherwise, without loss of generality, assume that A.srcID ∈ ID(v1 ). If |ID(v1 )| = 1 and there exists a port in G′ leading to a node containing only inactive agents, then A sets A.EXP = 1. If this is not the case, then there exists at least one agent at node v1 other than A.srcID. If no such agent is active, then A stays at its position. Otherwise, there exists at least one active agent other than A.srcID, and A considers a shortest path P between v1 and w1 . If multiple shortest paths exist, A selects the lexicographically smallest one. Let P = u1 (= v1 ) ∼ u2 ∼ · · · ∼ uλ (= w1 ) denote this path in G′ . If A.ID = A.srcID, then A stays at its position; otherwise, if A is at node uj with j < λ, it moves to node uj+1 . 3.1. Correctness and analysis of algorithm In this section, we prove that Ssync_EX PO solves exploration under the Ssync scheduler with move complexity O(k D̂) and memory requirement O(max{log n, log p}) per agent. Furthermore, every agent eventually becomes aware that exploration has been completed. We have the following observation as per our algorithm. 26
Observation 3.1. In the algorithm, the value of A.p for any agent A increases only if A receives information from an agent B with B.p > A.p, or if A observes more than A.p inactive agents in the current round. Since the adversary can deactivate at most p agents in any round, it follows that A.p ≤ p for every agent A. Lemma 3.1. Let Ar denote k−1 the set of agents active in round r, and let the adversary deactivate at most p = n−2 − 1 agents per round. Suppose that at round r1 , all agents in Ar1 agree on some information I of size O(log n). Then, there exists at least one agent that is active in both rounds r1 and r1 + 1, that is, Ar ∩ Ar+1 ̸= ∅. k−1 − 1 agents per round, where k is Proof. The adversary can deactivate at most p = n−2 the total number of agents and n is the number of nodes of G. As shown in Section 2, this implies k ≥ (n − 2)(p + 1) + 1. Consider a round r1 in which at most p agents are inactive; hence, the number of active agents is |Ar1 | = k−p. Assume that all agents active in round r1 agree on some information I of size O(log n). In round r1 +1, the adversary may deactivate at most p agents from Ar1 , so at least k −2p agents retain the information I at round r1 +1. Using the lower bound on k, we have k − 2p ≥ (n − 2)(p + 1) + 1 − 2p = np + n − 4p − 1. Since n ≥ 4 (considered in the begging of Section 3), this value is positive, which implies that Ar1 ∩ Ar1 +1 ̸= ∅. Therefore, at least one agent is active in both rounds r1 and r1 + 1. This completes the proof. Based on Lemma 3.1, we have the following observation. Observation 3.2. Let a non-empty set of agents set its EXP (resp. phase) parameter to 1 at round r1 . Then, for every round r ≥ r1 + 1, ∃ at least one agent B with B.EXP = 1 (resp. B.phase = 1) at round r. Also, for every agent A and every round r ≥ 0, the value of A.p is non-decreasing over time. Lemma 3.2. If there are at least two holes in round r, then there exists a node that contains at least p + 2 agents in round r. Proof. Let h denote the number of holes in round r. Since h ≥ 2, agents can occupy at most n − 2 nodes. The adversary can deactivate at most p agents per round, where k is the total number of agents and n is the number of nodes of G. Suppose, for contradiction, that no node contains p + 2 agents. Then each occupied node contains at most p + 1 agents. As agents occupy at most n − 2 nodes, the total number of agents is at most (n − 2)(p + 1) which contradicts the fact that k agents can solve the exploration only if k ≥ (n − 2)(p + 1) + 1 (recall from Section 2). Therefore, there exists at least one node that contains at least p + 2 agents in round r. This completes the proof. Based on lemma 3.2, we have the following observation. Observation 3.3. Let A be an active agent in round r, and suppose that there are at least two holes in Gr . Since A.p ≤ p by Observation 3.1, Lemma 3.2 implies that there exists a node v in Gr containing at least A.p + 2 agents. Consequently, if in round r agents observe that no node contains at least A.p + 2 agents, they can correctly conclude that there is at most one hole in Gr . 27
We prove that, in round r, every active agent possesses complete information about CCA(Gr ). Lemma 3.3. Let A be an active agent at node v of CCA(Gr ). Then, at the end of Phase 2, agent A constructs a labeled graph isomorphic to CCA(Gr ). Moreover, for every node in this reconstructed graph, the agent correctly identifies (i) which incident ports lead to holes and (ii) which incident ports lead to nodes occupied exclusively by inactive agents, along with the IDs of such inactive agents. Proof. Let (w1 , w2 ) be an edge in CCA(Gr ), and let π(w1 , w2 ) = q1 and π(w2 , w1 ) = q2 . Since (w1 , w2 ) belongs to CCA(Gr ), both w1 and w2 contain at least one active agent due to Def. 1. Let IDw1 and IDw2 denote the minimum identifiers among the active agents located at w1 and w2 , respectively. Then agent A receives the 1-hop views Cw1 and Cw2 , and hence IDw1 , IDw2 ∈ V ′ as per Phase 2. Because π(w1 , w2 ) = q1 and π(w2 , w1 ) = q2 , we have that Cwq11 ∈ Cw1 and Cwq22 ∈ Cw2 . In Phase 2, these tuples are Cwq11 = (ID(w1 ), q1 , ID(w2 )) and Cwq22 = (ID(w2 ), q2 , ID(w1 )). Therefore, agent A adds an undirected edge (IDw1 , IDw2 ) to E ′ with port labels π(IDw1 , IDw2 ) = q1 and π(IDw2 , IDw1 ) = q2 . Hence, every edge of CCA(Gr ) is correctly reconstructed. Now consider a node w1 ∈ CCA(Gr ) such that one of its ports, say q1 , leads to a node w2 containing only inactive agents. Since w1 ∈ CCA(Gr ), it contains at least one active agent, and thus agent A receives Cw1 . Since no agent is active at w2 , no view Cw2 is received. As port q1 of w1 leads to w2 , we have Cwq11 = (ID(w1 ), q1 , ID(w2 )). By the rules of Phase 2, IDw1 ∈ V ′ , where IDw1 is the minimum active identifier at node w1 , and agent A correctly records that port q1 of node IDw1 leads to a node with only inactive agents and it marks port q1 with set ID(w2 ). Next, consider a node w1 ∈ CCA(Gr ) such that one of its ports, say q1 , leads to a hole w2 . Since w1 ∈ CCA(Gr ), it contains at least one active agent, and hence Cw1 is received. As no agent is present at w2 , no view from w2 is received. Since port q1 of w1 leads to w2 , we have Cwq11 = (ID(w1 ), q1 , ∅). By the rules of Phase 2, IDw1 ∈ V ′ , and agent A correctly records that port q1 of node IDw1 leads to a hole. This completes the proof. Lemma 3.4. If in round r there exists a node in Gr that contains at least A.p + 2 agents, then at the end of round r either a hole is filled or a node containing only inactive agents receives at least one active agent, unless Gr contains no hole and no node consisting only of inactive agents, or there already exists an active agent B with B.EXP = 1 (or B.phase = 1) in round r. Proof. As per Ssync_EX PO, the value of A.p = max{X , Y}, where X represents the number of inactive agents at round r which active agents can observe, and Y is the maximum p value among all active agents at round r. Due to Observation 3.1, the value of A.p is the same as B.p for any two active agents A and B at round r. Due to Lemma 3.3, all active agents form a map of CCA(Gr ) (i.e., G′ ) including information which port(s) lead to a hole or port(s) lead to a node which has only inactive agents. As per Ssync_EX PO, agents do the following. Let w1 , w2 , . . . , wλ1 be the nodes in G′ that have at least A.p + 2 28
agents. Let bj be the minimum ID active agent at node wj . Without loss of generality, let b1 .ID = min{bj .ID | j ∈ [1, λ1 ]}. Consider the active connected component (say H) of G′ where node w1 is present. If there is a port in H that leads to a hole, then all active agents agree on the path P in H that leads to the hole. Let P = u1 (= w1 ) ∼ u2 ∼ . . . ∼ uλ be a path such that one of the ports of node uλ leads to a hole. Since path P is part of H ⊆ CCA(Gr ), at least one active agent is present at each node uj for every j ∈ [1, λ]. As per the algorithmic steps, the minimum active agent at node uj for every j < λ moves to node uj+1 . And the minimum active agent at the node uλ moves the minimum available port, which leads to a hole. Else, if no port in H leads to a hole, and Gr contains either a hole or a node consisting only of inactive agents, Definition 1 implies that there exists a port in H leading to a node containing only inactive agents. If there is a port in H that leads to a node with only inactive agents, then all active agents agree on the path P in H that leads to that node as per Ssync_EX PO. Let P = u1 (= w1 ) ∼ u2 ∼ . . . ∼ uλ be a path such that one of the ports of node uλ leads to a node which has only inactive agents. Since path P is part of H ⊆ CCA(Gr ), at least one active agent is present at each node uj for every j ∈ [1, λ]. As per the algorithmic steps, the minimum active agent at node uj for every j < λ moves to node uj+1 . And the minimum active agent at the node uλ moves via the minimum available port, which leads to a node that has only inactive agents present. Therefore, at the end of round r, one of the nodes which has only inactive agents gets one agent from one of the nodes of G′ . This completes the proof. We now present a key lemma on which the correctness of the algorithm relies. Lemma 3.5. Let at round r an active agent A observe that no node in Gr contains at least A.p + 2 agents. If Gr contains a hole, then there is at most one node in Gr containing only inactive agents. Proof. Let β denote the number of nodes in Gr that contain only inactive agents, and let w1 , w2 , . . . , wβ be these nodes. Since the adversary can deactivate at most p agents in any P round, the total number of inactive agents satisfies βj=1 ID(wj ) ≤ p. As β nodes contain only inactive agents and there is exactly one hole in Gr , the number of nodes that contain at least one active agent is n − β − 1. Since no node contains more than A.p + 1 agents at round r, the total number of agents is at most (A.p + 1)(n − β − 1) + p. Therefore, the following inequality must hold: (A.p + 1)(n − β − 1) + p ≥ (n − 2)(p + 1) + 1.
(96)
Case 1 A.p = p: From Eq. 96, we obtain (p + 1)(n − β − 1) + p ≥ (n − 2)(p + 1) + 1 =⇒ 2p β ≤ p+1 ≤ 2. Thus, β ≤ 2. We now show that β = 2 is impossible. Substituting A.p = p and β = 2 into Eq. 96 gives (p + 1)(n − 3) + p ≥ (n − 2)(p + 1) + 1 =⇒ 2 ≤ 0 which is a contradiction. Hence, β ≤ 1. 29
Case 2 A.p < p: From Eq. 96, we have (A.p + 1)(n − β − 1) + p ≥ (n − 2)(p + 1) + 1 =⇒ A.p(n − β − 1) − β ≥ np − 3p. Since A.p < p, it follows that p(n − β − 1) − β > np − 3p =⇒ 2p β < p+1 =⇒ β < 2. Therefore, β ≤ 1 holds in this case as well. This completes the proof. We now state the final result. Theorem 3.1. Ssync_EX PO solves exploration under the Ssync scheduler. The move complexity of the algorithm is O(k D̂), and each agent requires O(max{log n, log p}) memory. Furthermore, every agent eventually becomes aware that exploration has been achieved. Proof. Due to Lemma 3.4, if in round r there exists a node in Gr with at least A.p+2 agents, then by the end of round r either a hole is filled or a node containing only inactive agents receives an active agent, unless Gr contains no hole and no node consisting only of inactive agents, or there already exists an active agent B with B.EXP = 1 (or B.phase = 1) in round r. Therefore, in each such round, the number of agents at one of the nodes containing at least A.p + 2 agents decrease by at least one. Hence, there exists a round within the first k rounds in which agents observe that every node of G′ contains at most A.p+1 agents, where A is an active agent in that round. Let r1 denote the first such round. As per Observation 3.3, there is at most one hole at round r1 . There are two possible cases: Case 1: If there exists a round r ≤ r1 in which an active agent observes that no port of G′ leads to a hole and no port leads to a node containing only inactive agents, this implies that every node of G has at least one active agent at round r. As per Ssync_EX PO, all active agents can conclude correctly at round r that exploration has been completed and set their EXP parameter to 1 as per. By Observation 3.2, at least one agent is active in both rounds r and r + 1. Without loss of generality, let A be an agent that is active in both rounds r and r + 1. Therefore, at the beginning of round r + 1, there is an agent with its EXP parameter equal to 1. Any agent activated in round r + 1 that was inactive in round r learns this information via global communication and updates its own EXP parameter to 1. By the fairness of the Ssync scheduler, every agent is eventually activated and hence eventually sets its EXP parameter to 1. This step also guarantees that each agent is aware that exploration has been achieved within finite but unbounded time. Case 2: As per Ssync_EX PO, each active agent A at round r1 updates A.srcID to the minimum ID of a node that contains the smallest number of agents. This node can also be a node that contains only inactive agents. By Lemma 3.1, there exists an active agent B in every round r2 ≥ r1 such that B.srcID ̸= ⊥ and B.phase = 1. Any agent A1 with A1 .srcID = ⊥ and A1 .phase = 0 updates A1 .srcID = B.srcID and A1 .phase = 1. Therefore, this source is fixed in every round r2 ≥ r1 , and agents execute the algorithm of Case 2 of Phase 3 of Ssync_EX PO in every r2 ≥ r1 . Now, we consider the following sub-cases in which exploration can be correctly concluded. 1. Sub-case 1: At some round r2 ≥ r1 , if active agents find that there are two distinct nodes containing only inactive agents (i.e., τ ≥ 2), then every active agent A 30
sets A.EXP = 1 as per Ssync_EX PO. This correctly implies that exploration is completed at round r2 for the following reason. Since active agents observe two distinct nodes containing only inactive agents (i.e., τ ≥ 2), no hole is present. Indeed, if a hole were present, then τ ≤ 1 by Lemma 3.5. Therefore, every active agent A correctly concludes that exploration is achieved at round r2 . As in Case 1, within finite but unbounded time, each agent updates its EXP parameter to 1. 2. Sub-case 2: At some round r2 ≥ r1 , if an active agent A does not find the node corresponding to A.srcID in its 1-hop neighborhood and does not receive this information from the 1-hop views of other active agents, but there exists a port of G′ that leads to a node containing only inactive agents, then every active agent A sets A.EXP = 1 as per Ssync_EX PO. This correctly implies that exploration is completed at round r2 for the following reason. If a hole were present, then each active agent would receive information about A.srcID in round r2 as τ ≤ 1 due to Lemma 3.5. Since this does not happen, no hole is present, and hence every active agent correctly concludes that exploration is achieved. As in Case 1, within finite but unbounded time, each agent updates its EXP parameter to 1. 3. Sub-case 3: At some round r2 ≥ r1 , if one of the ports of G′ leads to a hole, as per Ssync_EX PO, one active agent moves from a node of G′ to the hole, and every active agent A sets A.EXP = 1 as per Ssync_EX PO. This correctly implies that exploration is completed at round r2 for the following reason. Since at round r1 , each active agent observes at most A.p + 1 agents, there is at most one hole due to Observation 3.3. As per Ssync_EX PO, in subsequent rounds r′ ≥ r1 + 1, movement occurs only when a node containing only inactive agents is observed by active agents, and node v with A.srcID has at least one active agent other than A.srcID. Therefore, no new hole is created. If round r2 is the first round where one of the ports of G′ leads to a hole, the hole is visited by at least one agent in round r2 . Therefore, every active agent correctly concludes that exploration is achieved. As in Case 1, within finite but unbounded time, each agent updates its EXP parameter to 1. 4. Sub-case 4: Let v be the node where A.srcID is present. Consider any round r2 ≥ r1 such that node v contains only the agent with A.srcID, this agent is active, and there exists at least one node containing only inactive agents. In this situation, every active agent A sets A.EXP = 1 according to Ssync_EX PO, and exploration is correctly concluded due to the following reasons. At round r1 , active agents observe that at most A.p + 1 agents are present at any node in G′ . Hence, no node in Gr1 contains at least p + 2 agents as A.p ≤ p. As per Ssync_EX PO, in every round r′ ≥ r1 + 1, movement occurs only when a node containing only inactive agents is observed by active agents, and node v with A.srcID has at least one active agent other than A.srcID, irrespective of A.srcID is active or inactive. Therefore, every node in Gr′ contains at most p + 1 agents at 31
the end of round r′ . If a hole exists at round r2 , no node contains at least p + 2 agents, and one node v has exactly one active agent (A.srcID), then at round r2 , agents are in C ∗ configuration. At round r2 , active agents observe that there exists a node containing only inactive agents other than node v (recall node v has exactly one agent, and it is active). From this, they infer that the system is not in configuration C ∗ and that no hole exists at round r2 . Consequently, every active agent at round r2 correctly concludes that exploration has been achieved. As in Case 1, within finite but unbounded time, every agent updates its EXP parameter to 1. Let v be the node where A.srcID is located at round r1 . Since at round r1 the active agent A selects A.srcID based on a node that contains the minimum number of agents or a node containing only inactive agents, the number of agents at node v is at most p. As per Ssync_EX PO, whenever an agent at node v is active other than A.srcID, all active agents compute a shortest path P between v and w1 (where w1 denotes a node containing only inactive agents). Using a pipeline strategy along P , node w1 receives one agent. If Sub-cases 1, 2, and 3 do not occur within at most p such a pipeline from node v, then Sub-case 4 must occur. Therefore, from round r1 onward, there exists a round r2 within finite but unbounded time in which one of the four sub-cases applies. The number of moves after which at least one active agent A sets A.EXP = 1 is at most O(k D̂). This bound follows from the following reasons. At most k pipelines are required for the agents to reach a configuration in which active agents k−1 observe that each − 1 ≤ k additional node contains at most A.p + 1 agents, and thereafter at most p = n−2 pipeline can occur from the node v where A.srcID is present. As node v cannot contain at most p agents. Each pipeline length cannot be more than D̂. Therefore, the move complexity is O(k D̂). Each agent A maintains the variables A.ID, A.p, A.EXP, A.srcID, and A.phase. By definition, the parameters A.EXP and A.phase require O(1) memory. The parameters A.ID and A.srcID store agent identifiers and therefore require O(log n) bits as per our model. ByObservation 3.1, we have A.p ≤ p, and hence storing A.p requires O(log p) bits. k−1 − 1 ≤ k, this requires O(log nk ) bits. Therefore, the total memory required Since p = n−2 by each agent is O(max(log n, log p)). This completes the proof. 4. Conclusion We studied exploration in 1-interval connected graphs under the Ssync scheduler with the dynamic port labeling. We established a bound on the adversary’s deactivation power and presented an exploration algorithm that matches this bound. We have identified the minimal visibility and communication assumptions required for solvability; however, our algorithm relies on global communication. Though we could not formally prove global communication as a necessary condition, the following challenges appear if one considers even (D̂ − 1)-hop communication and 1-hop visibility. An adversary can exploit dynamic port labeling and selective activation to maintain indistinguishable local views across agents, 32
thereby disrupting coordination. Hence, the pipeline strategy does not work properly and may create new hole(s). This highlights the technical challenge of maintaining coordinated progress under the dynamic port labeling and partial activation. In [6, 13, 12], the global communication is assumed to establish feasibility under the Fsync scheduler. This leads to two questions: whether global communication is necessary for solvability, and for which values of k exploration can be achieved without additional assumptions. References [1] C. E. Shannon, Presentation of a maze-solving machine, Claude Elwood Shannon Collected Papers (1993) 681–687. [2] S. Das, Graph exploration with mobile agents, in: Chapter 16 of Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, 2019, pp. 403–422. [3] F. Kuhn, N. Lynch, R. Oshman, Distributed computation in dynamic networks, in: STOC’2010, Association for Computing Machinery, New York, NY, USA, p. 513–522. [4] A. Casteigts, P. Flocchini, W. Quattrociocchi, N. Santoro, Time-varying graphs and dynamic networks, International Journal of Parallel, Emergent and Distributed Systems 27 (5) (2012) 387–408. [5] O. Michail, I. Chatzigiannakis, P. G. Spirakis, Causality, influence, and computation in possibly disconnected synchronous dynamic networks, Journal of Parallel and Distributed Computing 74 (1) (2014) 2016–2026. [6] A. Saxena, K. Mondal, Path connected dynamic graphs with a study of dispersion and exploration, Theoretical Computer Science 1050 (2025) 115390. [7] T. Gotoh, Y. Sudo, F. Ooshita, H. Kakugawa, T. Masuzawa, Group exploration of dynamic tori, in: ICDCS 2018, IEEE, 2018, pp. 775–785. [8] T. Gotoh, Y. Sudo, F. Ooshita, T. Masuzawa, Exploration of dynamic ring networks by a single agent with the h-hops and s-time steps view, in: SSS 2019, Springer, pp. 165–177. [9] T. Gotoh, P. Flocchini, T. Masuzawa, N. Santoro, Exploration of dynamic networks: Tight bounds on the number of agents, Journal of Computer and System Sciences 122 (2021) 1–18. [10] G. Di Luna, S. Dobrev, P. Flocchini, N. Santoro, Distributed exploration of dynamic rings, Distributed Computing 33 (2020) 41–67. [11] M. Bournat, S. Dubois, F. Petit, Computability of perpetual exploration in highly dynamic rings, in: ICDCS 2017, IEEE, 2017, pp. 794–804.
33
[12] A. D. Kshemkalyani, A. R. Molla, G. Sharma, Efficient dispersion of mobile robots on dynamic graphs, in: ICDCS 2020, 2020, pp. 732–742. [13] A. Saxena, K. Mondal, Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs, in: DISC 2025, Vol. 356, 2025, pp. 41:1–41:23. [14] S. Das, N. Giachoudis, F. L. Luccio, E. Markou, On the broadcast problem for mobile agents in dynamic networks, Discrete Applied Mathematics 379 (2026). [15] P. Flocchini, M. Kellett, P. C. Mason, N. Santoro, Searching for black holes in subways, Theory of Computing Systems 50 (2012) 158–184. [16] P. Flocchini, B. Mans, N. Santoro, On the exploration of time-varying networks, Theoretical Computer Science 469 (2013) 53–68. [17] D. Ilcinkas, A. M. Wade, On the power of waiting when exploring public transportation systems, in: OPODIS 2011, Springer, 2011, pp. 451–464. [18] D. Ilcinkas, A. M. Wade, Exploration of the t-interval-connected dynamic graphs: the case of the ring, Theory of Computing Systems 62 (2018) 1144–1160. [19] M. Bournat, A. K. Datta, S. Dubois, Self-stabilizing robots in highly dynamic environments, in: SSS 2016, Springer, 2016, pp. 54–69.
34