Perpetual Exploration of a Ring in Presence of Byzantine Black Hole

The black hole search (i.e., BHS) problem is a prominent variation of exploration problem studied in the literature. A survey of which can be found in [19]. This problem is investigated under various topologies (such as trees [8], rings [13], tori [5] and in arbitrary and unknown networks [7, 11]). All these discussed networks are static in nature. Recently, there has been a lot of interest in dynamic networks. The following papers [3, 4, 10], studied the BHS problem on dynamic ring, dynamic torus and dynamic cactus graph, where the underlying condition is that, irrespective of how many edges are dynamic in nature, the network must remain connected at any time interval (which is also termed as 1-interval connected). In rings, the BHS problem has been studied for different variants; the most predominant among them are choice of schedulers (i.e., synchronous [6] and asynchronous [1]), communication tools (i.e., face-to-face [7], pebble [16] and whiteboard [1]) and initial position of the agents (i.e., co-located [1] and scattered [6]).

The most relevant papers related to our work are the papers by Královič et al. [18] and by Bampas et al. [2]. The paper by Královič et al. [18] is the first to introduce a variant of this black hole, where the black hole has the ability to either choose to destroy an agent or let it pass (which they term as gray hole). Further they extended the notion of gray hole, where the gray hole has the following additional capabilities: it has the ability to alter the run time environment (i.e., changing the whiteboard information), or it has the ability to not to maintain communication protocol (i.e., do not maintain FIFO order). They solved this problem under an asynchronous scheduler on a ring, only when the agents are initially co-located and each node in the network has a whiteboard. The following results are obtained by them, they gave an upper bound of 9 agents for performing periodic data retrieval (i.e., which is equivalent to perpetual exploration) in the presence of a gray hole; further, in addition to gray hole, when the whiteboard is unreliable as well, they proposed an upper bound of 27 agents. Next, Bampas et al. [2] significantly improved the earlier results. They showed a non-trivial lower bound of 4 agents and 5 agents for gray hole case and for gray hole with unreliable whiteboard case, respectively. Further, with 4 agents as well, they obtained an optimal result for the gray hole case, whereas with 7 agents proposed a protocol for the case with gray hole and unreliable whiteboard. As far as we are aware, we are the first to investigate the perpetual exploration problem of a ring under different communication tools (i.e., face-to-face, pebble and whiteboard) as well as for different initial positions (i.e., co-located and scattered), for a variant of gray hole, where it can erase any previously stored information but can not alter it. We term this type of gray hole a Byzantine black hole. In the following part, we discuss the results we have obtained.
Our Contribution: In this paper, we investigate the perpetual exploration problem, by a team of synchronous mobile agents, of a ring $R$ of size $n$, in the presence of a Byzantine black hole. First, we consider the case when the agents are initially co-located. We obtain the following results.
A: For Pebble model of communication, we obtain that 3 agents are necessary and sufficient to perpetually explore $R$.
B: For Face-to-Face model of communication, we obtain that 5 agents are sufficient to perpetually explore $R$.
C: For Whiteboard model as well, we achieve the same lower and upper bounds as mentioned in A. This result shows that, by considering the scheduler to be synchronous instead of asynchronous (as assumed in [2]), the tight bound on the number of agents to perpetually explore $R$, reduces from 4 to 3.
Next, we consider the case, when the agents are initially scattered, and in this context, we obtain the following results:
D: For Pebble model of communication, we show that 4 agents are necessary and sufficient to explore $R$ perpetually .
E: For Whiteboard model of communication, we obtain an improved bound of 3 agents (in comparison to D), which is necessary and sufficient to explore the ring $R$ perpetually.
In the following Table 1, we have summarized the results.

In this section, we consider the communication model, where the starting node has $k-1$ identical and movable tokens (termed as pebbles), where $k$ is the total number of agents deployed. A pebble can be carried by an agent from one node to another. This pebble acts as a mode of communication for the agents, as the agents can perceive the presence of a pebble at the current node. Moreover, an agent can also perceive the presence of other agents which are co-located at the current round (i.e., gather the IDs of the other co-located agents). Our main aim is to prove the following theorem in this section.

The necessary part follows from Corollary 3.3. For the sufficiency part we present an algorithm, PerpExplore-Coloc-Pbl. We have provided a very brief description of the algorithm. For detailed description and pseudo code see Appendix (Section 9).

