Perpetual Exploration of a Ring in Presence of Byzantine Black Hole

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 bound on the number of agents to perpetually explore $R$, reduces from 4 to 3 rendering it tight.

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.

Rest of the paper is organised as follows. Section 2 presents the model and preliminaries. In Section 3, we discuss some impossibility results. In Section 4 and 5, we propose perpetual exploration algorithms for the agents when the agents are initially co-located and scattered, respectively. Lastly, we conclude in Section 6. Due to page limitations we are omitting the detailed descriptions of the algorithms and the proofs of the theorems and lemmas. These can be found in the full version [17].

Given a ring $R$ with a Byzantine black hole node $v_b$, a set of agents, $A=\{a_1,a_2,a_3\}$ (where we assume, ID of ID of ID of $a_3$), are initially co-located at $home$. The agents have no knowledge about the position of the node $v_b$, the only set of knowledge the agents have are: the total number of nodes in the underlying topology $R$ (i.e., $n$), and also the knowledge that the initial node, i.e., $home$ is safe. So, the remaining arc of $n-1$ nodes in $R$ is a suspicious region (which we term as $S$, where the cardinality of $S$ i.e., $|S|$ denotes the length or size of the suspicious region) for each of the three agents.

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\ge 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 , 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 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.

To prove the correctness of algorithm PerpExplore-Coloc-Pbl we prove the following Theorem. Here we just present a sketch of the proof. For details see Section 9.2 in the full version [17].

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 15 in the full version [17]). 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 17 in the full version [17]). For the later case we proved that the exploration continues until another agent is destroyed by the Byzantine black hole (Remark 18 in the full version [17]). 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 19 in the full version [17]). Thus it can then perform the exploration of $R$ avoiding the Byzantine black hole. This proves Theorem 8.

Let us consider, the starting position of $a_0$ to be the first, after which the starting position of $a_1,a_2$ and $a_3$, respectively follows in clockwise order. Let $h_i$ be the starting node of an agent $a_i$ (i.e., $home$ of $a_i$), where $i\in \{0,1,2,3\}$. By $Seg(a_i)$ we define the clockwise arc starting from the node $h_i$ and ending at $h_{(i+1)(mod4)}$ (called segment of $a_i$). If no agents are destroyed by the Byzantine black hole $v_b$ then the exploration of $R$ goes as follows. Note that in this explanation, if we say $a_k$ or $h_k$, we mean $a_{k(mod4)}$ or $h_{k(mod4)}$, for some $k\ge 0$.

Agent $a_i$ moves clockwise along $Seg(a_i)$ leaving its pebble at $h_i$ until it reaches $h_{(i+1)}$ (i.e., the end of $Seg(a_i)$). An agent can distinguish the node $h_{(i+1)}$ by seeing the pebble left there by the agent $a_{(i+1)}$. When $a_i$ reaches $h_{(i+1)}$ 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)}$, 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)}$ (the pebble left by $a_{(i+1)}$) 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)}$ 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)}$ it starts moving counter-clockwise without any pebble (this case can only happen if $a_{(i+1)}$ is destroyed at the Byzantine black hole node $v_b$, while it was returning back after collecting the pebble from $h_{(i+2)}$ 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 Section 10.1 in the full version [17]). 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)}$ left by $a_{(j+1)}$ and return $h_j$. So, when $a_{(j+1)}$, returns $h_{(j+1)}$ after moving counter-clockwise along with the pebble it has collected from $h_{(j+2)}$, it finds two pebble at $h_{(j+1)}$. This is considered by $a_{(j+1)}$ 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)}$. In this scenario, $a_{(j+1)}$ waits a certain number of rounds (if needed) to ensure that every other alive agents have reached their corresponding $home$. Then $a_{(j+1)}$ 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)}$ 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)}$ first meets $a_{(j+2)}$ at $h_{(j+2)}$ while it moves clockwise after detecting anomaly. Then both of them moves together, while $a_{(j+2)}$ carries the pebble, which it was earlier carrying back to $home$. They move until they meet with $a_{(j+3)}$ at $h_{(j+3)}$. Note that at this moment 3 agents are at a node (which is $h_{(j+3)}$), with at least 3 pebbles (one carried by $a_{(j+3)}$ and two carried by $a_{(j+2)}$). 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)}$. 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)}$ was picked by no agents and thus, while $a_{(j+1)}$ returns back to $h_{(j+1)}$ 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 20 in the full version [17]) at the expense of one agent and then execute PerpExplore-Coloc-Pbl to solve the PerpExplroation-BBH problem.

