Black Hole Search by a Set of Scattered Agents in Dynamic Rings
Giuseppe Antonio Di Luna Paola Flocchini Giuseppe Prencipe Nicola Santoro



Face embeddings of Archimedean Solids
    David Weed
    April 29, 2024
=====================================




In this paper we investigate the problem of searching for a black hole in a dynamic graph by a set of scattered agents (i.e., the agents start from arbitrary locations of the graph).
The black hole is a node that silently destroys any agent visiting it. This kind of malicious node nicely models network failures such as 
a crashed host or a virus that erases the visiting agents. The black hole search problem is solved when at least one agent survives, and it has the entire map of the graph with the location of the black hole. 
We consider the case in which the underlining graph is a dynamic 1-interval connected ring: a ring graph in which at each round at most one edge can be missing. We first show that the problem cannot be solved if the agents can only communicate by using a face-to-face mechanism: this holds for any set of agents of constant size, with respect to the size n of the ring.

To circumvent this impossibility we consider agents equipped with movable pebbles that can be left on nodes as a form of communication with other agents. 
When pebbles are available, three agents can localize the black hole  in O(n^2) moves. We show that such a number of agents is optimal. 
 We also show
that the complexity is tight, that is   Ω(n^2) moves are required for any algorithm solving the problem with three agents, even with stronger communication mechanisms (e.g., a whiteboard on each node on which agents can write messages of unlimited size). 
To the best of our knowledge this is the first paper examining the problem of searching a black hole in a dynamic environment with scattered agents. 





 




§ INTRODUCTION








 §.§ Exploration of Dynamic Networks



In the distributed computing community a large set of works (see <cit.>) studies the computational paradigm of mobile agents. 
A mobile agent is a software component that is able to move on a network visiting nodes. When a node is visited, the agent executes some computation interacting with the local environment, the memory and resources of the visited computational node, and then it moves on a next computational node by transmitting itself on the network. That is the agent can be seen as an intelligent message with computational capabilities and that is able to decide its next destination. 

In the mobile agent paradigm a plethora of problems have been studied. The most famous are: exploration, the agents have to collectively visit the entire network; gathering, the agents have to reach the same node; patrolling, the agents have to periodically patrol the network minimising the time between two visits of the same node. 