The main idea of this algorithm is as follows: initially two agents $a_{1}$ and $a_{2}$ explores the ring perpetually, while $a_{3}$ waits at the $home$. $a_{1}$ and $a_{2}$ explores the ring $R$, executing the rule described as follows. If all the three agents are at $home$ along with two pebbles, then in the $r-$th round ($r\geq 0$), $a_{1}$ moves clockwise with one pebble and it waits at round $r+1$ for $a_{2}$ to arrive. In round $(r+1)$, $a_{2}$, leaving the remaining pebble at $home$ moves to the next node along clockwise direction to meet $a_{1}$. In the subsequent round, i.e., $(r+2)-$th round, $a_{1}$ after meeting $a_{2}$ moves again to the next node in the clockwise direction and waits for 3 rounds (i.e., till $(r+5)-$th round) for $a_{2}$ if and only if $a_{1}$ is not at $home$. In the mean time at $(r+3)-$th round, $a_{2}$ leaves its current node, moves one step in counter-clockwise direction, collects the left behind pebble. Then in $(r+4)-$th round $a_{2}$ moves again to the earlier node in clockwise direction. Subsequently, in $(r+5)-$th round, $a_{2}$ again leaves the pebble at its current node, and moves in a clockwise direction, to meet $a_{1}$ (which is waiting at the current node for $a_{2}$ to arrive), for better reference see Fig. 1. Note that, when $a_{2}$ meets $a_{1}$ outside $home$, the pebble it was carrying is left by $a_{2}$ at the nearest counter-clockwise node of the meeting node (i.e., where $a_{2}$ meets with $a_{1}$). Now from round $(r+6)$ onwards to $(r+9)-$th round, the same execution repeats, as it has occurred between round $(r+2)$ to round $(r+5)$. The only difference is that, if both agents (i.e., $a_{1}$ and $a_{2}$) at round $r+2$ were at a node $v_{1}$, at round $r+6$, they are on the nearest clockwise node of $v_{1}$ (i.e., at $v_{2}$, say). This process continues until $a_{1}$ reaches $home$. In this case $a_{1}$ does not move clockwise, until $a_{2}$ meets it with the pebble it was carrying, in that case, it waits further until $a_{2}$ brings that pebble back at $home$. For this to happen after reaching $home$, 5 rounds are sufficient for waiting. When $a_{2}$ reaches $home$ with the pebble, then all 3 agents are again at the $home$ with 2 pebbles. This way the 3 agents explore the ring. The exploration can hamper if either $a_{1}$ or, $a_{2}$, or a pebble is destroyed by the Byzantine black hole $v_{b}$ while the above mentioned procedure is executed by them.

Firstly, let only $a_{1}$ is destroyed at some round $t$. Then there must exists a round $t^{\prime}<t$, when $a_{2}$ was with $a_{1}$ at some node $v_{0}$ (say) for the last time. This means at round $t^{\prime}$, $a_{1}$ moved clockwise to the next node $v_{1}$ along with the pebble it was carrying, and it must have been destroyed before or at the round when $a_{2}$ reaches $v_{1}$ again (in this case $v_{1}$ is $v_{b}$). Now when $a_{2}$ reaches $v_{1}$ there can be two cases. Either $a_{2}$ remains alive or (as the adversary may choose not to destroy $a_{2}$), it can get destroyed as well. For the initial case, $a_{2}$ identifies the Byzantine black hole by not seeing $a_{1}$ there and then it can leave that node and can explore the ring perpetually avoiding the node. The latter case is equivalent to both $a_{1}$ and $a_{2}$ are destroyed by the Byzantine black hole $v_{b}=v_{1}$. Note that since outside $home$ whenever $a_{2}$ reaches the same node of $a_{1}$, it leaves behind a pebble at the nearest counter-clockwise node (here $v_{0}$). For this case, another agent (i.e., $a_{3}$) which was waiting at $home$, finds none of the two exploring agents returns at $home$, even after waiting for a sufficient number of rounds. This incident triggers $a_{3}$ to move clockwise until it finds a pebble (one that is left behind by $a_{2}$ at $v_{0}$). Whenever the pebble is found, $a_{3}$ knows that the next clockwise node is the Byzantine black hole and it starts exploring $R$ avoiding that node.