To prove 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 Section 10.2 in the full version [17]). Fig. 2 illustrates the working of the algorithm PerpExplore-Scat-Pbl.

First, we proved that algorithm PerpExplore-Scat-Pbl guarantees exploration if no agents are destroyed (Corollary 24 in the full version [17]). This corollary is a direct consequence of the Lemma 23 also present in the full version [17]. 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 This can be found in Lemma 25 in the full version [17]. The rest of the proof follows from Theorem 8.

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)(mod3)}$. 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. Note that in this explanation, if we say $a_k$ or $h_k$, we mean $a_{k(mod3)}$ or $h_{k(mod3)}$, for some $k\ge 0$.

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)}$. It distinguishes $h_{(i+1)}$ by seeing the home type message left by $a_{(i+1)}$. When $a_i$ moves clockwise, it also marks each node of $Seg(a_i)$, except $h_i$ and $h_{(i+1)}$, by writing right, after erasing any previous such markings (if at all exists) at each such nodes. After $a_i$ reaches $h_{(i+1)}$ 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)}$). After this waiting, each alive agent $a_i$ write the message (visited, ID($a_i$)) at $h_{(i+1)}$ 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)}$ 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)}$). 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)}$. 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)}\}$. 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)}$ and also fails to write a visited type message there. So, when $a_{(j+1)}$ returns to its $home$ (i.e., $h_{(j+1)}$), it finds no visited type message (as it should’ve, if $a_i$ was not destroyed). $a_{(j+1)}$ 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)}$). Note that, when $a_{(j+1)}$ 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)}$ shares the information about its direction of movement in the whiteboard of $h_{(j+2)}$. 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)}$ and $a_{(j+2)}$ 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)}$ and $a_{(j+2)}$ 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)}$ and $a_{(j+2)}$ 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)}$. 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)}$ 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)}$ deduces that, $v_b$ must be in the segment adjacent to its own segment in the clockwise direction. It also deduces 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 the next clockwise move). So, this information triggers $a_{(j-1)}$ to move counter-clockwise with the aim to gather with $a_{(j-2)}$. Since $a_{(j-1)}$ starts its move while $a_{(j-2)}$ waits at $home$ and also, since the waiting time is sufficient, $a_{(j-1)}$ meets $a_{(j-2)}$ during the waiting period at $h_{(j-1)}$. So, after they meet, $a_{(j-1)}$, communicates the direction of its move to $a_{(j-2)}$ on the whiteboard of $h_{(j-1)}$ and they move together until they reach $h_{(j-2)}(=h_{(j+1)})$ together. They distinguish the node by the home type message left there by $a_{(j-2)}$ 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)}$ up to the previous node of $v_b$ are the only nodes that were marked left by $a_j$ before it was destroyed. So, from $h_{(j+1)}$, the alive agents $a_{(j+1)}$ and $a_{(j+2)}$ start moving cautiously in the counter-clockwise direction. Among $a_{(j+1)}$ and $a_{(j+2)}$, 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. If, on the contrary $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.
Sketch of Correctness: Here we give a brief glimpse on how we proved the following theorem. For details see Section 11.2 in the full version [17].

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 the cautious start node to be $h_i$ if $a_i$ was moving clockwise when destroyed, otherwise it is $h_{(i+1)}$. 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 36 in the full version [17]. 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 30 and Lemma 31 in the full version [17]. 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 (This result can be found in details in Lemma 37 in the full version [17]). Hence this agent can explore $R$ perpetually avoiding the Byzantine black hole. This proves Theorem 14.