One problem that has been thoroughly  investigated is the Black Hole Search () <cit.>. In this problem there exists a dangerous stationary node, called  black
hole (), that silently erases from the network all the agents that visit it. 
A node could model several kind of common failures: for instance, consider a crashed host, and any agent trying to visit it will be lost and removed from the network; or a node infected by a virus that cancels the incoming agents. 
The many works that investigated have given to us a complete knowledge of the computational properties of the problem under several assumptions (examples are communication mechanisms employed by the agents, level of synchronicity, topology of the network, and agents' knowledge and capabilities). However, almost all of them examine the case in which the network is static: the set of computational nodes and the links connecting them are static and never change. 


Recently, research within  distributed computing  has  started to focus on 
mobile-agents in  highly dynamic graphs, 
 i.e., graphs where the topological changes 
  are not limited to  sporadic and disruptive events (such as process failures, links congestion, etc).
Highly dynamic graphs model a wide range of 
 modern networked systems whose dynamic nature  is the natural product of  innovations 
 in communication technology (e.g., wireless networks), in software layer (e.g., a controller in a software defined network), and in society (e.g., the pervasive nature of smart mobile devices)  (e.g., see <cit.>). 

We consider evolving graphs, that are dynamic graphs that can be seen as an infinite sequence of static graphs. 
In this case the model of computation is by definition synchronous, and at each round corresponds a static graph of the aforementioned sequence. 
A popular assumption in this model is the 1-interval connectivity: this assumption dictates that at each round the dynamic graph is connected  (e.g., <cit.>).

We focus on the case of 1-interval connected rings, where the topology is a ring graph in which at each round at most one edge is missing. 

In the last years the body of works studying agents on highly dynamic graphs has been growing with a sustained velocity (for a recent survey see <cit.>). 
In particular, a large number of papers is focussing on 1-interval connected  rings:  the  gathering problem has been investigated in <cit.>, the exploration problem  in   <cit.> and the for colocated[Agents are colocated when they all start from the same node.] agents in the recent <cit.>. 
Despite this large interest, a lot of questions are open. One of them is answered in this paper: how does the computational landscape of finding a change when agents are scattered? In the scattered case agents start from arbitrary nodes of the graph. We will show that this setting has many differences with respect to the case of colocated agents (studied in <cit.>) in terms of both solvability (solving in some settings becomes impossible) and complexity.  





 §.§ Related Works




The Black Hole Search () problem  
has ben introduced in <cit.>. The problem has been studied
in graph of restricted topologies (e.g., trees <cit.>, rings and tori <cit.>)
and  in  arbitrary and possibly unknown topology (e.g., <cit.>). 
For a recent survey see  <cit.>.
 The most relevant papers are the ones investigating   in static ring networks. 
In the asynchronous setting, it is possible to solve
    the problem with two  colocated agents and   Θ(n log n)   moves,
   in the whiteboard model  <cit.>, 
and in the   pebble model <cit.>. 
It has been shown that  O(n log n) moves also suffices for the scattered case and oriented rings <cit.>. 
Others <cit.> investigated time-optimal algorithms when considering unitary delay. 





 
 In spite of all the differences in settings and assumptions, 
all these investigations share a common trait: 
the agents operate on a static network.

The only works studying in dynamic graph are <cit.> and <cit.>.
   <cit.> is on the black hole search in carrier graphs, a particular class of periodic temporal graphs 
defined by circular intersecting routes  of public carriers, where the stops are the nodes of the graph and  
the agents can board and disembark from a carrier at any stop.

 <cit.> studies the in the same setting studied in this paper: 1-interval connected ring with a single . <cit.> shows that three agents are necessary to find the (in the static case two agents are enough to explore arbitrary known graphs <cit.>), and it presents optimal algorithms to find the with three agents. Moreover, if agents can communicate only when they are on the same node, the authors show that can be solved in  Θ(n^2) moves and rounds. Finally, if agents can use pebbles, they show an improved algorithm that finds the in  Θ(n^1.5) moves and rounds.
  
 In both studies, the agents are assumed to be  initially colocated, i.e.  
 to start from the same safe node.
To the best of our knowledge, no study considers the case of scattered agents.







 §.§ Contributions



We study  the problem of
finding a in an oriented dynamic ring by a set of scattered agents with visible identities under different communication capabilities. 
We study two main families of communication mechanisms. The endogenous family, where the agents can communicate without using any external facilities. In this case, they can either see each other only when on the same node (Vision model), or they can also talk with each other (Face2Face model). 
In contrast, in the exogenous family, the agents communicate using external tools. In this case, we have the Pebbles model, in which each agent carries a pebble that can leave on a node to mark it for other agents, or that it can remove from a node in case this marking is not needed anymore; or the Whiteboard model, in which each node has a public whiteboard on which agents can write messages of unlimited size.  

Our first result (Obs. <ref>) is that in the endogenous family the is unsolvable using three agents. This is in contrast with the colocated case where is solvable in the same setting by using three agents (see <cit.>). 

To circumvent such impossibility we then rely on exogenous  communication. We focus on algorithms that use an optimal number of agents.
In particular, in <cit.>, it has been shown that in dynamic rings is unsolvable if only two agents are available. This results clearly extends also to the scattered case.  
Therefore, we will consider algorithms for set of three agents (size optimal algorithms). 
In Th. <ref>, we show that any optimal size algorithm solving requires Ω(n^2) moves and Ω(n^2) rounds in the whiteboard model. 
We note that on a static and synchronous rings  two agents can find the blackhole in O(n) moves and rounds. This observation is interesting as it shows that  dynamicity does not only increase the number of required agents but it also increases, significatively, the time and moves required. This also highlights the price to pay for having scattered agents: in fact, for dynamic rings, O(n^1.5) moves and rounds are sufficient in the colocated case <cit.>. 
Finally, our lower bound is tight: we provide an algorithm that solves in the pebble model in O(n^2) rounds and moves using three agents (Th. <ref>). 
































































§ MODEL AND PRELIMINARIES


 



 §.§ The Model and the Problem



The system is a temporal graph where a set of nodes V is connected by a set of edges E. The system is synchronous, and the dynamic networks is an evolving graph G. The time is divided in fictional unites called rounds. 
 The evolving graph can be seen as 
 a sequence of static graphs: = G_0,G_1, …,G_r, …, where G_r =(V_r,E_r) is the graph of the edges present at round r.  The footprint of the dynamic graph is a static graph containing all the edges that will  be present in the system, alternatively, is the union of all the graphs in the aforementioned sequence. 
An evolving graph  where connectivity is  guaranteed at every round  is called   1-interval connected
(i.e., ∀ G_i ∈, G_i is connected).  
 In this paper we focus on dynamic rings: 1-interval connected graphs whose footprint is a ring.
Let   R = (v_0, v_1, … v_n-1)  be a  dynamic oriented ring, i.e., where each node v_i has two ports, consistently labelled left and right connecting it to v_i-1 and v_i+1 (operations on 
indices are modulo n). Nodes are anonymous, that is they do not have IDs.  
A set    A = { a_0, a_1, …, a_k-1}    of   mobile    agents    inhabits  R.  The agents start from distinct arbitrary locations: they are   scattered. 
Agents have distinct visible identifiers in {0,…,k-1} and they know the total size of the ring n.  The agents  can move from node to neighbouring node and they have bounded storage (O(log n) bits of internal memory suffice for our algorithms).  In each round all agents are activated. Upon activation, an agent on node v at round r
   takes  a local snapshot of v that  contains  the set E_r(v) of edges incident on v at this round,  and  the set of agents present in v. The agent communicates   with the others   (the communication mechanism employed will be discussed later).
 On the basis of   the snapshot, the communication,  and the content of its local memory,
  an agent  then decides what action to take.  The action consists of a communication step (defined below) and a move step. In the move step the agent may decide to stay still or to move on an edge    e=(v,v') ∈ E_r(v). In the latter case, if the edge is present, the agent will reach v' in round r +1.  
 
 We consider two classes of communication mechanisms (endogenous and exogenous) which give rise to four models.

 
Endogenous Mechanisms
 rely only on the robots' capabilities without requiring  any external object. In the FaceToFace (F2F) model the agent can explicitly communicate among themselves  only when they reside on the same node.  In the Vision model an agents can see all the other agents that reside on the same node (hence count their number); however, they cannot communicate. 
 
Exogenous Mechanisms
do   require  external objects for the robots to exchange information. Among those we distinguish:

- Pebble: each agent is endowed with a single pebble that can be placed on or taken from a node.  On each node,  the concurrent actions of placing or taking  pebbles are done in  fair mutual exclusion.

-Whiteboard:   each node contains a local shared memory, called
whiteboard, of size O(log n) where agents can write on  and read from.  Access to the whiteboard is done in adversarial but fair mutual exclusion.











  
The temporal graph  contains a black hole (), a node 
that destroys any visiting agent without leaving any detectable trace of that
destruction. 






We say that an agent knows the footprint of R when it knows its left and right distance from the blackhole, that is the agent is able to build in its memory a graph isomorphic to the footprint of R and it knows its relative position with respect to the blackhole. 

() <cit.>
Given a dynamic ring R, and an algorithm A for a set of agents we say that A solves the if at least one agent survives and terminates knowing the footprint  of R. Each agent that terminates has to know the footprint  of R. 


Since n is known it is enough that the agent knows its right (or left) distance from the blackhole in order to know the footprint, this means that is not necessary for the agent to visit all nodes of R.

We call size the number of agents used by the protocol. 
Other measures of complexity are the total number of moves performed by the agents, which we shall call cost, and time it takes to complete the task. 
 
Figure <ref> shows (a) four rounds of an execution in a dangerous dynamic ring,
 and (b) the space diagram representation that we will use in this paper.  
 The agent is represented as the black quadrilateral and it is moving clockwise; the   is the black node. At round r=2 and r=3 the agent is blocked by  the missing edge. In the diagram,   the movement of the agent is represented as a solid line. 
 
 
 




 


§ PRELIMINARIES

Before presenting and analyzing our solution protocols, we report some known impossibility results and a technical lemma that we will use in our paper. 
Then we briefly describe a well known 
idea employed for  in static graphs that will be adapted in our algorithms, as well as
the conventions and symbols used in our protocols. 



 §.§ Known Impossibilities


In this section we report known impossibility results. 

<cit.>
In a dynamic ring    of size n>3,
two colocated agents  cannot solve the .


 The impossibility holds even  if    the agents have unique IDs, 
 and   are equipped with the strongest (Whiteboard) communication  model.



 <cit.>
There exists no algorithm that solves the  in a dynamic ring  R  whose size is unknown to the agents.
The result holds even if  the nodes have   whiteboards, the agents have IDs, and  irrespectively of the number of agents.



<cit.>
Given a dynamic ring R, and a cut U (with |U|>1) of its footprint connected by edges e_c and e_cc to nodes in V ∖ U, agents in U explore a node outside the cut at the end of round r
if and only if,   in round r,   there are two agents in U, one that tries to traverse e_c and one trying to traverse e_cc, respectively.


























 §.§ Cautious Walk


Cautious Walk is  a mechanism introduced in <cit.>  for agents to move on dangerous graphs in such a way that two (or more) agents never enter the black hole from the same edge. The general idea of cautious walk in static graphs is that when an agent a moves  from u to v through an unexplored (thus dangerous) edge (u,v), a  must leave  the information that the edge is under exploration at u. The information can be provided through some form of mark in case of exogenous communication mechanisms, or implicit   in case of endogenous  mechanisms  (e.g., by employing a second agent as a “witness”). 
In our algorithms we will make use of variants of the general idea of cautious walk, adapting it  to  the dynamic scenario.
  

 
 


 §.§ Pseudocode Convention and Communication

We use the pseudocode convention introduced in <cit.>. 
In particular, our algorithms use  as a building block  procedure (dir | p_1:s_1; p_2:s_2; …; p_k:s_k),
where dir ∈{, , }, p_i is a predicate, and s_i is a state. 
In Procedure , the agent takes a snapshot, then evaluates  predicates p_1, …, p_k in order;
as soon as a predicate is satisfied, say p_i, the procedure exits, and the agent transitions to the state s_i specified by p_i. 
If no predicate is satisfied, the agent tries to move in the specified direction dir (or it stays still if dir=), and the procedure is executed again in the next round. 
The following are the main predicates  used in our Algorithms:


  * [ID/Role]: the agent sees another agent with identifier ID (or role Role) arriving at the node where it resides, or the agent arrives in a node, and it sees another agent with identifier ID (or role Role). 


Furthermore, the following variables are maintained by the algorithms:


  * , : the total number of rounds and distinct visited nodes[An agent is able to identify if the node where it resides has been previously visited or not by counting the number of steps it has performed in certain direction.], respectively, since the beginning of the execution.


  * , : the total number of rounds and distinct visited nodes, respectively, since the last call of procedure .

  * [C/ (CC)]: the number of rounds during which the clockwise/ (resp. counter-clockwise) edge is missing since the last call of procedure .

  * #Meets[ID]: the number of times the agent has met with agent ID.

  * RLastMet[ID]  records the number of rounds elapsed since the agent has seen (or meet) an agent with id ID


Observe that, in a fully synchronous system, when predicate [y] holds for an agent a with id x, then predicate [x] holds for the agent with id y.  
In the pebble model we will also use the procedure: it is analogous to  , with the main difference that the agent uses the pebble to perform a cautious walk. That is, the agent leaves a pebble on the current node, it moves to the node in the moving direction, then it goes back to remove the left pebble, and finally it returns to the recently explored node. 


Communication and pebble removal. As for the ability of agents to interact, we observe that, even in the  simpler pebble  model, any communication between agents located at the same node is easy to achieve (e.g.,  two agents may exchange messages of any size   using a communication protocol in which they send one bit every constant number of rounds). 
Therefore, we can assume that, in the exogenous models, agents are able to communicate. 
 Specifically, the communication of constant size messages is assumed to be instantaneous, since it can implemented trivially by a multiplexing mechanism (the logical rounds are divided in a constant number of physical round, the first of which is used to execute the actual algorithm and the others to communicate). During a cautious walk using procedure, agent x might return to a node to retrieve its pebble, even while another agent is present on the same node. In such instances, the two agents meet, but any state transitions initiated by this meeting will only take effect after agent x has successfully reclaimed its pebble.





 §.§ : An algorithm for colocated agents


In this section we describe the algorithm presented in <cit.>. The algorithm solves the when three agents with visible IDs start from the same node. We will use as subprocedure in our algorithm for the scattered case (Section <ref>). 

The algorithm uses three agents: the Avanguard, the , and  the . 
The three agents start on the home-base node v_0.

Agents and move clockwise simulating a cautious walk. In particular,
If   the edge e in the clockwise direction is not present, both agents wait until it  reappears.  If edge e is present, moves to the unexplored node using edge e. Then, 
if in a successive round the edge e is still present, goes back to ,  signalling 
that the visited node is safe;  at this point,  both and move clockwise to the recently explored node.
If  does not return when e is present, then the knows that the node visited by is the blackhole. 

moves as follows:
it goes counter-clockwise until it visits the first unexplored node; then, it goes back clockwise until it meets again .
Once meets , it moves again counter-clockwise, iterating the same pattern. In case finds a missing edge on its path, it waits until the edge re-appears;  then  it resumes its movement. 
 


 If the sees a missing edge e in its clockwise direction and, while waiting for e to appear, does not meet after enough time for to explore a  node and go back, then we say that Agent fails to report to . 
  In this case, entered the black hole, hence the can correctly compute its location. 


 <cit.>
  Consider  a dynamic ring  R, with three colocated agents with distinct IDs in the Vision model. 
  Algorithm solves    with O(n^2) moves and in O(n^2) rounds. 




§ IMPOSSIBILITY WITH SCATTERED AGENTS AND ENDOGENOUS COMMUNICATION


When the agents are scattered, three of them, even equipped with the stronger endogenous mechanism (i.e., F2F model), cannot solve on rings of arbitrary size, as shown by the following: 


Three scattered agents in the F2F model cannot solve on a static ring 
of arbitrary size n, even if they
have distinct IDs.  


Let A be an algorithm that correctly solves the problem. The proof is by contradiction: we will show that there exists an initial configuration C of the 3 agents on a ring of a proper size n>10 that makes A fail.
We will construct the configuration C in such a way that no two agents meet. Let id_1,id_2,id_3 be the IDs of agents. We consider the behaviour of agent id_i until round r in a run where it executes the algorithm A, and it does not meet any agent. Let D(a_i,n,r) the maximum distance in any direction travelled by an agent until round r. Let r_m be the minimum round at which  D(a_i,n,r)>0 for some a_i.  Without loss of generality, let id_1 be this agent. We can position the agents so that id_1 is adjacent to the blackhole and enters it at round r_m. Every other agent can be positioned such that they have not met any other agent by round r_m. At this stage, we are left with two agents, and we can invoke Th. <ref> to conclude that it is impossible to solve the problem. Note that the premise of Th. <ref> is based on co-located agents. However, this scenario is simpler than the dispersed case, so the result is applicable to our context as well.








Fortunately, any exogenous mechanism circumvents the impossibility of Obs. <ref>. In the following we focus on such mechanisms.



§ EXOGENOUS COMMUNICATIONS: LOWER BOUND FOR SIZE-OPTIMAL ALGORITHMS.


We now consider the Exogenous Communications.
Interestingly, we can show a quadratic lower bound on the number of moves and rounds of any size-optimal algorithm that solve that with scattered agents; the bound holds even if agents have IDs and whiteboards are present.


In  a dynamic ring R   with whiteboards, any algorithm A for with three scattered agents with unique IDs requires Ω(n^2) moves and Ω(n^2) rounds.


The proof is by contradiction. Let A be a sub-quadratic algorithm that solves the ; and let a, b, and c be the three agents. Suppose the agents have unique IDs, and, without loss of generality, let c be the first agent that moves. 

Let us assume an initial configuration where c is initially placed on node v_c, neighbour of the , and where a and b are on two neighbours nodes, v_a and v_b, at distance n/2 from v_c. 
 Furthermore, w.l.o.g, let us assume that c is placed in such a way that when it moves, at round r=0, it immediately enters ; also, let v_c be the  counter-clockwise neighbor of the .

Note that, (N1) since c enters the blackhole at round 0 and it can write information on node v_c (whiteboard model), agents a and b can compute the position of the only in two cases: either (N1.1) one of them enters or (N1.2) one of them visits node v_c.  We now prove that case (N1.2) might never happen.
Let U_r be the partition of nodes explored by agents a and b at the end of round r. By Observation <ref>, agents a and b may explore a node outside U_r only if they try to traverse at the same round both the edges crossing the cut U_r and V ∖ U_r. Let e_c be the clockwise edge incident in U_r, and e_cc be the counter-clockwise one. Edge e_c might always be missing, thus preventing the agents from crossing it. Therefore, might only be reached by its clockwise neighbor, and node v_c will never be explored. 

Since the blackhole  is at distance n/2 from both v_a and v_b, by (N1.1) there must exists a set of rounds r_1,r_2,…,r_n/8  where U_r_j≥ n/8+j.  

We now prove that if A is sub-quadratic, then in one of these rounds, there must exist an agent, say b, that explores at least two nodes, say v_1 at round r_1 and v_2 at round r_2, such that (1) it does not communicate with a between the two explorations and (2) both a and b visit o(n) disjoint nodes between r_1 and r_2.  
Assume by contradiction then neither (1) or (2) apply. Then, in each U_r_j agent b explores only one node and the agents collectively performs at least n/8 moves. Since there are n/8 such rounds we have at least O(n^2) moves. Thus having a contradiction. 

Note that, since the initial configuration is arbitrary and a and b never received any information communicated from c, the positions of v_1 and v_2 do not depend on the positions of and v_c. Therefore, there can exist two initial configurations C_1 and C_2, such that v_1=in C_1 and v_2=in C_2. 
Since b reaches the by round r_2, a is the only agent that can disambiguate between the two configurations. However, a might be blocked indefinitely on a set of nodes that was never visited by b after round r_1 (see Observation <ref> – at round r_2 agent a is trying to traverse edge e_c). 
Consequently, a is not able to distinguish between C_1 and C_2; thus, A cannot be correct, having a contradiction.
Finally, the bound on the number of rounds derives immediately from the bound on moves and from having a constant number of agents.


The above theorem shows the cost optimality of the size-optimal algorithm described in the following Section <ref>. 



§ AN OPTIMAL EXOGENOUS ALGORITHM: 
 
In this section, we describe an algorithm to solve the problem with k=3 agents using pebbles.
We name the algorithm . works in two phases:




  * Phase 1: In the first phase agents move clockwise using pebbles to implement a cautious walk. If they meet they synchronise their movements such that at most one of them enters in the black hole. This phase lasts until all three agents meet or 9n rounds have passed. 
We will show that at the end of this phase we have either:


  * (1) three agents are on the same node or on the two endpoint nodes of the same  edge. In this case we say that agents gathered; 

  * (2) the counter-clockwise neighbour of the black hole has been marked, at most one agent is lost, and the two remaining agents are gathered (that is they are on the same node, or on two endpoints of an edge);

  * (3) one agent is lost in the black hole and the counter-clockwise neighbour of the black hole has been marked. The remaining two agents either both terminated, locating , or only one terminated, with the other still looking for the . In Phase 2 this last agent will either terminate or it will be blocked forever (in both cases the problem is solved). 



  * Phase 2: The second phase starts after the previous one, and relies on the properties enforced by the first phase. In particular, if at the beginning of this phase three agents are on the same node, they start algorithm . Otherwise, if two agents are on the same node, they act similarly to and in .  If none of the above applies, then two agents are on the two endpoints of a missing edge, or only a single agent is still looking for the . This scenario is detected by a timeout strategy: upon a timeout, an agent starts moving clockwise looking for the node marked during Phase 1. If two agents meet during this process, they act similarly to and in . Otherwise, in case a single agent is still active, it will either reach the marked node (and terminate correctly) or it will be blocked forever on a missing edge. We remark that in this last case there has been an agent correctly terminating in Phase 1, and thus is still correctly solved.  




 §.§ Detailed Description.

The pseudocode of Phase 1 is reported in Algorithms <ref>, <ref>, and <ref>; and Phase 2 in Algorithms <ref> and <ref>. 
In the pseudocode, we use the predicate #A=x that is verified when on the current node there are x agents. Initially, all agents have role Start.

 


 

 



Phase 1: 
The first phase lasts for at most 9n rounds (refer also to the examples in Figure <ref>). The agents start in state Init of Algorithm <ref> and role Start:  
each agent walks cautiously clockwise for 9n rounds. 
If an agent reaches a marked node (predicate marked), then it waits until the next node can be deemed as safe or unsafe (see state Wait). 

If in the marked node the incident clockwise edge is present and the agent that marked the node does not return, then the next node is the black hole (the agent terminates by triggering predicate NextUnsafe). 

If two Start agents meet on the same node (predicate meeting[Start]), they synchronise their movements such that they will never cross an edge leading to a possibly unsafe node in the same round. Specifically, the agents enter in the synchronisation state Two, where one agent becomes Follower (Algorithm <ref>) and the other becomes Explorer (Algorithm <ref>). The role of Explorer is to visit new nodes, while Follower just follows Explorer when a node is safe (this is similar to and in ). 
If the remaining Start agent meets with either the Follower or the Explorer, it will assume the behaviour of the Follower (predicate meeting[Follower] in state Init and state Copy). 
Finally, if the three agents meet on the same node, Phase 1 terminates (see predicate #A=3 in all states). In all cases, at the end of round 9n, this phase ends.  


In Section <ref>, we will show that, if in Phase 1 all the alive agents have not localised the , then either:


  * three agents gathered: either three agents are on the same node, or two agents are on a node v and the third agent is blocked on the clockwise neighbour v' of  (the marked) node v; or

  * the counter-clockwise neighbour of the black hole has been marked, at most one agent is lost, and the two remaining agents are gathered. The two agents are either on the same node, or on two different neighbours node and one of them has marked the node where the other resides. 

  * the counter-clockwise neighbour of the black hole has been marked, at most one agent is lost, one agent correctly terminated, while the other is still looking for the . 













   





; Phase 1 - Algorithm for scattered agents - Start 






   [h]



; Phase 1 - Algorithm for Explorer 





   



; Phase 1 - Algorithm for Follower 









Phase 2: 
The agents start in InitP2 state of Algorithm <ref>: here, several checks are executed to understand how Phase 1 ended and to orchestrate the behaviour of the agents. In more details:



  * Each agent checks if there are other agents on the same node:
in case there are two agents, they get the roles of and MLeader (their behaviour is similar to and in ).
If there are three agents, they start algorithm . 

  * If the agent is missing the pebble, then it was blocked while trying to recover its pebble at the end of Phase 1. The agent tries to recover the pebble by moving counter-clockwise on one step for 4 · n^2 rounds.
If during this period it succeeds then it goes to state Forward. If 4 · n^2 rounds have passed without succeeding, then the agent goes in the Forward state. This move has the following goal: 
if there are two agents on its counter-clockwise node, then they have role and MLeader, and in 4 · n^2  rounds can locate black hole. Otherwise, if there is just one agent on the clockwise node or if there is no one, this timeout avoids that the agent is blocked forever on a missing edge trying to recover a pebble. 


  * If the agent is on a marked node, then it waits there until either it meets the agent that marked the node, or 4 · n^2 rounds have passed.
If they meet, they get the roles of and MLeader; otherwise, if the timeout triggers, the agent goes in state Forward. 


  * If none of the above applies, the agent goes in state Forward.



We now detail the behaviour of the agents: 


  * Agent MLeader and agent . The  MLeader moves clockwise, while acts as in Algorithm . 
If fails to report, MLeader identifies the black hole and terminates. Finally, if MLeader and an agent that is not meet, then this new agent takes the role of and MLeader the role of , and they behave exactly as in Algorithm (predicate meeting[Leader] and state BeAvanguard for the agent with role Start; and predicate [Start] and state GoToCP for the ). The only caveat in this case, is that MLeader keeps the value of variable #Meets[] when switching to .

  * Agent in state Forward. In state Forward an agent moves in the clockwise direction. If it reaches a marked node, then it discovered the black hole and the agent terminates.  If two agents in state Forward meet, they use their IDs to get the roles of MLeader and . 




 
 



; Phase 2 - Algorithm for scattered agents - Start 






 



; Phase 2 - Algorithm for MLeader 







 §.§ Correctness of .


 (Gathered configuration)
We say that a group of k agents gathered if either:


  * There are k agents on the same node; or,

  * There are k-1 agents on node v_i, and one agent a on node v_i+1. Moreover, agent a marked node v_i with a pebble and has to still unmark it.



Let us first start with a technical lemma, derived from <cit.>, and adapted to our specific case. 


If  k agents perform a cautious walk in the same direction for an interval I of 9n rounds and one of the alive agents does not explore n nodes and no agent terminates, then the agents gathered. 


Let A be the set of agents performing a cautious walk, say in clockwise direction, and let a^* be the agent that does not explore n nodes. 

Agent a^* can be blocked in progressing its cautious walk in two possible ways: (i) when it is trying to explore a new node using a missing edge in its clockwise direction (we say that a^* is forward blocked); (ii) when
it is returning to a previously explored node to unmark it (it is blocked by an edge missing in its counter-clockwise direction, and we say that a^* is backward blocked). 
Thus, If in a round r an agent is forward blocked and another one is backward blocked, then they are on two endpoints of the same missing edge.  

 If a^* is not blocked for 3(n-1) rounds then it has explored n nodes. Therefore, a^* has been blocked for at least
 6n-3 rounds or more rounds over an interval of 9n rounds.
If there is a round r' when a^* is blocked, then every a∈ A
that at round r' is not blocked does move (note that all blocked agents are either backward or forward blocked on the same edge of a^*).  


Thus, all agents in A that are not
blocked
 move towards a^* of at least  6n-3/3 =2n-1 steps. 
On the other hand, every time  a^* moves, the other agents might be blocked; however,  by hypothesis, this can occur less than 3n times.
 
 Since  the initial distance between a^* and  an agent  in A  is at most n-1, it follows that
 such a distance increases less than n-1 (due to a^* movements); however, it decreases by 2n-1 (due to a^* being blocked). In conclusion, by the end of I,  all agents are either at the same node or at the two endpoints of a missing edge and the lemma follows.






Given three agents executing Phase 1, at most one of them enters the black hole. In this case, the counter-clockwise neighbour node of the black hole is marked by a pebble. 

If agents have not already met, then each agent performs a cautious walk, all in the same direction, marking a node and avoiding that other agents visit a possibly 
unsafe node (see state Init in Algorithm <ref>): when the agent sees a marked node, it goes in state Waits. In this state, the agent waits until it is sure that the next node is safe (that is, until the agent that marked the node returns to remove the pebble).  

When two agents meet, they become Follower and Explorer. By construction, Follower never reaches : in fact, Follower moves a step clockwise only when it sees  Explorer returning (see state Wait and predicate meeting[Explorer]); this implies that the node where it moves is safe.
Also note that Explorer never visits a possibly unsafe node if there is another agent on it: in fact, in state Explore, there is a check on whether the current node is marked or not; if marked, Explorer waits (thus, also blocking Follower) until the next node can be deemed as safe.  

 If the third agent reaches Follower, it will also become Follower and it will never visit an unsafe node. 
  Moreover, the Explorer agent always marks a node before visiting its unexplored neighbour (see state Explore of Algorithm <ref>).

In conclusion, we have that at most one agent enters , and the counter-clockwise neighbour node of will be marked by a pebble, and the lemma follows. 





If an agent terminates while executing Phase 1, then it correctly terminates. 


The claim follows immediately by observing that the state Terminate is always reached when an agent visits a marked node, the clockwise edge is not missing, and the agent that marked the node does not return. 



Let us consider three agents executing Phase 1. If not all agents terminated locating the , then Phase 1 ends by round 9n and, when it ends, one of the following scenarios holds:


  * (1) all agents gathered; 

  * (2) at most one agent disappeared in the black hole, the counter-clockwise neighbour of the black hole is marked, and the remaining agents gathered;

  * (3) one agent terminated, the counter-clockwise neighbour of the black hole is marked, and the remaining agent has to still locate the . 



By construction, in all states the agents check predicate = 9n; thus, Phase 1 ends after at most 9n rounds. By Lemma <ref> we have that at most one agent enters the , leaving its counter-clockwise neighbour marked.
There are three possible cases:


  * One agent terminates, and by Observation <ref> it terminates correctly solving the .   The other agent has to still locate the 
  * One agent enters in the and no one terminates. If no alive agent terminates, then no one of them has explored n nodes. Therefore, at the end of Phase 1 = 9n and by Lemma <ref>  the agents gathered, and the lemma follows.

  * No agent enters the and no agent terminates. In this case we have that three agents gather by the end of Phase 1.  If agents end Phase 1 because predicate #A=3, then the statement immediately follows.
Otherwise, = 9n, by Lemma <ref>  the agents gathered, and the lemma follows.



The next lemma shows that, if has been marked in Phase 1, then two agents executing Algorithm <ref> solve in at most O(n^2) rounds. 

Let us assume that the counter-clockwise neighbour v of has been marked by a pebble. If two agents execute Algorithm <ref>, at least one of them terminates correctly locating the in O(n^2) rounds; the other agent either
 terminates correctly locating the or it never terminates.  

By Lemma <ref>, at the first round of Phase 2 we have two possible cases:


  * The two agents are at the same node. In this case, they immediately enter in state AssignRoles. Let a be the agent that takes the role of MLeader and b be the one that becomes . 
Their movements are similar to the ones of and in , with the only difference that MLeader moves until it reaches a marked node. 
By Lemma <ref>, this marked node is the counter-clockwise neighbour of ; thus, if MLeader reaches it, MLeader correctly terminates. 

If MLeader does not visit the marked node because of a missing edge, is able to move. By using  a similar argument to the one used in the proof of Theorem <ref>, the black hole is located in at most  O(n^2) rounds, and the lemma follows. 
 Also note that the only agent that can go in a termination state is MLeader, therefore cannot terminate incorrectly. 


  * The two agents occupy two neighbouring nodes, and the most clockwise  agent does not have the pebble.
More precisely, agent a is at node v, agent b at node v'; also, agent b is missing its pebble, and node v is marked by a pebble. In this case, agent a  executes lines <ref>-<ref> of Algorithm <ref>: it removes the pebble from v, and waits for 4 · n^2 rounds.
Agent b  executes line <ref> of Algorithm <ref>: it moves towards node v for 4 · n^2 rounds.  

If edge e=(v, v') appears before the timeout, then a and b meet, and previous case applies. Otherwise, both agents go in state Forward. In this state they both move clockwise. If one of them reaches the marked node, it correctly terminates. Otherwise the path towards is blocked by a missing edge and the agents would meet in at most O(n) rounds.
When they meet, they both go in state AssignRoles, and previous case applies again. Note that this implies that at most one of the agents in state Forward can be blocked forever by a missing edge. 





Let us assume that three agents are gathered after Phase 1. Then, if three agents executes Algorithm <ref>, at least one of them terminates correctly locating the in O(n^2) rounds; the other agents either
 terminate correctly locating the or never terminate.  


If three agents are on the same node, then they start algorithm and the correctness follows from Theorem <ref>. 
Otherwise, we have two agents on a node v, with v marked with a pebble, and the other agent b on v', with v' the clockwise neighbour of v.
Upon the start of Phase 2, the two agents will become and MLeader, respectively; MLeader waits on the marked node, while b tries to go
back to v. 

If edge e=(v,v') is missing for 4 n^2 rounds, then has enough time to reach the black hole, and MLeader to terminate because of the fail to report of , hence the lemma follows. 
Note that after the termination of MLeader, the agent b goes in state Forward, it moves clockwise and either it enters the or is blocked forever by a missing edge; in all cases it
cannot terminate. 


Finally, the last case to analyse is when is blocked by a missing edge in the first 4 n^2 rounds. In this case, MLeader and b meet, and algorithm starts. 
The lemma follows by  Theorem <ref>.  




Let us assume that a single agent a starts  Phase 2. This agent, by executing Algorithm <ref>, either terminates correctly or it waits forever on a missing edge. 


By algorithm construction after at most 4 n^2 rounds from the beginning of Phase 2 the agent a goes in state Forward and it starts moving in clockwise direction. Being the only agent still active,  it will
never change behaviour until it reaches the marked node or another agent.

 By Lemma <ref> the counter-clockwise neighbour of is marked, and the terminated agent is located at that node. 
 If no edge is removed forever, a will reach the marked node, and it will terminate. 
 Otherwise, a will be forever blocked on a missing edge. 



Given a dynamic ring R, three agents with visible IDs and pebbles running , solve in  O(n^2) moves and O(n^2) rounds.


By Lemma <ref>, Phase 1 terminates in at most O(n) rounds. At this time, either: (1) is solved and all agents terminated, or  (2) the agents gathered, or  (3) the counter-clockwise neigbhour of is marked and the remaining agents are gathered, or (4) there is still an agent active while an agent correctly terminated. 
In case (2), the proof follows by Lemma <ref>.
In case (3), the proof follows by Lemma <ref>.
In case (4), the proof follows by Lemma  <ref>.


By Th. <ref> and Th. <ref> we have:

Algorithm is  size-optimal with optimal cost and time. 
 



§ CONCLUSION


In this paper, we have investigated the on dynamic rings in scenarios where agents are scattered. However, several questions remain open. In particular, we believe that the findings in Observation <ref> could potentially be applied to any constant number of agents. Another unresolved issue is the examination of unoriented rings with scattered and anonymous agents, as well as the development of faster algorithm for groups larger than three agents.