Now, there can be two other cases that can hamper the above mentioned exploring procedure. For the first case, let only $a_{2}$ is destroyed at some round $t>0$. Let $t^{\prime}<t$ be the last round before $t$ when both $a_{1}$ and $a_{2}$ were together at a node $v_{0}$. At round $t^{\prime}$, $a_{1}$, moves clockwise to the next node $v_{1}$. Now if $a_{2}$ is not destroyed in the next 3 rounds, then it meets $a_{1}$ at $v_{1}$ again, contrary to our assumption. So, if only $a_{2}$ is destroyed then it must be at any of the rounds $t^{\prime}+1,t^{\prime}+2$ or $t^{\prime}+3$. In this 3 round $a_{2}$ can be either on $v_{0}$ or $v_{-1}$ where, $v_{-1}$ is the counter-clockwise nearest node of $v_{0}$. In this case, when $a_{1}$ finds $a_{2}$ has not arrived at $v_{1}$ even after waiting for 3 rounds, in which case, it understands that either $v_{0}$ or $v_{-1}$ is the Byzantine black hole. This knowledge triggers $a_{1}$ to move clockwise until it meets $a_{3}$ at $home$, leaving the pebble along with it behind at $v_{1}$. When $a_{3}$ sees that even after certain round of waiting only $a_{1}$ is able to arrive at $home$, and that too without the pebble it was supposed to be carrying, $a_{3}$ understands that $a_{1}$ must have detected an anomaly. In this case both $a_{1}$ and $a_{3}$ moves counter-clockwise together to find the pebble left by $a_{1}$. When they find it they declare $v_{1}$ as $home$. After this they start exploring the ring in different directions in the following way. $a_{1}$ moves clockwise until $v_{-1}$ and $a_{3}$ starts moving counter-clockwise until $v_{0}$. After that, they both move in opposite direction until they again reach $home$ (which is the new $home$) and waits for sufficient number of rounds to meet each other. This way the exploration keeps going on until one among $a_{1}$ or $a_{3}$ is destroyed. Let $a_{3}$ fails to reach $home$. In that case, $a_{1}$ will detect that $v_{0}$ must be the Byzantine black hole and it can start exploring the ring $R$ avoiding $v_{0}$. On the other hand if $a_{1}$ fails to reach then it must be destroyed by the Byzantine black hole which is nothing but the node $v_{-1}$. Knowing this $a_{3}$ then explores the ring avoiding that node. Now there can be another case when no agents but a pebble is destroyed at $v_{b}$. This pebble must be the pebble that is left behind at $v_{-1}$ by the agent $a_{2}$ when it reaches $v_{0}$ to meet $a_{1}$. In this case, only the pebble can be destroyed before $a_{2}$ reaches to collect the pebble back. So, when $a_{2}$ reaches $v_{-1}$, it finds out that there is no pebble. This leads to $a_{2}$, knowing that $v_{-1}$ is the Byzantine black hole and in which case it starts exploring the ring $R$ avoiding that node. If $a_{2}$ is also destroyed while it reaches $v_{-1}$ to collect the pebble, this case is similar to the case where we described the algorithm when only $a_{2}$ is destroyed.

We first prove that if no agents are destroyed then either the agents continue with the exploration of ring $R$ without knowing the exact location of the Byzantine black hole, or there exists at least one agent that knows the exact location of the Byzantine black hole which can then explore the ring indefinitely avoiding the Byzantine black hole (See Lemma 9.1 in Appendix). Next we proved that, if one agent is destroyed while exploring the ring, then either there exists one agent that identifies the Byzantine black hole uniquely and continues to indefinitely explore all nodes of the ring, except the Byzantine black hole or the exploration continues while the length of the suspicious region (i.e., $|S|$) decreases to 2 from $n-1$ (Lemma 9.3 in Appendix). For the later case we proved that the exploration continues until another agent is destroyed by the Byzantine black hole (Remark 9.5 in Appendix). In this case when two agents are destroyed by the Byzantine black hole, the only alive agent can uniquely identify the Byzantine black hole without moving on to it (Lemma 9.6 in Appendix). Thus it can then perform the exploration of $R$ avoiding the Byzantine black hole. This proves Theorem 4.2.

In this section, we consider the Face-to-Face (also termed as F2F) model and prove the following theorem.

In order to prove Theorem 4.3, we discuss an algorithm with 5 co-located agents, where each agent can communicate among themselves at the same node at the same round (i.e., each agent have F2F model of communication). Initially 3 lowest ID agents, say, $a_{1}$, $a_{2}$ and $a_{3}$ are chosen, where fourth lowest ID agent say, $a_{4}$, is associated with $a_{1}$ and the largest ID agent, say $a_{5}$, is associated with $a_{2}$. The idea of the algorithm resembles to that of the algorithm PerpExplore-Coloc-Pbl. Note that as in this case there is no existence of pebbles, hence, we configure the behaviour of the agents $a_{4}$ and $a_{5}$ in such a way that they act as pebbles, associated with $a_{1}$ and $a_{2}$ in PerpExplore-Coloc-Pbl, respectively. In PerpExplore-Coloc-Pbl when we say that an agent $a_{i}$ carries a pebble $p$, in this case we mean that the agent $a_{i}$ communicates a message carry with its associated agent $a_{i^{\prime}}$ such that both these agents simultaneously move together until further new instruction is communicated. On the contrary as per PerpExplore-Coloc-Pbl when we say that an agent $a_{i}$ drops a pebble $p$ at a node $v$, then in this case we mean that $a_{i}$ communicates a message drop with $a_{i^{\prime}}$, which in turn instructs $a_{i^{\prime}}$ not to move further and remain stationary at the node $v$ until further instruction is communicated. Hence, with this terminology, a team of 5 agents can execute the algorithm PerpExplore-Coloc-Pbl, and the correctness also follows similarly. This shows that a team of 5 co-located and synchronous agents are sufficient to solve PerpExploration-BBH under F2F model of communication. This proves Theorem 4.3.

The algorithm PerpExplore-Coloc-Pbl can be simulated in whiteboard model of communication. A pebble on a node can be simulated by a bit of information, which is marked on the whiteboard of that node. Note that, collecting a pebble from the node is simulated by erasing the same bit of information, on that node and dropping the pebble can be simulated by marking the node with a bit of information as well on the whiteboard of that node. From this we get the following result for whiteboard model of communication.

Previously in [2], for asynchronous scheduler the tight bound for number of agents to solve this problem was 4. Now from Theorem 4.4, we get a trade-off between reducing the optimal number of agents required vs the scheduler, in presence of a more generalized version of gray hole as well (i.e., Byzantine black hole).

Our goal in this section is to prove the following theorem.

The necessary part follows from Corollary 3.5. For the sufficient part, we present an algorithm PerpExplore-Scat-Pbl, that can solve the PerpExploration-BBH problem in the above context. In this algorithm we assumed that 4 agents are initially scattered at 4 different nodes of $R$. To include the remaining cases where the agents are initially scattered at less than or equal to 3 nodes, a slight modification of PerpExplore-Scat-Pbl is enough which we describe in Remark 10.7 in Appendix. Here we describe only the main idea of the algorithm. The detailed description and pseudocodes of the algorithm can also be found at the Appendix (Section 10.1).

Agent $a_{i}$ moves clockwise along $Seg(a_{i})$ leaving its pebble at $h_{i}$ until it reaches $h_{(i+1)\pmod{4}}$ (i.e., the end of $Seg(a_{i})$). An agent can distinguish the node $h_{(i+1)\pmod{4}}$ by seeing the pebble left there by the agent $a_{(i+1)\pmod{4}}$. When $a_{i}$ reaches $h_{(i+1)\pmod{4}}$ traversing $Seg(a_{i})$ for the first time, it knows the length of the segment $Seg(a_{i})$ and stores the length in its own memory. For further traversals it does not depend on seeing pebbles at the end nodes of the segment. It can simply use the length of the segment. After $a_{i}$ reaches $h_{(i+1)\pmod{4}}$, it waits there for a certain number of rounds so that the other agents can in the meantime reach the endpoints of there corresponding segments, while moving along a clockwise direction. After this waiting, $a_{i}$ collects the pebble (if exists) from $h_{(i+1)\pmod{4}}$ (the pebble left by $a_{(i+1)\pmod{4}}$) and starts moving counter-clockwise along with the collected pebble until it reaches its own $home$, i.e., $h_{i}$ along with the pebble it was carrying. The waiting time at $h_{(i+1)\pmod{4}}$ also ensures that all agents starts moving counter-clockwise at the same round. Also note that, if $a_{i}$ does not find any pebble to collect at $h_{(i+1)\pmod{4}}$ it starts moving counter-clockwise without any pebble (this case can only happen if $a_{(i+1)\pmod{4}}$ is destroyed at the Byzantine black hole node $v_{b}$, while it was returning back after collecting the pebble from $h_{(i+2)\pmod{4}}$ in some previous round). After $a_{i}$ reaches $h_{i}$ moving counter-clockwise, it again waits for another set of rounds before it repeats the whole process again. Again, the waiting time at $h_{i}$ is configured in such a way that, all agents start repeating the process at the same round (for details on the precise value of these waiting times, refer to the detailed description of the algorithm in Appendix in Section 10.1). Note that, since $\cup_{i=0}^{3}Seg(a_{i})=R$, if no agents are destroyed, the perpetual exploration of $R$ happens.

The exploration can be hampered only if, an agent is destroyed at the Byzantine black hole node $v_{b}$. Note that, since $Seg(a_{i})\cap Seg(a_{j})$ is either empty or consists of a safe node and in addition to that, as a segment is explored by only one agent. Hence, at most one agent can be destroyed while exploring their respective segments, as described above. Without loss of generality, let $v_{b}\in Seg(a_{j})$, for some $j\in\{0,1,2,3\}$. Now there are two cases.
Case-I: Let $a_{j}$ is destroyed while moving clockwise. For this case, $a_{j}$ fails to collect the pebble at $h_{(j+1)\pmod{4}}$ left by $a_{(j+1)\pmod{4}}$ and return $h_{j}$. So, when $a_{(j+1)\pmod{4}}$, returns $h_{(j+1)\pmod{4}}$ after moving counter-clockwise along with the pebble it has collected from $h_{(j+2)\pmod{4}}$, it finds two pebble at $h_{(j+1)\pmod{4}}$. This is considered by $a_{(j+1)\pmod{4}}$ as an anomaly and it learns that $v_{b}$ must be in the arc, which is in the counter-clockwise direction starting from $h_{(j+1)\pmod{4}}$. In this scenario, $a_{(j+1)\pmod{4}}$ waits a certain number of rounds (if needed) to ensure that every other alive agents have reached their corresponding $home$. Then $a_{(j+1)\pmod{4}}$ starts moving clockwise with both the pebbles. The aim of this move is to meet and gather with the other alive agents. Note that the other alive agents wait at their corresponding $home$, after moving along the counter-clockwise direction. It is because, at their respective $home$ they do not detect any anomaly. The waiting time is provided in such a way that it is enough for $a_{(j+1)\pmod{4}}$ to detect anomaly and meet both the remaining alive agents after moving clockwise, while the other agents are waiting at their $home$. The agent $a_{(j+1)\pmod{4}}$ first meets $a_{(j+2)\pmod{4}}$ at $h_{(j+2)\pmod{4}}$ while it moves clockwise after detecting anomaly. Then both of them moves together, while $a_{(j+2)\pmod{4}}$ carries the pebble, which it was earlier carrying back to $home$. They move until they meet with $a_{(j+3)\pmod{4}}$ at $h_{(j+3)\pmod{4}}$. Note that at this moment 3 agents are at a node (which is $h_{(j+3)\pmod{4}}$), with at least 3 pebbles (one carried by $a_{(j+3)\pmod{4}}$ and two carried by $a_{(j+2)\pmod{4}}$). In this case they execute the algorithm PerpExplore-Coloc-Pbl and achieve PerpExploration-BBH of the ring $R$.
Case-II: Let $a_{j}$ be destroyed at $v_{b}$ while it was moving counter-clockwise along with the pebble it collected from $h_{(j+1)\pmod{4}}$. Then in this case, when all alive agents return to their corresponding $home$, none of them finds any anomaly as all agent sees exactly one pebble at their $home$. So, they wait and start the exploration again at the same round. Note that in this scenario, all agents except $a_{j}$, move clockwise to the end points of their corresponding segments, waits there and collects pebble (if any) and moves back to their corresponding $home$ again. Now, since $a_{j}$ was destroyed earlier, the pebble left by $a_{(j+1)\pmod{4}}$ was picked by no agents and thus, while $a_{(j+1)\pmod{4}}$ returns back to $h_{(j+1)\pmod{4}}$ it finds two pebbles and does the same execution as explained in Case-I.

The basic idea of this algorithm is to gather three agents with at least 3 pebbles (refer Remark 10.1) in the expense of one agent and then execute PerpExplore-Coloc-Pbl to solve the PerpExplroation-BBH problem.
Sketch of Correctness: To proof the correctness of the algorithm PerpExplore-Scat-Pbl, we have to prove the following theorem. Here we only provide the proof idea. For details see Appendix (Section 10.2).

First in Corollary 10.4, we proved that algorithm PerpExplore-Scat-Pbl guarantees exploration if no agents are destroyed. This corollary is a direct consequence of the Lemma 10.2. Further we showed that if an agent is destroyed then exactly one agent detects anomaly and that agent gathers with the remaining two alive agents within finite rounds (Lemma 10.5 in Appendix). The rest of the proof follows from Theorem 4.2.

The main aim of this section is to prove the following theorem.

The necessary part follows from Corollary 3.2. The sufficiency part for co-located initial situation follows from Theorem 4.4. For the other cases where the agents are initially scattered at more than one starting nodes, we propose an algorithm PerpExplore-Scat-Whitbrd. This algorithm is designed for the case when all the agents are starting at different nodes. Note that, this algorithm can be easily modified a bit to include the case where initially three agents are scattered at two distinct nodes (refer the modification in Appendix, Section 11.3). For detailed description and the pseudo code, see Appendix (Section 11.1).
Brief Description of the Algorithm: Let $a_{0},a_{1}$ and $a_{2}$ be three agents starting from the nodes $h_{0},h_{1}$ and $h_{2}$, respectively, where these nodes are in a clockwise order. Let $Seg(a_{i})$ (also called ‘Segment of $a_{i}$’) be the clockwise arc starting from $h_{i}$ and ending at $h_{(i+1)\pmod{3}}$. The algorithm first ensures that the ring is explored perpetually if no agents are destroyed. In order to do this, the algorithm goes as follows.

An agent, say $a_{i}$, first erases all previously stored data (if any) at $h_{i}$. Then it writes the message (home, ID($a_{i}$)) at $h_{i}$ and starts moving clockwise. This type of message is called a home type message that indicates it is $home$ of $a_{i}$. $a_{i}$ moves clockwise until it reaches $h_{(i+1)\pmod{3}}$. It distinguishes $h_{(i+1)\pmod{3}}$ by seeing the home type message left by $a_{(i+1)\pmod{3}}$. When $a_{i}$ moves clockwise, it also marks each node of $Seg(a_{i})$, except $h_{i}$ and $h_{(i+1)\pmod{3}}$, by writing right, after erasing any previous such markings (if at all exists) at each such nodes. After $a_{i}$ reaches $h_{(i+1)\pmod{3}}$ it waits for a certain number of rounds (if needed), so that the other agents (say $a_{j}$) gets enough time to reach endpoints of their corresponding segment (i.e.,$h_{(j+1)\pmod{3}}$). After this waiting, each alive agent $a_{i}$ write the message (visited, ID($a_{i}$)) at $h_{(i+1)\pmod{3}}$ at the same round. This type of messages is termed as a visited type message, which indicates that an agent with its corresponding ID, also mentioned in the visited type message, has visited the respective node. Then each $a_{i}$ waits for $n$ rounds at $h_{(i+1)\pmod{3}}$ and then starts moving counter-clockwise at the same round. $a_{i}$ moves counter-clockwise until it reaches $h_{i}$, i.e., its own $home$. While moving counter-clockwise, $a_{i}$ erases previously written right marking (which it marked while moving along clockwise direction) from each nodes of $Seg(a_{i})$ and writes left there upon arriving (except at $h_{i}$ and at $h_{(i+1)\pmod{3}}$). When $a_{i}$ reaches its own $home$ (i.e., $h_{i}$), it waits again for a certain number of rounds, upon seeing the visited type message, left there by $a_{(i-1)\pmod{3}}$. This waiting period is enough for each of the other alive agents to reach their corresponding $home$. After this waiting period is over, all of the agents, starts repeating the same procedure again together, from the same round. This procedure ensures that, if no agent is destroyed at the Byzantine black hole node $v_{b}$, then the perpetual exploration of $R$ continues. This can only be hampered, only if an agent gets destroyed at the node $v_{b}$. Without loss of generality let $v_{b}\in Seg(a_{j})$ for some, $j\in\{0,1,2\}$. So only $a_{j}$ can be destroyed at $v_{b}$, while performing this exploration. It is because $a_{j}$ is the only agent to visit each node $u$ of $Seg(a_{j})$, where $u\in Seg(a_{j})\backslash\{h_{j},h_{(j+1)\pmod{3}}\}$. There can be two cases.
Case-I: Let $a_{j}$ be destroyed while it is moving in clockwise direction along $Seg(a_{j})$. This implies it fails to reach $h_{(j+1)\pmod{3}}$ and also fails to write a visited type message there. So, when $a_{(j+1)\pmod{3}}$ returns to its $home$ (i.e., $h_{(j+1)\pmod{3}}$), it finds no visited type message (as it should’ve, if $a_{i}$ was not destroyed). $a_{(j+1)\pmod{3}}$ interprets from this that, the segment which is adjacent to its own segment in counter-clockwise direction has the Byzantine black hole and an agent must have been destroyed there while moving clockwise. This information triggers it to move clockwise with the aim of gathering with the other agent (i.e., $a_{(j+2)\pmod{3}}$). Note that, when $a_{(j+1)\pmod{3}}$ starts moving, the other agent is waiting and the waiting time is sufficient for the moving agent to meet it. After they meet, $a_{(j+1)\pmod{3}}$ shares the information about its direction of movement in the whiteboard of $h_{(j+2)\pmod{3}}$. With this, they again start moving clockwise together until they reach $h_{j}$. The agents can distinguish $h_{j}$ by the home type message written there by $a_{j}$ before it was destroyed. Note that in the clockwise direction each node after $h_{j}$ up to the previous node of $v_{b}$ were marked right by $a_{j}$ before it was destroyed. So from $h_{j}$, $a_{(j+1)\pmod{3}}$ and $a_{(j+2)\pmod{3}}$ starts moving cautiously clockwise. That is, while both agents ($a_{L}$ and $a_{H}$, where $a_{L}$ and $a_{H}$ are the agent with lowest ID and highest ID among $a_{(j+1)\pmod{3}}$ and $a_{(j+2)\pmod{3}}$ respectively) are at a node $v_{0}$, $a_{L}$ moves clockwise to the next node, say $v_{1}$ while the other agent waits at $v_{0}$. If at $v_{1}$, $a_{L}$ sees the right marking, it interprets $v_{1}$ is safe. So, it comes back to $v_{0}$. At $v_{0}$, seeing that $a_{L}$ has returned, $a_{H}$ also interprets $v_{1}$ to be safe. So, in the next round both $a_{L}$ and $a_{H}$ moves to $v_{1}$ together and repeats the process from $v_{1}$ again. When $a_{L}$ reaches $v_{b}$, it sees no right marking there. $a_{L}$ if alive, interprets this by determining the current node to be Byzantine black hole. So, it starts perpetual exploration of $R$, except $v_{b}$. Otherwise, if $a_{L}$ gets destroyed at $v_{b}$, it does not return to the previous node where $a_{H}$ is waiting. Even after waiting, when $a_{H}$ sees $a_{L}$ has not returned, it interprets this incident as the next clockwise node is the Byzantine black hole and starts exploring the ring $R$ avoiding that node. Thus for this case the perpetual exploration continues.
Case-II: Let $a_{j}$ be destroyed at $v_{b}$ while it is moving counter-clockwise. In this case both the alive agents $a_{(j+1)\pmod{3}}$ and $a_{(j+2)\pmod{3}}$ find visited type message after returning to their corresponding $home$. This is because, $a_{j}$ is destroyed at $v_{b}$ after writing visited type message at $h_{(j+1)\pmod{3}}$. So, all alive agents after waiting, starts repeating the exploration procedure again. The agents first erase the whiteboard content at their corresponding $home$ and then writes the corresponding home type message before it starts moving clockwise until the end of their corresponding segment. Note that since $a_{j}$ was destroyed earlier (even before the repetition starts), $a_{(j-1)\pmod{3}}$ finds the visited type message which was written there earlier by it, is still present (which was supposed to be erased if $a_{j}$ was alive). From this information, $a_{(j-1)\pmod{3}}$ interprets that, $v_{b}$ must be in the segment adjacent to its own segment in the clockwise direction. It also interprets that, an agent must have been destroyed at $v_{b}$ while it was moving counter-clockwise. This is because, if the agent was destroyed while it was moving clockwise then it would have been detected by the other agents when they are at their $home$ (as described in Case-I), which is before the start of the next clockwise move (note that the agents have already started next clockwise move). So, this information triggers $a_{(j-1)\pmod{3}}$ to move counter-clockwise with the aim to gather with $a_{(j-2)\pmod{3}}$. Since $a_{(j-1)\pmod{3}}$ starts its move while $a_{(j-2)\pmod{3}}$ waits at $home$ and also, since the waiting time is sufficient, $a_{(j-1)\pmod{3}}$ meets $a_{(j-2)\pmod{3}}$ during the waiting period at $h_{(j-1)\pmod{3}}$. So, after they meet, $a_{(j-1)\pmod{3}}$, communicates the direction of its move to $a_{(j-2)\pmod{3}}$ on the whiteboard of $h_{(j-1)\pmod{3}}$ and they move together until they reach $h_{(j-2)\pmod{3}}(=h_{(j+1)\pmod{3}})$ together. They distinguish the node by the home type message left there by $a_{(j-2)\pmod{3}}$ before the start of moving clockwise. Note that, in the counter-clockwise direction, the nodes in $Seg(a_{j})$, starting from the next node of $h_{(j+1)\pmod{3}}$ up to the previous node of $v_{b}$ are the only nodes those were marked left by $a_{j}$ before it was destroyed. So, from $h_{(j+1)\pmod{3}}$, the alive agents $a_{(j+1)\pmod{3}}$ and $a_{(j+2)\pmod{3}}$ start moving cautiously in the counter-clockwise direction. Among $a_{(j+1)\pmod{3}}$ and $a_{(j+2)\pmod{3}}$, an agent with lowest ID is denoted by $a_{L}$ and the agent with highest ID is denoted by $a_{H}$. The cautious walk is same as described in Case-I, except for the fact that here after moving one node in the counter-clockwise direction, the agent $a_{L}$ searches for the left marking. If it finds such marking it returns to $a_{H}$ and then both moves counter-clockwise and repeats the process. On the other hand if $a_{L}$ does not find any left marking (it must be $v_{b}$) and it stays alive, $a_{L}$ moves out of that node and starts exploring $R$ avoiding that node. On the contrary, if $a_{L}$ gets destroyed then $a_{H}$ sees that $a_{L}$ has not returned while it should have. From this incident it interprets next counter-clockwise node is $v_{b}$ and it starts exploring $R$ avoiding that node.

In order to prove this theorem, we first define a cautious start node. Let $a_{i}$ be the agent destroyed at the Byzantine black hole first. We define cautious start node to be $h_{i}$, if $a_{i}$ was moving clockwise when destroyed, otherwise it is $h_{(i+1)\pmod{3}}$. We first prove that after one agent is destroyed, the remaining two agents gather at the cautious start node. This result can be found in details in Lemma 11.11 in Appendix. Note that $a_{i}$ marks each node on the arc between the cautious start node and the Byzantine black hole with either left or right markings depending on the direction it was moving before it was destroyed. We proved that the alive agent can know the direction of $a_{i}$ before it was destroyed. This can be found in details in Lemma 11.1 and Lemma 11.3 in Appendix. After the alive agents reach the cautious start node, they start moving cautiously looking for the marking based on the direction of $a_{i}$ before it was destroyed. We proved that at least an agent among the two moving cautiously will stay alive knowing the exact location of the Byzantine black hole (Lemma 11.13 in Appendix). Hence this agent can explore $R$ perpetually avoiding the Byzantine black hole. This proves Theorem 5.4.

In the following part, we give a detailed description of our algorithm PerpExplore-Coloc-Pbl. Initially, all the agents are in state Initial. In this state, an agent first declares its $Current-Node$ as $home$, after which initializes the variable $T_{time}=0$ (where, $T_{time}$ is the number of rounds passed since the agent has moved from state Initial) and gathers the ID of the remaining agents currently at $home$. Next, the agent with the lowest ID, i.e., $a_{1}$ moves to state Leader, the agent with the second lowest ID, i.e., $a_{2}$ moves to state Follower-Find, whereas the remaining agent, i.e., $a_{3}$ moves to state Backup. We now define an iteration for this algorithm. An iteration is defined to be a collection of $4n+1$ consecutive rounds starting from the latest round where all 3 agents along with 2 pebbles are at $home$ in state Initial. Note that, a new iteration fails to execute if either at least one pebble or an agent gets destroyed by the Byzantine black hole in the current iteration. More precisely, the meaning of failing an iteration implies that an agent after ending its current iteration does not again start a new iteration by moving into state Initial.

Suppose, all the 3 agents along with 2 pebbles successfully execute the $i$-th iteration and reach $home$, i.e., neither any pebble nor any agent gets destroyed by the Byzantine black hole. In this situation, according to our algorithm, $a_{1}$ being the lowest ID, follows the following sequence $SEQ1$, whereas $a_{2}$ being the second lowest ID follows $SEQ2$, and the $a_{3}$ follows the sequence $SEQ3$. The above sequences are as follows:

1. 1.

   $SEQ1$: Initial $\rightarrow$ Leader $\rightarrow$ Initial.

2. 2.

   $SEQ2$: Initial $\rightarrow$ $({Follower-SEQ})^{n}$ $\rightarrow$ Initial.

   1. (a)

      ${Follower-SEQ}$: Follower-Find $\rightarrow$ Follower-Collect $\rightarrow$ Follower-Find.

3. 3.

   $SEQ3$: Initial $\rightarrow$ Backup $\rightarrow$ Initial.

On the contrary, if the current node of $a_{1}$ is not $home$, then also it performs the following checks: first, it checks whether it is with the second lowest ID agent (i.e., $a_{2}$ in this case), and if so, then initializes $W_{time}=0$ and then moves one hop clockwise to the next node along with the pebble it is accompanying. Otherwise, if it is not with the second lowest ID agent, then wait for 3 rounds (i.e., waits when $W_{time}<4$), after which if still it is without the second lowest ID agent, then the agent moves to state Report-Leader while leaving the pebble (it is accompanying) at the current node and moving one hop to the clockwise node.

Note that until and unless there are no anomalies detected by the agent $a_{1}$, it ends an iteration, by changing to state Initial from Leader. Otherwise, if any anomaly is detected, then $a_{1}$ ends the current iteration by either changing to state Detection or Report-Leader from the state Leader, in which case, it never changes to state either Leader or Initial.

Note that, the agent only changes to state Initial only when it reaches $home$ again, which is after it performs ${Follower-SEQ}$ for $n$ times starting from $SEQ2$. If at any point, $a_{2}$ finds any irregularities, based on whether a pebble is present or not, then only it directly concludes the Byzantine black hole position. In all other cases, it follows the ${Follower-SEQ}$ sequence and changes to state Follower-Collect.