Jadavpur University, West Bengal,
Indiapritamgoswami.math.rs@jadavpuruniversity.in[OrcidId:0000-0002-0546-3894]
Indian Institute of Technology Guwahati, Assam,
Indiaa.bhattacharya@iitg.ac.in[OrcidId:0000-0003-1517-8779] Jadavpur
University, West Bengal,
Indiarajad.math.rs@jadavpuruniversity.in[OrcidId:0009-0002-0161-5341] Indian
Institute of Technology Guwahati, Assam,
<EMAIL_ADDRESS>[100]Theory of Computation
$\rightarrow$ Distributed Algorithms

# Perpetual Exploration of a Ring in Presence of Byzantine Black Hole.

Pritam Goswami  Adri Bhattacharya  Raja Das  Partha Sarathi Mandal

###### Abstract

Perpetual exploration is a fundamental problem in the domain of mobile agents,
where an agent needs to visit each node infinitely often. This issue has
received lot of attention, mainly for ring topologies, presence of black holes
adds more complexity. A black hole can destroy any incoming agent without any
observable trace. In [2, 18], the authors considered this problem in the
context of  Periodic data retrieval. They introduced a variant of black hole
called gray hole (where the adversary chooses whether to destroy an agent or
let it pass) among others and showed that 4 asynchronous and co-located agents
are essential to solve this problem (hence perpetual exploration) in presence
of such a gray hole if each node of the ring has a whiteboard. This paper
investigates the exploration of a ring in presence of a “byzantine black
hole”. In addition to the capabilities of a gray hole, in this variant, the
adversary chooses whether to erase any previously stored information on that
node. Previously, one particular initial scenario (i.e., agents are co-
located) and one particular communication model (i.e., whiteboard) are
investigated. Now, there can be other initial scenarios where all agents may
not be co-located. Also, there are many weaker models of communications (i.e.,
Face-to-Face, Pebble) where this problem is yet to be investigated. The agents
are synchronous. The main results focus on minimizing the agent number while
ensuring that perpetual exploration is achieved even in presence of such a
node under various communication models and starting positions. Further, we
achieved a better upper and lower bound result (i.e., 3 agents) for this
problem (where the malicious node is a generalized version of a gray hole), by
trading-off scheduler capability, for co-located and in presence of a
whiteboard.

###### keywords:

Mobile Agents, Exploration, Ring, Black Hole, Byzantine Fault

##  1 Introduction

Exploring a set of nodes in a network is one of the fundamental tasks in the
domain of distributed computing by mobile agents, formulated in the year of
1951 by Shannon [20]. Now the of security of these mobile agents while
exploring these networks is one of the fundamental issues to address. Among
all the possible security threats that is addressed yet in literature, two
among them are the most prominent, i.e., the threats from a malicious agent
[17] and the threats from a malicious host [13]. In this paper, we are
interested in the latter case, where the threats are from a malicious host.
This host is a stationary node in the network, which has the ability to
destroy any incoming agents without leaving any trace of its existence. So,
first task of the mobile agents operating in the network, must be to locate
this malicious node. Note that, the most trivial optimisation parameter to
ensure while locating the black hole, is that minimum of number of agents gets
consumed or destroyed by this node. This problem of locating the black hole by
mobile agents is termed as black hole search (also termed as BHS problem)
problem. BHS problem is studied from the year of 2006, when Dobrev et al. [12]
first introduced it. After which, till date there has been many variations to
this problem, some of them are [7, 8, 11, 13, 15]. This problem has various
real life implications, such as the black hole can be a virus in the network
or it can be some kind of crash failure, such that this node resembles the
characteristic of a black hole, after the failure.

Observe that, in order to detect the black hole, there needs to be some agent
which has to visit that particular node. Further, since any agent visiting the
node gets destroyed, so there must be some communication tool, which can
render this information to other alive agents, such that at least one agent
remains alive, knowing the location of the black hole. Three such
communication tool has been predominantly used in literature: a) whiteboard
model [14], in which there is a storage capacity at each node, which an agent
can use to leave a message by reading its contents and writing some new
information, b) pebble model [16], an agent can carry a movable token from one
node to another, c) face-to-face model [10], in this case an agent can share
and communicate with another agent when they are at the same node and at the
same time. In addition to the communication tools, the initial locations of
the agents (i.e., whether the agents are initially scattered [15] or they are
co-located [10]) is also one of the important parameters, generally studied in
literature.

Further, the most studied version of black hole has fairly a basic nature,
i.e., only destroying any incoming agent. Note that, in reality black hole’s
may not be such simple, it may have many ways to disrupt the movement or harm
an agent. Considering this phenomenon, we in this paper have tried to consider
a black hole which has more capabilities other than just destroying any
incoming agent. In our case, black hole may or may not kill any incoming
agent, it may do so based on an adversarial scheduler which decides when to
destroy an incoming agent and when not to. Whenever it decides not to destroy
an agent, it simply behaves as any other node in the network, disguising it
from the rest of the nodes, creating no anomaly for the visiting agent. In
addition to this, we have also considered that the black hole has further
capabilities, it can also choose whether to destroy the message (i.e., stored
data in case of whiteboard, and placed token in case of pebble) at that node
along with the incoming agent or not. This choice is also maintained by an
adversarial scheduler. We call this kind of black hole as a byzantine black
hole.

Our aim in this paper is to solve the problem of perpetual exploration in a
network, i.e., visiting every node in the network infinitely often by the
mobile agents, while detecting the presence of this byzantine black hole.
After detection, the task of the agents must be visit the remaining nodes of
the network infinitely often, whereas avoiding this byzantine black hole node.
Previously, in [2, 18] the authors introduced this model of black hole, which
has more capabilities other than just destroying a black hole. They considered
the following black hole characteristics: a black hole can fake agents, change
the whiteboard contents, or change the ports different from the requested
ones. In those papers, their aim was to achieve perpetual exploration in a
ring (which they term as periodic data retrieval problem) by a team of
asynchronous mobile agents, which are initially co-located, under these
various black hole characteristics. In our paper, we chose one such black hole
(which has more capability than a normal black hole) and we investigated this
perpetual exploration problem in a ring, by a team of synchronous agents,
under all possible initial configurations (i.e., the agents can be co-located
or the agents can be scattered), as well as under all possible communication
tools (i.e., the agents can either communicate among themselves via
whiteboard, or using a pebble, or while they meet in a face-to-face manner).
In each case, we are able to design algorithms, which serve our purpose of
detection of this malicious node, as well as execute perpetual exploration.

###  1.1 Related Works

The black hole search (i.e., BHS) problem is a prominent sub-problem of
exploration problem, studied in 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 yet are static in nature. Recently, there has been a
lot of interest on 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., colocated [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 these 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 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 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 as a byzantine black hole. In the following part, we discuss the results
we have obtained.

Our Contribution: We, in this paper, investigate the perpetual exploration
problem, by a team of synchronous mobile agents, of a ring $R$ of size $n$, in
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 Face-to-Face model of communication we obtain that
$\lceil\log(n-1)\rceil+3$ agents are sufficient to perpetually explore $R$.
B: For Pebble model of communication, we obtain that 3 agents are necessary
and sufficient to perpetually explore $R$.
C: For Whiteboard model as well, we achieve the same lower and upper bounds as
mentioned in B. This result shows that, by weakening the scheduler from
asynchronous (as assumed in [2]) to synchronous, the tight bound on number of
agents in order 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 perpetually explore $R$.
E: For Whiteboard model of communication, we obtain an improved bound of 3
agents (in comparison to D), which is necessary and sufficient to perpetually
explore the ring $R$.
In the following table, we have summarized the results.

|  | Whiteboard | Pebble | Face-to-Face
---|---|---|---|---
Co-located | Upper Bound | 3 | 3 | $\lceil\log(n-1)\rceil+3$
Lower Bound | 3 | 3 | —
Scattered | Upper Bound | 3 | 4 | —
Lower Bound | 3 | 4 | Non-Constant [9]
Table 1: Table of results

##  2 Model and Preliminaries

In this paper , the considered underlying topology of the network is an
oriented ring $R=\\{v_{0},v_{1},\dots v_{n-1}\\}$. Each node $v_{i}$ (where
$i\in\\{0,1,\dots,n-1$}) is unlabeled and has two ports connecting
$v_{(i-1)\bmod{n}}$ and $v_{(i+1)\bmod{n}}$ labeled left and right
consistently. A set $A=\\{a_{0},a_{1},\dots a_{k-1}\\}$ of $k$ agents operate
in $R$. We consider two types initial position for the set $A$ of agents. In
the first type we consider, each agent in $A$ is co-located at a node, which
we term as $home$. In the second type we consider, the agents can start from
several distinct nodes, which we term as scattered initial position. Each
agent has the knowledge of the underlying topology $R$ and has some
computational capabilities, thus it requires $\mathcal{O}(\log n)$ bits of
internal memory. The agents have unique IDs of size $\lceil\log k\rceil$ bits
taken from the set $[1,k]$, which are perceived by other agents when they are
co-located. The agents are autonomous and they execute same set of rules
(i.e., they execute the same algorithm).

We consider three types of communication that the agents have, in order to
communicate with other agents. These models of communication are as follows:

  * •

Face-to-Face: In this model of communication, an agent can communicate with
another agent when they are co-located.

  * •

Pebble: In this model, the agents are equipped with a movable token (also
termed as pebble), which signifies a single bit of information, the agents can
use this pebble in order to communicate with other agents.

  * •

Whiteboard: In this case, each node of $R$ contains $\mathcal{O}(\log k)$ bits
of memory, which can be used to store and maintain information. Any agent can
read the existing information or write any new information at the whiteboard
of its current node. Note that, fair mutual exclusion is maintained, i.e.,
concurrent access of the whiteboard data is not permitted.

The agents operate in synchronous rounds and in each round every agent becomes
active and takes a local snapshot of its surroundings. For an agent at a node
$v$ in some round $r$, the snapshot contains two ports incident to $v$,
already stored data’s on the memory of $v$ (if any, only in case of whiteboard
model of communication), number of pebbles located at $v$ (if any, only in
case of pebble model of communication), contents from its own local memory and
IDs of other agents on $v$. Based on this snapshot an agent executes some
action. This actions includes a communication step and a move step. In a
communication step an agent can communicate implicitly or explicitly with
other agents according to the communication models discussed above. In the
move step the agent can move to a neighbour node by following a port incident
to $v$. Thus if an agent at node $v$ in round $r$, decides to move during the
move step, at round $r+1$ it resides on a neighbour node of $v$. All these
actions are atomic, so an agent cannot distinguish another agent concurrently
passing through the same edge, instead it can only interact with another agent
(based on its communication model) only when it reaches another node.

A black hole is a stationary malicious node in an underlying graph, which has
the ability to destroy any visiting agent, without leaving any trace of its
existence. In this paper we have considered one unique node of $R$ to be a
black hole. Further, the black hole nature of the node is controlled by an
adversary. We term this kind of node as Byzantine Black Hole, which is defined
as follows.

######  Definition 2.1 (Byzantine Black Hole).

Let $G$ be an underlying graph of a network with agents. A node $u$ of $G$ is
called a Byzantine black hole if sometimes it behaves as a black hole,
whereas, in rest of the time it behaves as a normal node. Moreover, this
transition between the black hole nature and normal nature of the node is
controlled by the adversary.

We, in this paper, have assumed that the underlying graph contains a single
byzantine black hole, whereas the other nodes are normal nodes, and they are
termed as safe nodes. Note that, the starting positions of each agent must be
a safe node. Here, we assume that, if the adversary decides to activate the
black hole nature of the byzantine black hole node, then it does so at the
beginning of its corresponding round, and the node retains that nature until
the end of this current round. Furthermore, we have considered that our
byzantine black hole has the ability to always destroy any incoming agent,
during its black hole nature. In addition it also has the ability to choose
whether to destroy any information present on that node during the black hole
nature of that node.

So, our aim in this paper, is to perpetually explore the ring $R$, with
minimum number of agents. Next, we formally define our problem.

######  Definition 2.2 (PerpExploration-BBH).

Given a ring network $R$ with $n$ nodes, where one node ($v_{b}$) is a
Byzantine black hole, and with a set of agents $A$ positioned on R, the
PerpExploration-BBH asks the agents in $A$ to move such a way that, each node
of $R$ except $v_{b}$ is visited by at least one agent infinitely often.

##  3 Impossibility Results

In the first result we prove that two agents can not solve PerpExploration-BBH
in the strongest communication model of whiteboard.

######  Theorem 3.1.

A set of two synchronous agents in a ring $R$ of size $n$ cannot solve
PerpExploration-BBH, even in presence of whiteboard if number of possible
consecutive black hole positions is greater or equals to 3.

######  Proof 3.2.

Let $v_{1},v_{2}$ and $v_{3}$ be three possible consecutive black hole
positions in a ring $R$. Let two agents $a_{1}$ and $a_{2}$ are sufficient to
solve the PerpExploration-BBH problem on $R$. Thus there exists an algorithm
$\mathcal{A}$ such that $a_{1}$ and $a_{2}$ can solve PerpExploration-BBH by
executing $\mathcal{A}$. Without loss of generality let $a_{1}$ explores
$v_{2}$ and it moves to $v_{2}$ for the first time at round $t$ from vertex
$v_{1}$. Then $a_{1}$ must have been at the vertex $v_{1}$ at round $t-1$. Let
us take two copies $R_{1}$ and $R_{2}$ of the same ring $R$. In $R_{1}$,
$v_{1}$ is the black hole and in $R_{2}$, $v_{2}$ is the black hole. Let the
adversary in $R_{1}$ destroys $a_{1}$ at round $t-1$ and in $R_{2}$ destroys
$a_{1}$ in round $t$. We claim that at round $t$ and $t-1$, $a_{2}$ can not be
on either of $v_{1}$ or $v_{2}$. Note that at $t$-th round $a_{2}$ can not be
on $v_{2}$ otherwise, both $a_{1}$ and $a_{2}$ gets destroyed at the same
round and no other agent is left to explore further. Similarly at round $t-1$
$a_{2}$ can not be on $v_{1}$. Now consider the case when at $t-$ th round
$a_{2}$ is at $v_{1}$. Since at round $t-1$, $a_{2}$ can not be on $v_{2}$
there can be two cases either at round $t-1$, $a_{2}$ was in $u_{0}$ ($u_{0}$
is another adjacent node of $v_{1}$ except $v_{2}$) or was in $v_{1}$ itself.
We first argue that at round $t-1$, $a_{2}$ can not be at $u_{0}$. Otherwise,
since the whiteboard content at nodes except at $v_{1}$ and $v_{2}$ are same
in $R_{1}$ and $R_{2}$ at round $t$ (due to same execution by $a_{1}$ and
$a_{2}$ upto round $t-1$ and at round $t$ for $a_{2}$ in both $R_{1}$ and
$R_{2}$). Now since at round $t$ all previous datas on whiteboard except
$v_{1}$ and $v_{2}$ does not help $a_{2}$ to distinguish between $R_{1}$ and
$R_{2}$, the problem now can be thought of solving PerpExploration-BBH with
one agent where number of possible consecutive black hole position is atleast
two. Now this is impossible to solve. So, at $t-1$-th round $a_{2}$ can not be
on $u_{0}$ We now only have to prove that $a_{2}$ can not be at $v_{2}$ during
round $t-1$. Let in $R_{2}$, adversary activates the black hole at $v_{2}$ at
round $t-1$ which destroys $a_{2}$ at round $t-1$. Now since the effect of
this destruction of agent $a_{2}$ does not effect the inputs of $a_{1}$ at
round $t-1$ on $v_{1}$, it move to $v_{2}$ at round $t$ where the black hole
is activated again by adversary destroying $a_{1}$ too. Thus $a_{2}$ must
remain outside of $v_{1}$ and $v_{2}$ during round $t$ and $t-1$ while
executing $\mathcal{A}$. So, at round $t$ since all whiteboard content are
same for $R_{1}$ and $R_{2}$ (except for nodes $v_{1}$ and $v_{2}$ whose
content only differs after round $t-2$ for $R_{1}$ and $R_{2}$ which can not
be known by $a_{2}$ as it was not there during that rounds), they can not help
$a_{2}$ to distinguish between $R_{1}$ and $R_{2}$. So the problem now can be
thought of as solving PerpExploration-BBH with one agent where number of
possible consecutive black hole position is at least 2. And this is
impossible. So there doesn’t exist any algorithm that solves PerpExploration-
BBH with two agents on a Ring $R$ where number of possible consecutive
positions of black hole is at least 3.

Note that since the $n$ can be sufficiently large so that initially number of
possible consecutive black hole positions is atleast three we have the
following corollary.

######  Corollary 3.3.

It is impossible to solve PerpExploration-BBH on a ring $R$ with $n$ nodes
using two synchronous agents even if the nodes are equipped with whiteboards.

######  Corollary 3.4.

A set of three synchronous agents are required to solve the PerpExploration-
BBH on a ring $R$ with $n$ nodes, where each node has a whiteboard.

######  Corollary 3.5.

A set of two agents, each equipped with $O(\log n)$ pebbles can not solve the
PerpExploration-BBH problem on a ring $R$ with $n$ nodes.

Now the following theorem improves the lower bound for the case when agents
are scattered and each agent is equipped with a pebble, whereas there is no
whiteboard present at the nodes of $R$. The theorem is as follows.

######  Theorem 3.6.

A set of 3 scattered agents, each equipped with a pebble can not solve the
PerpExploration-BBH problem on a ring $R$ with $n$ nodes.

######  Proof 3.7.

Let $a_{1},a_{2}$ and $a_{3}$ be three agents equipped with a pebble each. The
agents are placed on three nodes $h_{1},h_{2}$ and $h_{3}$ initially in such a
way that distance between $h_{i}$ and $h_{j}$ is same for all
$i,j\in\\{1,2,3\\}$, where we consider $h_{j}$ to be the nearest node of
$h_{i}$ in the clockwise direction. Without loss of generality let this
distances be sufficiently large. Further, let there exists an algorithm
$\mathcal{A}$ that solves the PerpExploration-BBH problem in this setting. Let
without loss of generality $a_{1}$ be the first agent to explore the third
node from its corresponding starting position (i.e., $h_{1}$) in any of the
clockwise or counter-clockwise direction, when each agent starts executing the
algorithm $\mathcal{A}$. Suppose by following $\mathcal{A}$, $a_{1}$ can visit
the third node in clockwise direction (without loss of generality) first at a
round say $t>0$. Let $v_{1},v_{2}$ and $v_{3}$ be those set of three nodes
from $h_{1}$ in the clockwise direction. Let $C_{1}$,$C_{2}$ and $C_{3}$ be
three scenarios where in $C_{i}$, $v_{i}$ is the black hole. We claim that,
$a_{1}$ can not carry its pebble during any execution of $\mathcal{A}$.
Otherwise in scenario $C_{1}$, it would be consumed along with its pebble, and
since the distances between two consecutive $h_{i}$ are sufficiently large,
hence other agents would have no idea that an agent is already consumed. This
is equivalent to solving the PerpExploration-BBH with two agents having a
pebble each and as $n$ is sufficiently large this is impossible due to
Corollary 3.5. Now suppose adversary chooses to activate the black hole
whenever $a_{1}$ reaches there for the first time. In this case for all
$C_{1}$, $C_{2}$ and $C_{3}$, at round $t$, agents $a_{2}$ and $a_{3}$ has no
idea about where $a_{1}$ is consumed even if it knows that $a_{1}$ is
consumed, as the distances between two consecutive $h_{i}$ are sufficiently
large so their exploration region does not intersects till round $t$ and
timeout (or,waiting for other agent) strategy do not work as for all $C_{i}$
an agent can get same timeout output. Also for all $C_{i}$s the position of
the pebbles and alive agents will be same at round $t$. Now for the alive
agents, the number of nodes for possible position of the black hole must be
greater than or equal to 3 at round $t$. So the situation at round $t$ is
similar to the problem of solving PerpExploration-BBH on a ring $R$ with two
agents having a total of 3 pebbles where the number of possible consecutive
positions of black hole is greater or equal to 3. Since we have assumed
$\mathcal{A}$ solves the problem thus, $\mathcal{A}$ can also solve the
problem of PerpExploration-BBH with two agents where number of possible
positions of black hole is greater or equal to 3. But due to Theorem 3.1 it is
impossible. Hence there can never exists any algorithm that solves
PerpExploration-BBH with three scattered agents each of which are equipped
with a pebble.

######  Corollary 3.8.

A set of four scattered agents each with a pebble, are required to solve
PerpExploration-BBH on a ring $R$ with $n$ nodes.

##  4 Co-located Agents

###  4.1 Communication: Face-to-Face

In this section, we discuss the PerpExploration-BBH problem, under the
conditions, where the agents are initially located at a safe node $home$, and
they can only communicate with another agent whenever they are at the same
node at the same round. Here considering this scenario we provide an algorithm
PerpExplore-F2F (Algorithm 1) to solve the PerpExploration-BBH problem with
$\lceil\log(n-1)\rceil+3$ agents.
Description of PerpExplore-F2F: Given a ring $R$ with a byzantine black hole
node $v_{b}$, a set of agents $A=\\{a_{1},a_{2},\dots,a_{k}\\}$, where
$k=\lceil\log(n-1)\rceil+3$, are initially co-located at a safe node, which we
term as $home$. Note that, the agents have no knowledge about the position of
$v_{b}$. The agents have the knowledge of $n$ (which is the total number of
nodes in $R$), whereas they know that $home$ is safe, as it is the initial
position of the set of agents, $A$. Moreover, they have no idea about the
remaining $n-1$ nodes of $R$, as $v_{b}$ can be any node among these $n-1$
nodes. We call this arc containing these $n-1$ nodes as the suspicious region,
and it is denoted by $S$ with cardinality $|S|$.

The main idea of the PerpExplore-F2F algorithm is from the $home$ only two
agents, say $a_{1}$ and $a_{2}$ starts exploring the ring perpetually. The
algorithm goes like this, one agent (preferably the agent with lowest Id,
among the set of agents which are yet to be consumed by $v_{b}$) moves
clockwise until it reaches the ’middle node’ of the suspicious region $S$,
while the other agent (preferably the agent with second lowest Id, among the
set of agents which have not been consumed by $v_{b}$) also performs the same
movement, but along counter-clockwise direction, after which they return to
the $home$ and this process perpetually continues. Now while executing this
movement by these two agents, there can be two possible scenarios, the moment
at least one agent gets destroyed by the byzantine black hole, $v_{b}$.
Firstly, both the agents can get destroyed (this happens only when $v_{b}$ is
the middle node of $S$), whereas secondly, only one agent is destroyed while
the other agent following its usual course of algorithm, returns to $home$.
For the initial case, the remaining agents at home can uniquely determines the
byzantine black hole, $v_{b}$, as the middle node of $S$ and consecutively
starts exploring the ring while avoiding $v_{b}$. For the latter case, the
agents at the $home$ along with the agent that has returned to $home$,
eventually gets to know that, the other agent has not returned and which in
turn concludes that the arc, along which the missing agent was exploring
contains the node $v_{b}$. This way our algorithm guarantees that, in the
worst case, the size of the suspicious region decreases by a factor of at
least half of the previous size, in the expense of one agent. So this implies,
when $\lceil\log n\rceil$ agents are destroyed in $v_{b}$, the size of the
suspicious region becomes exactly 1 (where this node in the suspicious region
is nothing but $v_{b}$). In this case the remaining alive agent can determine
the exact position of $v_{b}$ and hence, can perpetually explore the ring $R$
avoiding $v_{b}$.

Next we will give a brief description of our algorithm PerpExplore-F2F. The
algorithm works as follows, initially each agent at $home$ starts from state
Initial0. In this state, an agent initializes the following variables:
$S_{lft}$ to 1, $S_{rgt}$ to $n-1$,where $S_{lft}$ and $S_{rgt}$ denotes the
distance to the left and the right end nodes of the suspicious region $S$ from
the $home$, in the clockwise direction. Also in this state an agent declares
its current node as the $home$. Note that, the agents stay at this state only
for one round at the beginning of the execution of our algorithm, after which
they enter the state Initial1. Now, after an agent enters the state Initial1,
it calculates $|S|$ (where $|S|=|S_{rgt}-S_{lft}+1|$), initializes $Tnodes$ to
0 (where $Tnodes$ is the distance an agent traverses in order to reach its
destination node). Next, it checks the variables $|S|$ and $k$ (where $k$ is
the number of agents present at the $Current-Node$, i.e., $home$). If it finds
$|S|=2$ and $k=2$, i.e., the length of the suspicious region is 2 and the
total number of agents present at $home$ is also 2, then both the agents
execute the sequence $SEQ0$ of states, where $SEQ0$ is defined as follows:

$SEQ0):\leavevmode\nobreak\
\textbf{Initial1}\rightarrow\textbf{Detection}\rightarrow\textbf{Initial1}$

According to this sequence, the agent moves in to state Detection (after
satisfying both the conditions $|S|=2$ and $k=2$ in state Initial1). In this
state, the lowest Id agent is instructed to move clockwise and reach its
destination position $S_{lft}$, whereas, the other agent reaches its
destination $S_{rgt}$ along a counter-clockwise direction, while after each
movement updating $Tnodes=Tnodes+1$. Now, after reaching their respective
positions, the agents return back to $home$ along the same path in which they
reached their destination nodes, again incrementing $Tnodes$ by 1 after each
move. So, the total number of rounds required by the agent, starting from
Initial1 in order to reach $home$ is $Tnodes+1$. After reaching $home$, they
are further instructed to wait for $2n-Tnodes+2$ rounds. In the following
round it again checks whether, $\\#Agent$ at $home$ is still $k$ i.e., 2, if
so then again it changes to state Initial1, and the sequence $SEQ0$ is
executed repeatedly. Otherwise, if the current agent is of lowest Id then
declares the byzantine black hole node is at the location of $S_{rgt}$,
otherwise if the current agent is not of lowest Id, then it declares that this
byzantine black hole node is at $S_{lft}$. Irrespective of which, they
continue performing perpetual exploration of $R$, by avoiding this black hole
node. Hence, the total number of rounds required to complete the execution of
this sequence is $2n+4$.

On the contrary, if either $|S|\neq 2$ or $k\neq 2$. Note that, if $|S|=1$,
then this node is nothing but the byzantine black hole node, and the remaining
agents (such agent always exists, refer Lemma 4.11) detect this, and further
continue perpetual exploration, avoiding this node. Otherwise, for $|S|\geq 2$
and $k\geq 3$ in state Initial1, the agents update the following variables:
$k$ to $k-2$ (where $k-2$ is the number of agent which enters the next state
Stagnant), locates the next destination node, where it calculates the variable
$Dest=S_{lft}+\lceil\frac{|S|}{2}\rceil-1$, which is the clockwise distance of
the destination node from $home$, $W_{time}$ to $0$ (where $W_{time}$
signifies the waiting time at destination node). Agents in Initial1 state can
change their state in to one of the following three states: Forward-Left,
Forward-Right and Stagnant. An agent moves in to Forward-Left, if it is the
agent with lowest Id among all the agents present at $home$, whereas an agent
moves in to Forward-Right, if the agent is having second lowest Id among all
the agents present at $home$. Lastly, an agent enters the state Stagnant, if
it is neither with lowest Id nor with second lowest Id.

According to the state an agent enters after Initial1, we define three
sequence of states $SEQ1$, $SEQ2$ and $SEQ3$, respectively, which an agent can
follow in the exact order after Initial1 state, based on whether the agent
enters Forward-Left or Forward-Right or Stagnant. If the agent enters the
state Forward-Left then it starts following $SEQ1$, or if it enters the state
Forward-Right then it follows $SEQ2$ or if it enters Stagnant state then it
follows $SEQ3$, respectively. Note that, in each sequence of states the agent
eventually reaches back to Initial1, if not it is destroyed at the node
$v_{b}$, while performing any of the states: Forward-Left (resp, Forward-
Right) or Wait-Left (resp, Wait-Right) or Backtrack-Left (resp, Backtrack-
Right). Also note that if one agent stated executing sequence $SEQ1$, then
there must be another agent that executes sequence $SEQ2$ and the other agents
execute the sequence $SEQ3$ starting from the same round (refer Line 10-17 of
Algorithm 1). We define $SEQ1$, $SEQ2$ and $SEQ3$ as follows:
$SEQ1)\leavevmode\nobreak\ \textbf{Initial1}\rightarrow\textbf{Forward-
Left}\rightarrow\textbf{Wait-Left}\rightarrow$ $\textbf{Backtrack-
Left}\rightarrow\textbf{Wait1-Left}$ $\rightarrow\textbf{Initial1}$
$SEQ2)\leavevmode\nobreak\ \textbf{Initial1}\rightarrow\textbf{Forward-
Right}\rightarrow\textbf{Wait-Right}\rightarrow$ $\textbf{Bactrack-
Right}\rightarrow\textbf{Wait1-Right}\rightarrow\textbf{Initial1}$
$SEQ3)\leavevmode\nobreak\
\textbf{Initial1}\rightarrow\textbf{Stagnant}\rightarrow\textbf{Initial1}$.
Our algorithm guarantees that, each agent starting from Initial1 again enters
the state Initial1 at the same round, after following any of these three
sequences.

######  Definition 4.1 (Iteration).

We define an iteration of our algorithm as the number of rounds required to
execute any one of these sequences (i.e., $SEQ0$, $SEQ1$, $SEQ2$ and $SEQ3$)
by an agent.

Note that, each iteration has exactly $2n+4$ rounds. Each agent performs these
iterations until this byzantine black hole is detected, after which, they
explore the ring $R$ perpetually just by avoiding this black hole node.

Next, we describe how the agents execute the sequences in order to perform the
PerpExplore-F2F algorithm in one iteration.

1 Input: $n,k$;

2 States: {Initial0, Initial1, Stagnant, Forward-Left, Forward-Right,
Backtrack-Left, Backtrack-Right, Wait-Left, Wait-Right, Wait1-Left,
Wait1-Right}

3

4In State Initial0:

5 $S_{lft}=$ 1, $S_{rgt}=$ $n-1$;

6

7Declare $Current-Node$ as $home$ and update to state Initial1.

8

9In State Initial1:

10 $|S|=|S_{rgt}-S_{lft}+1|$, $Tnodes=0$;

11 if  _$S_{lft}\neq S_{rgt}$_ then

12 if  _$|S|=2\wedge k=2$_ then

13 Move to state Detection.

14

15 else

16 $k=k-2$, $Dest=S_{lft}+\lceil\frac{|S|}{2}\rceil-1$, $W_{time}=0$;

17 if  _$LowestID$_ then

18 Update state to Forward-Left.;

19

20 else if  _$SecondLowestID$_ then

21 Update to state Forward-Right.;

22

23 else

24 Move to state Stagnant.;

25

26

27

28else

29 Declare $S_{lft}$ as the byzantine black hole location and continue
exploration avoiding that node.

30

31

32In State Stagnant:

33 Wait at the $Current-Node$ for $2n+2$ rounds.

34 if  _$\\#Agent=k$_ then

35 Declare $Dest$ is the byzantine black hole location and continue
exploration avoiding that node.

36

37 else if  _$\\#Agent=k+1$_ then

38 Update $k=k+1$ and collect the updated $S_{lft}$, $S_{rgt}$ and update
accordingly.

39 Move to state Initial1.

40

41 else

42 Update $k=k+2$ and move to state Initial1.

43

44

45In State Forward-Left: Explore$(left\wedge Tnodes++\leavevmode\nobreak\
|\leavevmode\nobreak\ Tnodes=Dest\leavevmode\nobreak\ :\leavevmode\nobreak\
\textbf{Wait-Left})$

46 In State Forward-Right: Explore$(right\wedge Tnodes++\leavevmode\nobreak\
|\leavevmode\nobreak\ Tnodes=n-Dest\leavevmode\nobreak\ :\leavevmode\nobreak\
\textbf{Wait-Right})$

47

48In State Wait-Left:

49

50if  _$W_{time} <n-Tnodes$ _ then

51 $W_{time}++$

52else

53 Enter state Backtrack-Left and move $right$

54

55

56In State Wait-Right:

57

58if  _ $W_{time}<n-Tnodes$ _ then

59 $W_{time}++$

60else

61 Enter state Backtrack-Right and move $left$

62

63

Algorithm 1 PerpExplore-F2F

Execution of the sequence $SEQ1$: As discussed earlier, if the agent is of
lowest Id in the in the state Initial1, then it is instructed to change their
state to Forward-Left. In state Forward-Left, an agent reaches the destination
node, which is $Dest$ distance away from $home$, along the clockwise
direction, while after each move incrementing the variable $Tnodes$ by 1. Now,
the moment it reaches the destination node, it is further instructed to change
its state to Wait-Left. Note that, an agent stays in Forward-Left state for
exactly $Tnodes+1$ rounds while following the sequence $SEQ1$ in an iteration.
After changing its state to Wait-Left, the agent waits at the destination node
for $n-Tnodes-1$ rounds, after which it is again instructed to move in to
another state, which is Backtrack-Left while already starting to move one hop
along counter-clockwise direction. Observe that an agent spends exactly
$n-Tnodes$ round in state Wait-Left while executing $SEQ1$ in an iteration.
Next in the state Backtrack-Left, an agent immediately starts moving along
counter-clockwise direction, until the agent reaches the $home$ node, which is
$Tnodes-1$ distance apart from its current node. While it reaches $home$, it
again changes to state Wait1-Left. An agent stays at the Backtrack-Left state
for exactly $Tnodes$ rounds. State Wait1-Left, instructs the agent to wait at
the current node, i.e., $home$ for $n-Tnodes$ many rounds. This waiting time
is enough for another agent that started executing sequence $SEQ2$ to return
back to the $home$ if not destroyed by the byzantine black hole. After
waiting, the agent checks the number of agent present at the current node. If
$\\#Agent$ increases to $k+1$ (where $k$ agents are in state Stagnant), then
in that case, it updates $k$ to $k+1$ and understands that the second lowest
Id agent has not returned to $home$. In this situation, the only possibility
of the other agent not returning back is that it has entered the black hole,
along its traversal. In this situation it updates $S_{lft}$ to the destination
node, which is $Dest$ distance apart from $home$ (i.e., basically the
suspicious region becomes half, because initially $S_{lft}$ was 1, whereas now
it is updated to $Dest$), and also communicates this information to the
remaining $k-1$ agents at $home$, and directly moves into state Initial1.

42

43In State Bactrack-Left: Explore($right\wedge d++\leavevmode\nobreak\
|\leavevmode\nobreak\ d-Tnodes-1=0\leavevmode\nobreak\ :\leavevmode\nobreak\
\textbf{Wait1-Left})$

44 In State Backtrack-Right: Explore($left\wedge d++\leavevmode\nobreak\
|\leavevmode\nobreak\ d-Tnodes-1=0\leavevmode\nobreak\ :\leavevmode\nobreak\
\textbf{Wait1-Right})$

45 In State Wait1-Left:

46 Update $d=0$ and wait at the $Current-Node$ for $n-Tnodes$ rounds.

47 if  _$\\#Agent=k+1$_ then

48 Update $k=k+1$ and $S_{lft}=Dest$ and communicate $S_{lft}$ to remaining
agents at $Current-Node$.

49 In the next round move to state Initial1.

50

51else

52 Update $k=k+2$.

53 In the next round move to state Initial1.

54

55

56In State Wait1-Right:

57 Update $d=0$ and wait at the $Current-Node$ for $n-Tnodes$ rounds.

58 if  _$\\#Agent=k+1$_ then

59 Update $k=k+1$ and $S_{rgt}=Dest$ and communicate $S_{rgt}$ to remaining
agents at $Current-Node$.

60 In the next round move to state Initial1.

61

62else

63 Update $k=k+2$.

64 In the next round move to state Initial1.

65

66

67In State Detection:

68 If lowest Id then move to $S_{lft}$ clockwise, otherwise move to $S_{rgt}$
counter-clockwise, and after each move, update $Tnodes=Tnodes+1$.

69 Return back to $home$ and again update $Tnodes=Tnodes+1$ after each move.

70 if  _$Current-Node$ is $home$_ then

71 Wait at $home$ for $2n-Tnodes+2$ rounds.

72 if  _$\\#Agent=k$_ then

73 Move to state Initial1.

74

75 else

76 If lowest Id then declare byzantine black hole is $S_{rgt}$, otherwise
declare byzantine black hole is $S_{lft}$, and then continue exploration
avoiding this node.

77

78

79

On the other hand, if $\\#Agent$ at $home$ increases from $k$ to $k+2$ (i.e.,
both lowest Id and second lowest Id has returned back to $home$) then the
agent simply waits for one round, after which it directly moves to state
Initial1. Here note that an agent stays in the state Wait1-Left for
$n-Tnodes+2$ rounds. Hence for an agent executing sequence $SEQ1$, the length
of an iteration is $2n+4$.

Execution of the sequence $SEQ2$. This execution if followed by the agent,
which in state Initial1 has the second lowest Id. In this sequence, the agent
from Initial1 moves to state Forward-Right. The state Forward-Right is exactly
the same as the state Forward-Left which has been discussed above, the only
difference is that the agent moves along a counter-clockwise direction,
instead of clockwise direction. After this state, the agent moves to state
Wait-Right, in this state again similar to the earlier state Wait-Left, the
agent waits for $n-Tnodes-1$ many rounds at the destination node. After which
it directly moves along clockwise direction for one hop and moves to state
Backtrack-Right. This state resembles Backtrack-Left, instead the fact that in
this state the agent moves along clockwise direction for $Tnodes-1$ distance,
in which case it reaches $home$. After reaching $home$, it again waits for
$n-Tnodes$ rounds while in state Wait1-Right, and after which performs similar
checks as discussed earlier in Wait1-Left, but here, if after the waiting
period, the total number of agents at $home$ is $k+1$ (where $k$ many agents
are in state Stagnant), it similarly modifies the suspicious region by
updating $S_{rgt}$ to $Dest$ (while earlier $S_{lft}$ was updated to $Dest$ in
state Wait1-Left). Lastly, it ends this sequence $SEQ2$ by moving in to state
Initial1 again. Similar to the length of an iteration for an agent executing
$SEQ1$, the length of an iteration for any agent executing $SEQ2$ is again
$2n+4$.

Execution of the sequence $SEQ3$. This execution is followed by the agent,
which in state Initial1 finds that it is neither of lowest Id nor of second
lowest Id. In this state, the agent is instructed to move to state Stagnant.
While in state Stagnant, it waits for $2n+2$ rounds at $home$, after which in
$(2n+3)$-th round it checks the number of agent present at $home$. If
$\\#$Agent is $k$ (i.e., only the agents which moved to state Stagnant), then
the agent understands that the lowest Id agent (which started sequence $SEQ1$)
and second lowest Id agent (which started sequence $SEQ2$), both has entered
the black hole, and since $R$ has only one black hole node, so this scenario
of both agents entering the black hole can only occur when the node is common
to both of these agents. This common node is nothing but the destination node,
hence if this scenario happens, then the agent in state Stagnant, concludes
that the black hole is none other than the destination node, and continues
perpetual exploration avoiding this node. On the contrary, if $\\#Agent$ is
$k+1$ (i.e., one among the agents executing $SEQ1$ and $SEQ2$ has returned,
whereas the other agent has entered the black hole). In this scenario, updates
either $S_{lft}$ or $S_{rgt}$ (based on the fact, whether the agent executing
$SEQ1$ or the agent executing $SEQ2$ has returned), and then moves to state
Initial1 while updating $k$ to $k+1$, ending sequence $SEQ3$. On the other
hand, if both the agents executing $SEQ1$ and $SEQ2$ return to $home$ (i.e.,
$\\#$Agent is $k+2$), then the agents in state Stagnant simply moves to state
Initial1 while updating $k$ to $k+2$, and ending the sequence $SEQ3$. Note
that here also, the iteration is of length $2n+4$ rounds, which leads to the
following observation.

For any $i$ ($i>0$), the $i$-th iteration for each of the $k$ alive agents,
starts at the same round and at the same node, i.e., $home$.

For any $i$ ($i>0$), each agent moves to the state Initial1 at the end of this
$i$-th iteration.

If $|S|=2$ and $k=2$, then both these agents follow the sequence $SEQ0$,
whereas, if $|S|\geq 2$ and $k\geq 3$, then one agent follows $SEQ1$, another
agent follows $SEQ2$, whereas the remaining agents follow the sequence $SEQ3$.
That is,during an iteration if an agent follows $SEQ0$ then no agent follows
$SEQ1$, $SEQ2$ or $SEQ3$ in that iteration, and vice-versa.

####  4.1.1 Correctness and Complexity

In this section we give the correctness and complexity analysis of our
algorithm PerpExplore-F2F.

######  Lemma 4.2.

During any iteration, if exactly one agent gets destroyed by the byzantine
black hole, then at the end of this iteration, the length of the suspicious
region becomes at most $\lceil\frac{|S|}{2}\rceil+1$, where $|S|\geq 2$ is the
length of the suspicious region at the start of this iteration.

######  Proof 4.3.

Let us consider at the $i$-th iteration of our Algorithm 1, the suspicious
region be $S$ (where, $|S|>1$), so the agent starts from the state Initial1,
and can encounter one of the following scenarios: first, $|S|=2$ (i.e.,
$S=\\{S_{lft},S_{rgt}\\}$) and $k=2$, second, $|S|\geq 2$ and $k>2$ (refer
line 8 of Algorithm 1).

If the first scenario is satisfied, then both the agents execute the sequence
$SEQ0$ (refer description of PerpExplore-F2F), in which they perpetually visit
the nodes $S_{lft}$ and $S_{rgt}$, respectively and return back to $home$,
until one of these agent fails to return $home$, i.e., enters the byzantine
black hole (refer state Detection in Algorithm 1). So, while the other agent
returns $home$ (which was visiting $S_{rgt}$, without loss of generality), it
is instructed to wait for $2n-Tnodes+2$ rounds (refer line 63 of Algorithm 1).
After waiting, it finds that the agent visiting $S_{lft}$ is yet to return
$home$, then this phenomenon helps the alive agent conclude that the agent
visiting $S_{lft}$ must have entered the black hole (because $2n-Tnodes+2$
rounds is sufficient number of rounds for any agent visiting the node
$S_{lft}$ to return back to $home$, if not consumed by the black hole), which
is none other than the node $S_{lft}$ (as it is the only node in the
suspicious region that this agent visits). Hence, in this case the black hole
node is detected and also $|S|$ becomes 1 at the end of $i$-th iteration,
which satisfies our claim.

On the otherhand, if $|S|\geq 2$ and $k>3$, the agents are either following
$SEQ1$ or $SEQ2$ or $SEQ3$, among them exactly one agent follows $SEQ1$ (say,
$a_{1}$), exactly one agent follows $SEQ2$ (say, $a_{2}$), whereas the rest of
the agent follows $SEQ3$ (where these agents stay at $home$ during this
iteration, refer the description of execution of $SEQ3$). This means that the
agent which can be destroyed by the black hole can be either $a_{1}$ or
$a_{2}$ (as $home$ is always a safe node). If $a_{1}$ is destroyed, then
$a_{2}$ during this iteration, after returning back to $home$ (while in state
Backtrack-Right), waits at $home$ for $n-Tnodes$ many rounds (while in state
Wait1-Right) for $a_{1}$ to return. Since, $a_{1}$ has already been consumed
by the black hole, so it fails to return to $home$ within the waiting time of
$a_{2}$. This observation of $a_{2}$ at $home$ instigates it to modify the
suspicious region by updating $S_{rgt}$ to $Dest$, and $a_{2}$ communicates
this updated information to the rest of the agents executing $SEQ3$ at $home$.
It is because, $a_{1}$ only explores the nodes of the suspicious region that
lies between $S_{lft}$ and $Dest$. Let $S_{new}$ be the modified suspicious
region, then $|S_{new}|=|Dest-
S_{lft}+1|=|S_{lft}+\lceil\frac{|S|}{2}\rceil-1-S_{lft}+1|=\lceil\frac{|S|}{2}\rceil<\lceil\frac{|S|}{2}\rceil+1$.

Now consider the other case, where instead of $a_{1}$, $a_{2}$ be the agent
which enters the black hole during an iteration. In this situation as well,
similar to the argument explained above in case of $a_{2}$, $a_{1}$ will get
to know $a_{2}$ has entered the black hole during the iteration, while $a_{1}$
waits for $n-Tnodes$ rounds at $home$. Observe, $a_{2}$ traverses the nodes of
the suspicious region that lies between $Dest$ and $S_{rgt}$. So, $a_{1}$
updates $S_{lft}$ to $Dest$ in order to get the updated suspicious region
$S_{new}$ and communicate with the rest of the agents executing $SEQ3$ at
$home$. This implies
$|S_{new}|=|S_{rgt}-Dest+1|=|S_{rgt}-S_{lft}-\lceil\frac{|S|}{2}\rceil+2|=||S|-\lceil\frac{|S|}{2}\rceil+1|\leq\lceil\frac{|S|}{2}\rceil+1$.

So, in each scenario, our claim holds.

Note that, if $|S|$ is odd then $|S_{new}|=\lceil\frac{|S|}{2}\rceil$,
otherwise,
$\lceil\frac{|S|}{2}\rceil\leq|S_{new}|\leq\lceil\frac{|S|}{2}\rceil+1$.

######  Lemma 4.4.

If during an iteration, exactly two agents gets destroyed by the byzantine
black hole, then in that iteration, the position of the black hole is detected
by the remaining alive agents.

######  Proof 4.5.

This situation of both agents being consumed by the black hole cannot arise
when $|S|=2$ and $k=2$, because in this case both agents explore disjoint
nodes of the suspicious region, in which only one node can be the black hole.

On the other hand when $|S|\geq 2$ and $k>3$, this situation of two agents
entering the black hole, can only arise for the agents $a_{1}$ and $a_{2}$,
where $a_{1}$ and $a_{2}$ are following $SEQ1$ and $SEQ2$, respectively. Now,
since the node (say $v_{b}$) at distance $Dest$ in the clockwise direction
from $home$ is the only common node that both $a_{1}$ and $a_{2}$ visits while
executing an iteration. So, if both these agents gets destroyed, then $v_{b}$
must be the node, in which the black hole is located. Now, as per our
algorithm, the agents executing $SEQ3$ waits at $home$ for $2n+2$ rounds,
after which they find that both $a_{1}$ and $a_{2}$ are yet to return $home$,
whereas $2n+2$ rounds are sufficient for these two agents to return back to
$home$ while executing their respective sequences, if they have not entered
the black hole. This scenario helps the remaining agent conclude that both
$a_{1}$ and $a_{2}$ has entered the black hole, and the node $v_{b}$ is the
exact position of the byzantine black hole.

######  Lemma 4.6.

Let $|S_{0}|$ be the initial length of the suspicious region where
$|S_{0}|=2^{p}+l$, $p\geq 1$ and $0\leq l<2^{p}$. Let $S_{i}$ be the
suspicious region after it is modified for the $i-$th time. Then,
$|S_{i}|\leq\lceil\frac{|S_{0}|}{2^{i}}\rceil+2$.

######  Proof 4.7.

Let $|S_{0}|$ be the initial length of the suspicious region where
$|S_{0}|=2^{p}+l$, $p\geq 1$ and $0\leq l<2^{p}$. Let $S_{i}$ be the
suspicious region after $i$ modifications. We now prove this lemma by
induction. For the base case let $i=1$. Then from Lemma 4.2,
$|S_{1}|\leq\lceil\frac{|S_{0}|}{2}\rceil+1<\lceil\frac{|S_{0}|}{2}\rceil+2$.
So the lemma is true for $i=1$. Let the lemma be true for $i=j-1$. That is,
$|S_{j-1}|\leq\lceil\frac{|S_{0}|}{2^{j-1}}\rceil+2$. Now to prove the lemma
we have to show that $|S_{j}|\leq\lceil\frac{|S_{0}|}{2^{j}}\rceil+2$. Now by
Lemma 4.2,
$|S_{j}|\leq\lceil\frac{|S_{j-1}|}{2}\rceil+1\leq\lceil\frac{\lceil\frac{|S_{0}|}{2^{j-1}}\rceil+2}{2}\rceil+1\leq\lceil\frac{|S_{0}|}{2^{j}}\rceil+2$.
Hence, by mathematical induction we can conclude that
$|S_{i}|\leq\lceil\frac{|S_{0}|}{2^{i}}\rceil+2$, for any $i\geq 1$

######  Lemma 4.8.

If $|S_{t}|>2$ , then there exists at least one agent which is following the
sequence $SEQ3$ in our Algorithm 1 in any iteration until the next
modification of $S_{t}$, where $S_{t}$ is the suspicious region after $t$
modifications .

######  Proof 4.9.

Let $S_{0}$ be the initial suspicious region. Then, $|S_{0}|=2^{p}+l$ where
$p\geq 1$ and $0\leq l<2^{p}$. Let $S_{i}$ be the suspicious region after $i$
modifications of it. Let for some $t>0$, $|S_{t}|>2$. This implies that during
all the previous $t$ iterations where the suspicious region is modified, only
one agent is consumed by the byzantine black hole. As otherwise $|S_{j}|=1$
for some $0<j<t$, and already the byzantine black hole is detected. This
implies after the $t$-th modification, number of agents consumed is exactly
$t$. So the remaining number of agent after $t$-th modification of suspicious
region is exactly $\lceil\log|S_{0}|\rceil+3-t$ (since
$\lceil\log|S_{0}|\rceil+3$, are the total number of agents executing
PerpExplore-F2F along $R$). Now in any iteration until the next modification
of $S_{t}$, there is an agent that follows $SEQ3$ if
$\lceil\log|S_{0}|\rceil+3-t\geq 3\implies t\leq\lceil\log|S_{0}|\rceil$.

Now we suppose, let $t>\lceil\log|S_{0}|\rceil$. Now there are two cases.

Case-I : $|S_{0}|=2^{p}$ (i.e., $l=0$). Then, $t>p$. Now by Lemma 4.6,
$|S_{p}|\leq 3$. Also, number of alive agent is exactly 3 after the $p-$th
modification. Now if $|S_{p}|$ is not less than or equal to 2, then the agents
will again follow the sequences $SEQ1,SEQ2$ and $SEQ3$ until the next
modification of $S_{p}$. Now , $|S_{p+1}|\leq 2$ ( Observation 4.1.1). Now
this is a contradiction as $2<|S_{t}|\leq|S_{p+1}|\leq 2$.

Case-II : Now let us consider the case where $|S_{0}|=2^{p}+l$ where
$2^{p}>l>0$. Then $t>p+1$. Now by Lemma 4.6, $|S_{p}|\leq 4$. Also, number of
alive agent is exactly 4 after the $p-$th modification. Now if $|S_{p}|$ is
not less than or equal to 2, then the agents will again follow the sequences
$SEQ1,SEQ2$ and $SEQ3$ until the next modification of $S_{p}$. Now,
$|S_{p+1}|\leq 3$ (by Observation 4.1.1). Again if $|S_{P+1}|$ is $\geq 2$
then the agents will again follow the sequences $SEQ1,SEQ2$ and $SEQ3$ until
the next modification of $S_{p+1}$. Now again by Observation 4.1.1,
$|S_{P+2}|\leq 2$. Now this again is a contradiction as
$2<|S_{t}|\leq|S_{p+2}|\leq 2$.

Hence $t\leq\lceil\log|S_{0}|\rceil$. Thus, there must exist an agent
following $SEQ3$ in any iteration after the $t-$th modification of suspicious
region until the next one where $|S_{t}|>2$

From the above proof we can have the following corollary

######  Corollary 4.10.

If $|S_{t}|>2$ where $S_{t}$ is the suspicious region after $t$ modifications,
then there is atleast 3 alive agents for all iterations after the $t$-th
modification of the suspicious region and until the next modification.

######  Lemma 4.11.

Let $S_{t}$ be the suspicious region after $t$-th modification of $S_{0}$,
where $S_{0}$ is the initial suspicious region. If $|S_{t}|=2$, then Algorithm
1, ensures that the number of agent which has not been consumed by the
byzantine black hole is at least 2, for all iterations after the $t$-th
modification of the suspicious region and until the next modification.

######  Proof 4.12.

As per our claim, $|S_{t}|=2$ after the $t$-th modification of $S_{0}$. This
implies that after the $(t-1)$-th modification, we have either $|S_{t-1}|=3$
or $|S_{t-1}|=4$. Now we have the following cases.

Case-I: If $|S_{0}|=2^{p}$ and $|S_{t-1}|=4$, then by Lemma 4.6, we have
$|S_{t-1}|\leq\lceil\frac{|S_{0}|}{2^{t-1}}\rceil+2\implies 2\leq
2^{p-t+1}\implies 1\leq p-t+1$, i.e., $t-1\leq p-1$. Now since in each
iteration where the suspicious region is modified exactly one agent gets
destroyed, this means after $t-1$ modifications of suspicious region, at most
$p-1$ agents gets destroyed by the black hole. This implies out of $p+3$
agents executing Algorithm 1 on $S_{0}$, now at least $4$ agents are alive to
explore the suspicious region $S_{t-1}$. Hence, in the worst case, exactly one
agent among them can enter the black hole at the $t$-th (note that 2 agents
cannot enter the black hole, because in that case $|S_{t}|$ will be 1, by
Lemma 4.4) modification whereas the updated length of suspicious region
$S_{t}$, i.e., $|S_{t}|=2$. Now for the case when $|S_{t-1}|=3$, by similar
argument $t-1\leq p$, so at least 3 agents among $p+3$ are now alive to
explore $S_{t-1}$. Again, by consumption of one agent in the worst case, the
updated suspicious region length $|S_{t}|$ will be 2. So, in both the
scenarios, we show that when $|S_{t}|=2$ at least 2 agents are alive.

Case-II: If $|S_{0}|=2^{p}+l<2^{p+1}$, where $0<l<2^{p}$ and $|S_{t-1}|=4$, in
this case we have $p+4$ agents operating along $S_{0}$ (since,
$\lceil\log|S_{0}|\rceil+3$ are the total number of agents) then again by
Lemma 4.6, we have $|S_{t-1}|\leq\lceil\frac{|S_{0}|}{2^{t-1}}\rceil+2\implies
2<2^{p-t+2}\implies t-1<p$, so by earlier argument discussed in case-I, at
least 5 (=$p+4-(p-1)$) agents are alive. So, in the worst case, exactly one
agent gets consumed among 5 agents for the modification of $S_{t-1}$, which
leads to the $t$-th modification, where $|S_{t}|=2$. On the contrary, if
$|S_{t-1}|=3$, then similarly we have $1<2^{p-t+2}\implies t-1<p+1$, i.e., at
least 4 agents are alive ($=p+4-p$ agents), so again in the worst case exactly
one agent gets consumed among 4 agents for the modification of $S_{t-1}$,
which leads to the $t$-th modification, where $|S_{t}|=2$. So, in this case as
well, in both the scenarios when $|S_{t}|=2$, at least 2 agents are alive.
This holds our claim.

######  Theorem 4.13.

PerpExplore-F2F solves the PerpExplore-BBH problem with
$\lceil\log(n-1)\rceil+3$ agents having face to face communication and
starting from the same node on a ring $R$ with $n$ nodes.

######  Proof 4.14.

We prove this theorem, by first ensuring that in any iteration of our
Algorithm 1, every node is visited by at least one agent. Second, we show
that, in any iteration there exists at least one alive agent.

Let $|S|$ be the length of the suspicious region and $k$ be the number of
alive agents at the beginning of iteration $i$. Let $|S|=2$ and $k=2$, in this
case we have, $S=\\{S_{lft},S_{rgt}\\}$. So, the two agents $a_{1}$ and
$a_{2}$ (say) follows the sequence $SEQ0$, in which $a_{1}$ is instructed to
visit $S_{lft}$ along clockwise direction, whereas $a_{2}$ is instructed to
visit $S_{rgt}$ along counter-clockwise direction, while performing an
iteration. This implies that, if $S_{lft}$ is at distance $l$ ($l>0$) in a
clockwise direction, $a_{1}$ after traversing a distance of $l$ reaches
$S_{lft}$, whereas $a_{2}$ traverses a distance of $n-l-1$ in counter-
clockwise direction to visit $S_{rgt}$, in an iteration. This in turn shows
that, the agents starting from $home$, visits each node of $R$ while
performing an iteration. Note that, $|S|>2$ and $k=2$ never occurs by
Corollary 4.10. So, the only possibility remains is that $|S|>2$ and $k>2$, in
this situation, one among them say, $a_{1}$ executes the sequence $SEQ1$,
another say, $a_{2}$ executes the sequence $SEQ2$, whereas the remaining
agents does not leave $home$ while executing $SEQ3$, in an iteration. Observe
that, $a_{1}$ traverses in a clockwise direction for $Dest$ distance, and
reaches the destination node. Similarly, $a_{2}$ also reaches this same node,
while traversing along a counter-clockwise direction for $n-Dest$ distance.
This shows that, in any iteration, there exists two such agents, which explore
the whole ring, hence exploration is guaranteed in each such iteration.

Next, we show that in every iteration, number of alive agents is at least 1.
Let us consider during the $i$-th iteration, all the agents gets consumed by
the byzantine black hole.

Note that, at the beginning of the $i-$th iteration, number of alive agent can
not be 1. By contradiction, let us suppose there is only one agent alive at
the beginning of $i-$th iteration which gets consumed by the byzantine black
hole during this iteration. This implies $|S|\geq 2$ at the beginning of this
iteration. Now by Lemma 4.11 and Corollary 4.10, there must exists at least
two alive agents at the beginning of the $i-$th iteration which contradicts
our assumption of one alive agent. Also observe that number of alive agent at
the start of iteration $i$, can not be strictly greater than 2. Otherwise, let
number of alive agents $k>2$ at the beginning of iteration $i$. Since during
iteration $i$ all the $k$ agents are destroyed, this implies $|S|\geq 2$ . Now
since $|S|\geq 2$ and $k>2$, our algorithm ensures that, in the worst case
during this iteration at most two agents can be consumed by the byzantine
black hole. So after the iteration number of alive agents is at least $k-2\geq
1$. This contradicts our assumption that all agents are destroyed at the end
of this iteration. Now the only remaining case is that exactly two agents are
alive at the beginning of $i-$th iteration. Similarly as both of the agents
are destroyed during the $i-$th iteration $|S|\geq 2$ at the beginning of this
iteration. Note that $|S|$ will be exactly 2, for $k=2$, as by Corollary 4.10,
we have if $|S|>2$ then $k$ must be at least 3. Now according to the
algorithm, both the agents follows $SEQ0$, which instructs them to follow
disjoint paths. Hence, this concludes that during this iteration, only can be
consumed by the black hole, while there exists another agent which is alive
even after the iteration, contradicting our assumption. Hence for all
iterations number of alive agents must be greater or equals to 1. Thus,
algorithm PerpExplore-F2F solves the PerpExplore-BBH problem with
$\lceil\log(n-1)\rceil+3$ agents having face to face communication and
starting from the same node on a ring $R$ with $n$ nodes.

###  4.2 Communication: Pebble

In this section, we consider the model, where each agent has an access to a
movable token (termed as pebble) which 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). Next, we discuss the idea of our algorithm PerpExplore-Coloc-Pbl
(Algorithm 2) which solves the PerpExploration-BBH problem with 3 agents, each
accompanying a pebble.

Description of PerpExplore-Coloc-Pbl: Given a ring $R$ with a byzantine black
hole node $v_{b}$, a set of agents $A=\\{a_{1},a_{2},a_{3}\\}$ (where w.l.o.g
ID of $a_{1}\leavevmode\nobreak\ <$ ID of $a_{2}\leavevmode\nobreak\ <$ ID of
$a_{3}$), are initially co-located at a safe node, which we term as $home$. In
this case as well, 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 again term as $S$, where the
cardinality of this arc is defined by $|S|$) for each of the three agents.

The idea of this algorithm is as follows: if all the three agents are at
$home$ along with their pebble, then in the $r-$th round ($r>0$) $a_{1}$ moves
clockwise with its pebble. In the next round, i.e., $(r+1)-$th round, $a_{2}$,
leaving its 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.
Note that $a_{1}$ moves to next node even if $a_{2}$ meets $a_{1}$ without
pebble if and only if $a_{1}$ is not at $home$, and waits for 3 rounds (i.e.,
till $(r+5)-$th round). In $(r+3)-$th round, $a_{2}$ leaves its current node,
moves one step in counter-clockwise direction, collects the left behind
pebble, and in $(r+4)-$th round 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}$. This
process continues, until each of $a_{1}$ and $a_{2}$ along with the two
pebbles they carried, reaches $home$. This movement of $a_{1}$ and $a_{2}$
guarantees exploration unless at least one agent is destroyed by the black
hole, while they are exploring the ring by following the above mentioned
rules. In the meantime the third agent $a_{3}$ along with a pebble waits at
$home$ for these remaining agents to return. Note that, if all the agents
along with the pebbles carried by them, return back to $home$, then again they
start the above mentioned execution from $home$, this guarantees that until an
agent enters the black hole, perpetual exploration is performed.

Now, if any agent ($a_{1}$ or $a_{2}$ or both $a_{1}$ and $a_{2}$), enters the
black hole, then our algorithm guarantees that either perpetual exploration is
performed by the remaining alive agents or, the byzantine black hole will be
detected within finite rounds by at least one alive agent, and it will
continue performing perpetual exploration, avoiding the byzantine black hole,
and independent of the position of other alive agents or pebbles.

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 lowest ID,
i.e., $a_{1}$ moves to state Leader, the agent with 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 3 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 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 in to state Initial.

Suppose, all the agents along with the pebbles successfully execute the $i$-th
iteration and reaches $home$, i.e., neither any pebble nor any agent gets
destroyed by the black hole. So, 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.

Execution of sequence $SEQ1$: $a_{1}$ performs this sequence, in which it
first changes to state Leader, after finding it as the lowest ID agent at
$home$ in state Initial. In state Leader, the agent performs the following
checks: if the current node is $home$, then it checks that if the current node
has the agent with second lowest ID, whereas the number of pebble at $home$ is
3 and $T_{time}\geq 2$. If all these conditions are satisfied, then the agent
waits till $T_{time}=4n$ after which it moves to state Initial during
$T_{time}=4n+1$. Otherwise, if it finds that it is with the second lowest ID
agent and number of pebble at $home$ is also 3, but $T_{time}<2$, in this case
the agent initializes $W_{time}=0$ (where $W_{time}$ is the waiting time of
the agent) and then moves one hop along with the pebble to the next clockwise
node. Otherwise, if the agent finds that neither it is with the second lowest
ID agent nor the number of pebbles at $home$ is 3, then it waits for 5 rounds
(i.e., waits when $W_{time}<6$), after which if still the above condition
persists, then concludes $S_{lft}$ as the node which is at a clockwise
distance of $n-2$ from $home$ and $S_{rgt}$ the node at a clockwise distance
of $n-1$. Further, it updates $W_{time}=0$ and moves to the next state
Detection.

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), 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 waits 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 at the current node and moving one hop
to the clockwise node.

Note that until and unless there is 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.

Execution of sequence $SEQ2$: $a_{2}$ being the second lowest Id agent in
state Initial, performs this sequence in an iteration. On successful
completion of this iteration, an agent starting from Initial, performs the
sub-sequence ${Follower-SEQ}$, $n$ times and then again changes to state
Initial. The sub-sequence ${Follower-SEQ}$ symbolizes the sequence Follower-
Find $\rightarrow$ Follower-Collect $\rightarrow$ Follower-Find, which an
agent performs $n$ times until it again changes to state Initial (i.e.,
${Follower-SEQ}$ is denoted by ${Follower-SEQ}^{n}$). While executing
${Follower-SEQ}$, the agent in state Follower-Find checks, whether the current
node does not contain the lowest ID agent and the $Move$ parameter is also set
to 0 (the parameter $Move$ is either 0 or 1, when 1 it symbolizes that the
current node must contain the lowest ID agent, when 0, it means the current
node is the adjacent counter clockwise node with respect to the node which
contains the lowest ID agent), if so then it moves one hop clockwise leaving
the pebble at the current node, while updating $Move$ to 1. Otherwise, if it
finds $Move$ to be 1 whereas the current node does not contain the lowest ID
agent, then it stops the current iteration, detects that current node is black
hole and starts performing perpetual exploration, avoiding the black hole
node. On the other hand, if the current node contains the lowest ID agent,
then $a_{2}$ directly changes to state Follower-Collect. In state Follower-
Collect, $a_{2}$ first moves one hop counter-clockwise, then in the current
node either finds a pebble or not. If it finds a pebble, then moves one hop
clockwise along with the pebble. Now, if $T_{time}=4n+1$ and current node is
$home$, then stops performing $Follower-SEQ$ and moves to state Initial.
Otherwise, updates $Move$ to 0 and changes to state Follower-Find. If the
pebble is not found, then it concludes current node to be the black hole and
starts performing perpetual exploration avoiding this node.

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, if $a_{2}$ finds any irregularities, based on whether
a pebble is present or not, then only it directly concludes the black hole
position. In all other cases, it follows the ${Follower-SEQ}$ sequence and
changes to state Follower-Collect.

Exploration of sequence $SEQ3$: This sequence is only performed by the highest
ID agent, which is $a_{3}$ in this case. In this sequence, after being in
state Initial, it changes to state Backup, in which the agent first waits at
$home$ till $T_{time}=4n$, after which it checks the following details, and
accordingly either moves to state Initial if no irregularities are detected,
otherwise moves to state Find-Pebble or Find-BH, based on the irregularity it
detects.

  * •

The current node, i.e., $home$ has only the lowest and highest ID agents,
i.e., $a_{1}$ and $a_{3}$, whereas the number of pebble at $home$ is 1. If
this condition is satisfied, then the agent changes its state to Find-Pebble.
Note that, this condition is satisfied only when $a_{2}$ fails to reach $home$
while performing this iteration, i.e., enters the black hole, while $a_{1}$
has detected some anomalies, which instigates it to leave the pebble at the
current position at which it detects the anomaly, and henceforth moves back to
$home$ while in state Report-Leader.

  * •

$home$ has only the highest and lowest ID agents, i.e., $a_{1}$ and $a_{3}$,
but number of pebble at $home$ is 2, which implies that $a_{2}$ has failed to
return to $home$ even when $T_{time}=4n$. In this case, $a_{3}$ concludes
$S_{lft}$ to be the node which is at a clockwise distance of $n-2$ from
$home$, whereas $S_{rgt}$ to be the node which is at a clockwise distance of
$n-1$ from $home$. Finally, it updates $W_{time}=0$ and then moves to state
Detection.

  * •

$home$ has all the three agents and moreover, number of pebbles present at
$home$ is also 3. In this case, $a_{3}$ changes to state Initial, completing
the iteration without detecting any anomalies.

  * •

After $4n$ rounds, there is no other agent except $a_{3}$ present at $home$.
In this case, the agent move one hop, clockwise without the pebble present at
$home$, and then changes to state Find-BH. This case arises only when both the
agents $a_{1}$ and $a_{2}$ fail to reach $home$, while performing this
iteration.

Now, next we define the states Report-Leader, Find-Pebble, Find-BH, Detection.
An agent moves to either of these states only when it detects some anomalies.

The state Report-Leader, is executed by only the lowest ID agent, i.e.,
$a_{1}$, while it is in state Leader. The anomaly detected is as follows,
$a_{1}$, after reaching a new node that is not $home$, along with the pebble
it is carrying, waits for at most 3 rounds, for second lowest ID agent, i.e.,
$a_{2}$ to arrive (which is in state Follower-Find). If $a_{2}$ does not
arrive even after the waiting, $a_{1}$ concludes that the agent (i.e.,
$a_{2}$) has entered the black hole, this triggers $a_{1}$ to move to state
Report-Leader. In this state, it moves clockwise until it finds the highest ID
agent, i.e., $a_{3}$ at $home$. Then waits until $T_{time}=4n$, after which
changes state to Find-Pebble.

1 Input: $n,\leavevmode\nobreak\ k=3$;

2 States:{Initial, Leader, Follower-Find, Follower-Collect, Backup, Report-
Leader,Find-Pebble, Detection, Find-BH}

3 In State Initial:

$T_{time}=0$ // $T_{time}$ is the number of rounds elapsed since the agent has
moved from state Initial

4 Declare $Current-Node$ as $home$.

5 Gather the Ids of the remaining agents at $home$.

6 if  _lowest ID_ then

7 Move to state Leader.

8

9 else if  _second lowest ID_ then

10 Set $Move=0$.

11 Move to state Follower-Find.

12

13 else

14 Move to state Backup.

15

16In State Leader:

17 if  _$Current-Node=home$_ then

18 if  _$With\leavevmode\nobreak\ Second\leavevmode\nobreak\
Lowest\leavevmode\nobreak\ Id\wedge\\#Pebble=3\wedge T_{time}\geq 2$ _ then

19 Wait at the current node till $T_{time}=4n$.

20 Move to state Initial.

21

22 else if  _$With\leavevmode\nobreak\ Second\leavevmode\nobreak\
Lowest\leavevmode\nobreak\ Id\wedge\\#Pebble=3\wedge T_{time} <2$_ then

23 $W_{time}=0$.

24 Move one hop along with the pebble to the next node along clockwise
direction.

25

26 else if  _$Not\leavevmode\nobreak\ with\leavevmode\nobreak\
Second\leavevmode\nobreak\ Lowest\leavevmode\nobreak\ Id\lor\\#Pebble\neq 3$_
then

27 if  _$W_{time} <6$_ then

28 $W_{time}=W_{time}+1$

29 else

30 $S_{lft}=$ node at a clockwise distance of $n-2$ from $home$

31 $S_{rgt}=$ node at a clockwise distance of $n-1$ from $home$

32 Update $W_{time}=0$ then move to state Detection.

33

34

35

36else

37 if  _with second lowest ID_ then

38 $W_{time}=0$.

39 Move one hop along with the pebble to the next node along clockwise
direction.

40

41 else

42 if  _$W_{time} <4$_ then

43 Stay at the current node, $W_{time}=W_{time}+1$.

44

45 else

46 Move to state Report-Leader while moving one hop in clockwise direction
along without pebble.

47

48

49

50In State Follower-Find:

51 if  _not with lowest ID $\wedge$ $Move=0$_ then

52 Move one hop clockwise, without pebble and update $Move=1$.

53 else if  _not with lowest ID $\wedge$ $Move=1$_ then

54 Detect the $Current-Node$ as black hole and continue exploring the ring
perpetually avoiding this node.

55

56 else

57 Move to state Follower-Collect.

58

59In State Follower-Collect:

60 Move one hop in counter-clockwise direction.

61 if  _pebble is found_ then

62 Collect the pebble, and move one hop clockwise along with the pebble.

63 if  _$T_{time}=4n+1\wedge Current-Node=home$_ then

64 Change to state Initial.

65

66 Update $Move=0$ and change to state Follower-Find.

67

68else

69 Detect the $Current-Node$ as black hole and continue perpetually exploring
the ring avoiding this node.

Algorithm 2 PerpExplore-Coloc-Pbl

54 In State Report-Leader:

55 if  _$T_{time} <4n+1$_ then

56 Move clockwise until finds the agent with highest ID.

57 Wait until $T_{time}=4n$.

58

59Change to state Find-Pebble.

60

61In State Backup:

62 Wait until $T_{time}=4n$.

63 if  _$Current-Node$ has only the lowest and highest ID agents and
$\\#Pebble=1$_ then

64 Move to state Find-Pebble.

65

66 else if  _$Current-Node$ has only the lowest and highest ID agents and
$\\#Pebble=2$_ then

67 $S_{lft}=$ node at a clockwise distance of $n-2$ from $home$

68 $S_{rgt}=$ node at a clockwise distance of $n-1$ from $home$

69 Update $W_{time}=0$ $home\\_away=1$ and move to state Detection.

70

71 else if  _$Current-Node$ has both lowest and second lowest Id agent and
$\\#Pebble=3$_ then

72 Change to state Initial.

73

74 else if  _$Current-Node$ has no other agent_ then

75 Move in a clockwise direction without pebble and change to state Find-BH.

76

77

78In State Find-BH:

79

80if  _a pebble is found_ then

81 Conclude the next node along clockwise direction is the black hole, and
continue perpetual exploration avoiding the black hole node.

82

83else

84 Move along a clockwise direction.

85

86

87In State Find-Pebble:

88 Move counter-clockwise without the pebble.

89 if  _a pebble is found_ then

90 Declare $Current-Node$ as $home$.

91 $S_{lft}=$ node at a clockwise distance of $n-2$ from $home$

92 $S_{rgt}=$ node at a clockwise distance of $n-1$ from $home$

93 Update $W_{time}=0$ and move to state Detection.

94

95else

96 Move along a counter-clockwise direction.

97

98In State Detection:

99

100if  _lowest ID_ then

101 Moves clockwise till the node at a distance $n-2$ from $home$ then returns
back to $home$ along the same path and checks for the other agent.

102 If other agent is there it repeats the same procedure as stated in line 86
of Algorithm 2. Otherwise detects $S_{rgt}$ as the black hole and start
exploring avoiding that node.

103else

104 Moves one hop counter-clockwise from $home$ then returns back to $home$
along the same path then waits for $2n-6$ rounds and checks for the other
agent.

105 If other agent is there it repeats the same procedure as stated in line 90
of Algorithm 2. Otherwise detects $S_{lft}$ as the black hole and start
exploring avoiding that node.

The state Find-Pebble, is performed together by only $a_{1}$ and $a_{3}$,
i.e., the lowest and highest ID agent. This state can be reached by $a_{1}$
only via Report-Leader state, whereas by $a_{3}$ from the state Backup. The
main idea for the agents in this state is to move counter-clockwise till they
find the pebble left by $a_{1}$ when it detects some anomaly (i.e., $a_{2}$
has entered the byzantine black hole) and moved into state Report-Leader. This
pebble acts as a marker which indicates that black hole is either the counter-
clockwise neighbour of this node or, it is at a counter clockwise distance of
2 hop from it. This node at which it finds the pebble is declared to be the
new $home$, from which they conclude $S_{lft}$ and $S_{rgt}$ to be the nodes
which are at a clockwise distance of $n-2$ and $n-1$, respectively from this
new $home$. Finally, they updates $W_{time}=0$ and then changes to state
Detection. Note that, this state is performed by an agent during the last
round of the current iteration, (i.e., when $T_{times}=4n+1$).

The state Find-BH, is only executed by the highest ID agent, i.e., $a_{3}$.
This state is executed by $a_{3}$, only when it finds no other agent at
$home$, at the last round of the current iteration. This situation can only
occur, when both the agents $a_{1}$ and $a_{2}$ has entered the black hole.
So, this triggers $a_{3}$ to change to state Find-BH, in which it moves along
a clockwise direction, until a pebble is found. Whenever, a pebble is found,
it concludes the next node to be the black hole, and starts performing
perpetual exploration avoiding this node.

Finally, the state Detection, is performed by an agent (i.e., $a_{1}$ or
$a_{3}$) only if they know the position of $S_{lft}$ and $S_{rgt}$, which are
not only two consecutive nodes in a suspicious region $S$. Moreover, these two
nodes are exactly at a distance of clockwise $n-1$ and $n-2$ distance from
$home$ (the $home$ can be the initial starting node, or it can be the updated
$home$ as well). In this state, the agent with lowest ID, i.e., $a_{1}$, moves
clockwise till it reaches $S_{rgt}$, and then again returns back to $home$.
After returning back, if it finds $a_{3}$, then again it performs the same
procedure. On the contrary, if it does not find $a_{3}$, then it understands
that $S_{rgt}$ is the black hole node, and hence continues perpetual
exploration avoiding this node.

On the other hand, $a_{3}$ in this state moves counter-clockwise direction
from $home$, i.e., reaches $S_{lft}$, after which it returns back to $home$
again following the same path and then waits for $2n-6$ rounds at $home$ and
then checks for the other agent, i.e., $a_{1}$. If it finds $a_{1}$, then
again continues to perform the same movement, otherwise it concludes that
$S_{lft}$ is the black hole node, and hence starts the perpetual exploration
of the ring just by avoiding this black hole node.

####  4.2.1 Correctness and Complexity

In this section we discuss the correctness and complexity of our algorithm
PerpExplore-Coloc-Pbl.

######  Lemma 4.15.

If no agent gets consumed by the byzantine black hole, while performing an
iteration of Algorithm 2, then our algorithm ensures that in that iteration,
either the ring $R$ is explored or there is one agent that knows exactly the
location of the black hole.

######  Proof 4.16.

Suppose till the completion of $i$-th iteration $(i>0)$ no agent is consumed
by the black hole, then in any iteration $0<j\leq i$, the agent $a_{1}$
follows the sequence $SEQ1$, whereas $a_{2}$ follows the sequence $SEQ2$, as
instructed starting from the initial $home$ node. Considering this scenario we
have two cases:

  * •

No agents and no pebbles are destroyed: In this case, while executing the
sequence $SEQ1$, the agent after changing its state to Leader from Initial,
visits a new node after every 4 rounds in clockwise direction. Since, no agent
has been consumed in this iteration as well, so $a_{1}$ un-obstructively
visits each node in a clockwise direction, and reaches $home$ to finally end
this sequence $SEQ1$, while again changing its state to Initial. This shows
that, at least one agent visits each node of $R$ in an iteration completing
the exploration of $R$.

  * •

No agent gets destroyed but some pebbles are consumed by the black hole: Note
that, this situation can only occur when the black hole consumes the pebble
carried and released by $a_{2}$, while $a_{2}$ is not at the node containing
the pebble, executing the sequence $SEQ2$. It is because, in an iteration,
only $a_{1}$ and $a_{2}$ moves away from $home$ while executing their
respective sequences $SEQ1$ and $SEQ2$. And the pebble carried by $a_{1}$ (
i.e., the agent with smallest ID) cannot be destroyed without destroying
$a_{1}$, as $a_{1}$ always carries the pebble at each node while executing its
respective sequence. So, in this situation, while $a_{2}$ ( i.e., the agent
with second lowest ID) in state Follower-Collect moves back to the adjacent
node in counter-clockwise direction, in order to collect the already released
pebble, absence of which triggers $a_{2}$ to conclude the current node to be
the black hole, and which leads the agent to immediately leave the black hole
node. In this case, the consumption of a pebble leads to the black hole
detection.

If no agent gets consumed by the byzantine black hole while performing an
iteration of Algorithm 2 but some pebbles are consumed by the black hole, then
by Lemma 4.15, one agent (more precisely, the agent with second lowest ID,
i.e., $a_{2}$) detects the exact location of the black hole. Further, this
agent continues to perpetually explore the ring $R$ by avoiding the black hole
node.

######  Lemma 4.17.

If exactly one agent enters the byzantine black hole while performing an
iteration of Algorithm 2, then within finite additional rounds any of the two
following conditions hold:

  1. 1.

The exact location of the black hole is detected by at least one agent.

  2. 2.

All alive agents become colocated and they agree about two consecutive nodes
$S_{lft}$ and $S_{rgt}$, one among which is the black hole.

######  Proof 4.18.

Note that the agent which has entered the black hole is either $a_{1}$ or
$a_{2}$, based on which we have the following conditions:

  * •

$a_{1}$ falls in to the black hole: This situation can only occur when $a_{1}$
following sequence $SEQ1$ is in state Leader, visits the black hole node along
with its pebble. Now, based on the adversarial choice of byzantine black hole,
the pebble may or may not be destroyed by the black hole. Irrespective of
which, $a_{2}$ within 3 additional rounds reaches the black hole node while in
state Follower-Find, and absence of $a_{1}$ triggers the agent $a_{2}$ to
determine the current node as black hole, and immediately leave the current
node.

  * •

$a_{2}$ falls in to the black hole: This can only happen when $a_{2}$ is not
with $a_{1}$ at the black hole node. Otherwise, both agents will be destroyed,
contradicting our claim. Note that, $a_{2}$ can either be with the pebble or
alone, while it is consumed by the black hole. Also note that, since $a_{2}$
is executing the sequence $SEQ2$, hence the distance between $a_{1}$ and
$a_{2}$ can be at most 2. So during an iteration, if $a_{2}$ is destroyed by a
black hole, then the black hole must be any one of the two consecutive
counter-clockwise nodes, from the current position of $a_{1}$. If the current
node is not $home$, in this case, $a_{1}$ gets to know about this fact, only
when it finds the absence of $a_{2}$ even after waiting for 3 rounds, at the
current node. Now, according to our algorithm, it leaves the pebble
accompanied by it, and moves from the current node in clockwise direction to
$home$ with state Report-Leader. After, reaching $home$, it waits until the
end of this iteration, i.e., until $4n$ rounds from the start of this
iteration and moves to state Find-Pebble. During the $4n+1$-th round from the
start of the current iteration, $a_{3}$ finds that it is only with $a_{1}$,
whereas only one pebble exits, this leads the agent to change its state to
Find-Pebble. In this state, both the agents move counter-clockwise from $home$
until they encounter a pebble. Note that, this pebble is the one left by
$a_{1}$ after determining the fact that $a_{2}$ has entered the black hole.
So, now both these agents $a_{1}$ and $a_{3}$, declare the node with pebble as
$home$, whereas also denote the adjacent counter-clockwise node from the
current node as $S_{lft}$, whereas the other node adjacent to $S_{lft}$ in
counter-clockwise direction as $S_{rgt}$. On the other hand, if the current
node of $a_{1}$ is $home$, while $a_{2}$ is destroyed by the black hole, then
$a_{2}$ can never reach $home$ along with the pebble it was carrying by
following the sequence $SEQ2$. So, at the end of this iteration, both $a_{1}$
and $a_{3}$ finds that there are two agents (i.e., $a_{1}$ and $a_{3}$) and
two pebbles, respectively at $home$. This leads both of them to conclude that,
the adjacent counter-clockwise node to be $S_{rgt}$, whereas the adjacent
counter-clockwise node of $S_{rgt}$ as $S_{lft}$.

So, in each case we showed that either of our two conditions hold.

######  Remark 4.19.

Following from Lemma 4.17, if exactly one agent gets destroyed by the
byzantine black hole and the exact location of the black hole is detected by
at least one agent, then our algorithm ensures that the ring is perpetually
explored by at least one alive agent while avoiding the black hole node. On
the contrary, all alive agents become co-located and they agree about two
consecutive nodes $S_{lft}$ and $S_{rgt}$, among which one is a black hole,
then until and unless another agent falls in to the black hole, our algorithm
ensures that the ring is perpetually explored, by the remaining alive agents.
Note that, by Lemma 4.20 while any one among them gets destroyed, then the
other agent detects the exact black hole node, and then further perpetually
explores the ring $R$, avoiding the black hole node.

######  Lemma 4.20.

Algorithm PerpExplore-Coloc-Pbl ensures that if two among three agents gets
consumed by the byzantine black hole, then the remaining agent knows the exact
location of the black hole within some additional finite rounds without being
destroyed.

######  Proof 4.21.

Let us suppose, by contradiction, there exists a round $r$ ($>0$), within
which two agents gets destroyed by the black hole, whereas the alive agent is
unable to detect the exact location. Now we have the following cases:

  * •

Both agents gets consumed by the black hole in the same iteration: Note that
in this case, the consumed agents are $a_{1}$ and $a_{2}$, respectively, which
while executing the sequences $SEQ1$ and $SEQ2$ enters the black hole. Also
note that, $a_{1}$ and $a_{2}$ can only be together at a node, when $a_{2}$
has left the pebble it is carrying in the counter-clockwise node. So, now
$a_{3}$ after the end of this iteration, finds that no agent among $a_{1}$ and
$a_{3}$ has reached $home$, which triggers $a_{3}$ to change to state Find-BH.
In this state, it moves clockwise, until it finds a pebble (this pebble is the
one left by $a_{2}$ in the counter-clockwise node of the black hole). Whenever
a pebble is found, $a_{3}$ concludes that the next node is the black hole,
which contradicts our claim.

  * •

There exists an iteration where exactly one agent is destroyed and the other
one is destroyed during round $r$: Now in this case let $r^{\prime}<r$ be a
round when exactly an agent is destroyed during an iteration, say $i>0$. Then
by Lemma 4.17, within finitely many additional rounds $r_{0}$, where
$r_{0}+r^{\prime}<r$, both the alive agents becomes colocated and agree about
two consecutive nodes $S_{lft}$ and $S_{rgt}$, one among which must be the
black hole. Observe that according to our algorithm, the node which is
clockwise adjacent to $S_{rgt}$ is determined to be the $home$ (if not already
so). Note that the other case according to Lemma 4.17 where after exactly one
agent is destroyed by the black hole during an iteration at a round
$r^{\prime}<r$, there is an agent that knows the exact location of the black
hole within a finite additional rounds and the agent starts exploring the ring
avoiding the black hole and so even after round $r$ it stays alive knowing the
exact location of the black hole contradicting our assumption. Now, when both
the agents are colocated during a round say $r_{0}+r^{\prime}<r$ and knows
that the black hole must be any of the two consecutive nodes $S_{lft}$ or,
$S_{rgt}$. In this case, they move in to state Detection. After which one
agent moves clockwise until it reaches $S_{lft}$ and the other one moves
counter clockwise until it reaches $S_{right}$ and moves back to $home$. The
agent that visits $S_{rgt}$ waits for the other agent at $home$ for $2n-6$
rounds which is sufficient for the other agent to return back at $home$. Now
when during round $r$, another agent among these two gets destroyed, within at
most $(2n-4)$ rounds they fails to meet at $home$. Which trigers the remaining
alive agent to determine exactly which one among $S_{lft}$ or, $S_{rgt}$ is
the black hole. This also contradicts the claim we made earlier. Thus, The
algorithm PerpExplore-Coloc-Pbl ensures that, if two agent among three agents
gets consumed by the byzantine black hole, the remaining agent must know the
exact location of the black hole in some finite additional rounds without
getting destroyed.

######  Corollary 4.22.

Number of alive agents must be at least 2, when the exact position of the
byzantine black hole is not known to them.

From Lemma 4.20 and algorithm PerpExplore-Coloc-Pbl we have the following
theorem

######  Theorem 4.23.

A set of 3 synchronous colocated agents equipped with one pebble each are
necessary and sufficient to solve PerpExploration-BBH on a ring $R$.

######  Remark 4.24 (Algorithm on whiteboard model of communication).

The PerpExplore-Coloc-Pbl algorithm (i.e., Algorithm 2 ) also works for
colocated agents with whiteboard model of communication. The agents can easily
simulate a pebble on a node by a bit marked on that nodes memory. Also,
carrying a pebble from one node to another can be simulated by removing the
marking from the current node’s memory and move to a new node where the agent
writes a new bit. Thus 3 colocated agents are also sufficient to solve
Perpexplore-BBH when the nodes are equipped with whiteboards.

##  5 Scattered Agents

###  5.1 Communication: Pebble

In this section, we discuss the model where the agents are placed arbitrarily
along the nodes of the ring $R$ (note that each such node must be a safe
node), where each agent has a movable token, which it can carry along with it,
and acts as a mode of inter agent communication. Moreover, the agent can
gather the IDs of other agents which are currently at the same node at the
same round. With this context, in the following part we show that 4 scattered
agents with a pebble each is sufficient to solve PerpExploration-BBH on $R$,
using our algorithm PerpExplore-Scat-Pbl.

If 4 agents are scattered in more than one nodes initially then there are 3
cases. Firstly, all four agents are at different nodes. Secondly, Four agents
are scattered in three different nodes nodes initially. For this case there
exists exactly one node with two agents and remaining two nodes with exactly
one agents each. In the third case, four agents are scattered in two nodes
initially. In this case either each of the two nodes contains exactly two
agents or, one node contains three agents and the other one has exactly one
agent. We here describe and present the pseudocode considering the first case
only. The case with 3 agents in one node can be dealt by instructing the
colocated agents to execute PerpExplore-Coloc-Pbl when there are three agents
on the current node (i.e., from the beginning). The algorithm we discuss here
can also be used for the remaining cases with slight modifications. These
modifications are described in the Remark 5.7

The main idea of the PerpExplore-Scat-Pbl algorithm is that 4 agents
perpetually explore the ring, when no agents are consumed by the black hole.
Our algorithm ensures that during this exploration at most one agent can be
destroyed. In this scenario, the remaining agents within further finite time,
gather at a single node (which is the starting node of either of these 4
agents, hence it is safe), and after which they together start executing the
algorithm PerpExplore-Coloc-Pbl.

At the beginning of the Algorithm 3 all agents are in state Initial1. In this
state, the agents declare their current node as $home$, moreover they
initialize the variables $size=0$ and $s=0$, where $size$ variable is used by
the agents in order to store the length of the path between it’s own $home$
and the nearest $home$ of another agent in the clockwise direction. Further
the variable $s$ indicates the state transition. If the agent is at state
Forward and $s=$ 0 then the agent moved from state Initial1 to its current
state (i.e., state Forward), otherwise if the agent is at state Forward and
$s=1$ then this indicates it changes to state Forward from state Wait2. An
agent $a_{1}$ in state Forward, initializes $W_{time}=0$ (which stores the
waiting time) and checks whether $s=0$ or $s=1$. Note that, if $s=0$ and the
current node is $home$, then the $a_{1}$ is first instructed to leave the
pebble at current node and then move clockwise direction, after increasing
$size$ by 1. The next node where $a_{1}$ has reached can either be $home$ of
another agent, say $a_{2}$, or it is not $home$ for any other agents. For the
first case $a_{1}$ would find a pebble on its $Current-Node$ which was left by
$a_{2}$. In this case $a_{1}$ updates $s$ to 1 and moves into state Wait1. On
the other hand, if the $Current-Node$ is not $home$ of any other agents then
$a_{1}$ finds no pebble at the $Current-Node$ and thus moves clockwise after
increasing the variable $size$ by 1. Note that, when $s=0$ and an agent is in
state Forward it always finds another pebble on some node, if it is not
destroyed (this pebble must be left by another agent which is simultaneously
executing Algorithm 3 and currently in state Forward). This node must be the
clockwise nearest $home$ (i.e., $home$ of another agent which is clockwise
nearest to own $home$). Now since during each move at state Forward, an agent
increases the variable $size$ by 1, the $size$ variable must store the length
between an agents own $home$ and the clockwise nearest $home$ when the agent
finds another pebble. Beyond this point (i.e., when $s=1$) the agents will use
the $size$ variable as reference to calculate how much it should move, as
after this, as there is a possibility that the agent may not find a pebble at
the clockwise nearest $home$.

On the contrary, if $s=1$, this implies the agent already knows how much
distance it should travel from its own $home$ in order to reach the clockwise
nearest $home$. So, now if the current node is $home$ it just moves clockwise
by initializing the variable $distance$ to 1 (where the variable $distance$
stores the amount of distance the agent has traversed from its own $home$).
Otherwise, if current node is not $home$, then the agent continues to move
clockwise while updating $distance$ by 1, until it reaches the clockwise
nearest $home$ (i.e., when $distance=size$), after which it further changes to
state Wait1.

In state Wait1, the agent is instructed to wait at the current node (more
specifically, the current node is the clockwise nearest $home$ of the agent)
for $n-size-1$ rounds. After which it changes to state Fetch. Note that, if
each agent starts executing the state Forward at the same round, this implies
that these agents change to state Fetch together at the same round (which is
precisely at the $n+1$-th round since the start of state Forward). Thus we
have the following observation. If all agents moved into the Forward state
together at a round $t$ then, all of them move to state Fetch together at the
round $t+n+1$.

In state Fetch, the agent first checks if the current node has a pebble, if so
then it further checks whether current node is $home$ or not. If the current
node is not $home$, then it moves counter-clockwise with pebble, until it
reaches $home$. Otherwise, if current node is $home$ then it checks whether
there are more than one pebble present at the current node or not. If so, then
the agent changes its state to Gather1. Otherwise, if the current node does
not have more than one pebble, then it initializes $W_{time}$ to 0 and changes
to state Wait2.

In state Wait2, the agent first checks whether $W_{time}<2n-size$, if so then
it further checks whether $\\#Agent$ at current node is exactly 1. If these
two conditions are satisfied then the agent just increments $W_{time}$ by 1.
On the other hand, if it finds that $W_{time}<2n-size$ but $\\#Agent$ at the
current node is 2, then it changes its state to Gather2 and updates $W_{time}$
to 0. Otherwise, if it finds $W_{time}<2n-size$ but $\\#Agent$ at the current
node is 3 then it updates $W_{time}$ to 0, whereas changes its state to Coloc.
Lastly, whenever it finds $W_{time}=2n-size$, it changes its state to Forward.

Note that if no agent gets destroyed by the black hole, then our algorithm
guarantees that an agent can neither changes its state to Gather1 or in state
Gather2. It is because, an agent, say $a_{1}$ can only find more than one
pebble at its $home$ node, only when another agent say $a_{2}$ (exploring the
counter-clockwise nodes of $home$ of $a_{1}$), which was supposed to fetch the
pebble left by $a_{1}$ at its $home$, is destroyed. In this case, whenever
$a_{1}$ returns while in state fetch with another pebble, it finds more than
one pebble. So the first agent, which first finds this anomaly changes its
state to Gather1 from the state Fetch. Now this agent must initiate gathering
with the remaining two agents (as it is the one which has first detected the
anomaly of more than one pebble at its $home$). Note that, if while $a_{1}$
starts its gathering phase, moving in a clockwise direction, there is a
possibility that other agents are still moving either in clockwise or counter-
clockwise direction. So, to address this challenge, the algorithm instructs
$a_{1}$ (i.e., the agent which is in state Gather1) to wait at the current
node (i.e., its $home$) for precisely $n-size-1$ rounds, and then start moving
clockwise direction. This waiting time of $a_{1}$ guarantees all the other
alive agents to reach their respective $home$ while in state Fetch. Now, in
order to avoid further movement of remaining agents (i.e., again change to
state Forward, since these agents are yet to detect any anomaly, which makes
gathering a bit challenging), our algorithm instructs the remaining agents to
wait at the current node for a certain number of rounds (i.e., more precisely,
$2n-size-1$). This waiting period is sufficient, for the agent $a_{1}$ to meet
with the other alive agents while in state Gather1. Note that, if no agent
detects any anomaly, then they directly change their state to Wait2 from the
state Fetch. If no such agent exists which encounters any anomaly and changes
its state to Gather1 or Gather2 then this waiting time of $2n-size-1$ rounds,
also ensures that all of them must move to state Forward at the exact same
round (i.e, ($3n+2$)-th round from the previous time it moved to state
Forward)111At $(n+1)$-th round an agent moves to state Fetch after that it
moves for $size$ rounds to reach its $home$ in counter-clockwise direction and
changes to state Wait2. So at round $n+3+size$ an agent changes to state
Wait2. After that waits for further $2n-size-1$ rounds and changes to state
forward, taking a total of $3n+2$ rounds . Now we have the following
observation Let $t$ be a round when all alive agents moved into state Forward.
If no agent detects any anomaly (i.e., no agent finds more than one pebble at
home) then, at round $t+3n+2$ all the agents together move into state Forward
again.

An agent in state Gather1, is the first agent to detect the anomaly, hence it
is first instructed to wait at the current node, i.e., its $home$ for the
first $n-size-1$ rounds, and then start moving in a clockwise direction, while
accompanying all the pebbles at the current node 222Note that we have
considered that in this case an agent, while in state Gather1 or Gather2 can
carry more than one pebble, which can be easily restricted to one agent can
carry only one pebble, but in that case the agent needs to return and carry
one pebble each time and reach back to its current node. This movement in the
clockwise direction continues until the number of agent at the current node is
exactly 3, after which it changes to state Coloc.

An agent in state Gather2 (i.e., the alive agents which are not the first to
detect the anomaly), first checks whether the current node has exactly 3
agents on it, if not then it moves in a counter-clockwise direction, while
accompanying the pebbles present at its $home$,

1 Input: $n$

2 State:{Initial1, Forward, Fetch, Wait1, Wait2, Coloc, Gather}

3 In State Initial1:

4 Declare $Current-Node$ as $home$.

5 Initialize $size=0$ and $s=0$, then change to state Forward.

6 In State Forward:

7 Initialize $W_{time}=0$.

8 if  _$s=0$_ then

9

10 if  _$Current-Node$ is not $home$ and has a pebble_ then

11 update $s=1$ and Change state to Wait1

12

13 else if  _$Current-Node$ is $home$_ then

14 Leave the pebble at $home$.

15 Move in a clockwise direction and update $size=size+1$.

16

17 else

18 Move in a clockwise direction and update $size=size+1$.

19

20

21else

22 if  _$Current-Node$ is $home$_ then

23 Initialize $distance=1$ and move in a clockwise direction leaving the
pebble.

24

25 else if  _$distance <size$_ then

26 Move in a clockwise direction and update $distance=distance+1$.

27

28 else if  _$distance=size$_ then

29 Change State to Wait1.

30

31

32In State Wait1:

33 if  _$W_{time} <n-size$_ then

34 $W_{time}=W_{time}+1$.

35

36else

37 Change state to Fetch.

38

39In State Fetch:

40 if  _$Current-Node$ has a pebble_ then

41 if  _$Current-Node$ is not $home$_ then

42 Move counter-clockwise with the pebble.

43

44 else

45 if  _$home$ has more than one pebble_ then

46 Change to state Gather1.

47

48 else

49 Initialize $W_{time}=0$ and change to state Wait2.

50

51

52

53else

54 if  _$Current-Node$ is not $home$_ then

55 Move in a counter-clockwise direction.

56

57 else

58 Initialize $W_{time}=0$ and change to state Wait2.

59

60

61In State Wait2:

62 if  _$W_{time} <2n-size\wedge\\#Agent$ at $Current-Node$ is 1_ then

63 $W_{time}=W_{time}+1$.

64

65 else if  _$W_{time} <2n-size\wedge\\#Agent$ at $Current-Node$ is 2_ then

66 Initialize $W_{time}=0$ and change to state Gather2.

67

68 else if  _$W_{time} <2n-size\wedge\\#Agent$ at $Current-Node$ is 3_ then

69 Initialize $W_{time}=0$ and change to state Coloc.

70

71 else if  _$W_{time}=2n-size$_ then

72 Change to state Forward.

73

74In State Gather1:

75 if  _$W_{time} <n-size$_ then

76 $W_{time}=W_{time}+1$

77else

78 if  _$\\#Agent$ at $Current-Node<$3_ then

79 Move in a clockwise direction with all the pebbles at the $Current-Node$

80

81 else

82 Change to state Coloc.

83

84In State Gather2:

85 if  _$\\#Agent$ at $Current-Node$ < 3_ then

86 Move in a clockwise direction with all the pebbles at the $Current-Node$.

87

88else

89 Change to state Coloc.

90

91In State Coloc:

92 Declare $Current-Node$ as $home$.

Change state to Initial and execute PerpExplore-Coloc-Pbl.// State Initial is
the state defined in PerpExplore-Coloc-Pbl algorithm

93

Algorithm 3 PerpExplore-Scat-Pbl

until it satisfies the condition, where it finds a node on which a total of 3
agents exists. After which they change their state to Coloc.

In state Coloc, an agent declares its current node as $home$, while also
changes its state to Initial 333The state Initial is defined in Algorithm 2
and then executes algorithm PerpExplore-Coloc-Pbl.

####  5.1.1 Correctness and Complexity

In this section, we discuss the correctness and complexity of our algorithm
PerpExplore-Scat-Pbl.

######  Lemma 5.1.

PerpExplore-Scat-Pbl guarantees to solve PerpExploration-BBh problem if no
agent is consumed by the byzantine black hole.

######  Proof 5.2.

Let us define a segment for an agent $a_{1}$ be $Seg(a_{1})$, where
$Seg(a_{1})$ is defined to be the collection of consecutive nodes in the
clockwise direction, starting from its own $home$ and its clockwise nearest
$home$ (which is the $home$ of another agent say, $a_{2}$). Note that, since
no agent is consumed by the black hole, any agent, say $a_{1}$, while
executing the Algorithm 3, starts moving in clockwise direction in state
Forward, reaches the nearest clockwise $home$, i.e., the last node of this
segment $Seg(a_{1})$, then changes its state to Wait1, and after waiting for
$n-size$ rounds, again changes its state to Fetch. In state Fetch, the agent
basically moves counter-clockwise, until and unless it reaches its own $home$,
which is nothing but the first node of this segment $Seg(a_{1})$. Also, note
that, each agent, changes their state to Forward and Fetch together at the
same round, while exploring their respective segments. Now, note that, the
union of all these segments is basically the whole ring $R$ (i.e., more
specifically $\cup^{4}_{i=1}Seg(a_{i})=R$) . Hence, this guarantees that the
ring is perpetually explored if no agent is consumed by the black hole.

######  Lemma 5.3.

If an agent is consumed by the byzantine black hole, then within an additional
finite rounds, there exists exactly one agent, which changes its state to
Gather1.

######  Proof 5.4.

Let $a_{1}$ be an agent exploring $Seg(a_{1})$. Without loss of generality,
let the black hole be in $Seg(a_{1})$. Also let $a_{2}$ be another agent which
is exploring the segment $Seg(a_{2})$, where $home$ of $a_{2}$ is the common
node between $Seg(a_{1})$ and $Seg(a_{2})$. Also, let $a_{3}$ be an agent
which is exploring the segment $Seg(a_{3})$, where the $home$ of $a_{3}$ is
the common node between $Seg(a_{2})$ and $Seg(a_{3})$. Note that, $a_{1}$ can
be consumed by the black hole, either in state Forward or in state Fetch.

  * •

If $a_{1}$ is consumed while in state Forward, then it fails to bring back the
pebble from the $home$ of $a_{2}$, while it is scheduled to change its state
to Fetch, after ending the states Forward and Wait1. Note that, since we have
assumed that the black hole is in $Seg(a_{1})$, and $Seg(a_{1})\cap
Seg(a_{2})=\\{home\text{ of }a_{2}$}. Thus, $a_{2}$ must bring a pebble from
the $home$ of $a_{3}$ to it’s own $home$, after it changes its state to Fetch.
So, now as $a_{2}$ reaches its own $home$ along with the pebble it carried
from the $home$ of $a_{3}$, it finds that there already exists another pebble,
which the agent $a_{1}$ is unable to carry back to its own $home$, as it is
already consumed by the black hole. This causes an anomaly for $a_{2}$ at its
own $home$ (i.e., encountering more than one pebble). After detecting the
anomaly $a_{2}$ immediately changes its state to Gather1. Note that, after
$a_{1}$ is consumed by the black hole, it has taken an additional at most
$size-1+(n-size)+1+size+1=n+size+1$ 333calculates the number of rounds it took
$a_{2}$ to change to state Gather1, where at most $size-1$ rounds required in
state Forward after $a_{1}$ gets consumed by the black hole, $(n-size)$ rounds
for changing to state Wait1 and waiting, 1 round for changing from Wait1 to
Fetch, then $size$ rounds for moving in state Fetch and returning back to its
$home$, and lastly 1 round for changing to state Gather1 from Fetch. rounds to
change the state of $a_{2}$ to Gather1. Further in this case we show that no
other agents except $a_{2}$ changes to state Gather1. Let $t^{\prime}$ be the
round when $a_{2}$ changes its state to Gather 1. And $t<t^{\prime}$ be the
last round before $t^{\prime}$ when all the agents moved into state Forward.
Then $t^{\prime}=t+n+1+size+1$. Next $a_{2}$ waits for $n-size-1$ rounds that
is until round $t+2n+1$ and starts moving counter clockwise being in state
Gather1. Note that by observation 1, the other agents stay at their home until
round $t+3n+1$. So from $t+2n+2$ until $t+3n+1$, these $n-1$ rounds are enough
for $a_{2}$ to meet the other two while they are still being in the state
Wait2. So they change their state to Gather2 and eventually to Coloc. As an
agent can not change state to Gather1 from state Coloc or Gather2, no other
agent changes to state Gather1.

  * •

If $a_{1}$ is consumed while in state Fetch. In this case, $a_{2}$ after
returning back to its $home$ carrying the pebble from the nearest clockwise
$home$, i.e., the $home$ of $a_{3}$, finds no anomaly. It is because, $a_{1}$
has been consumed by the black hole while in state Fetch, so that means, the
pebble at $home$ of $a_{2}$ has been carried by $a_{1}$. Since, $a_{2}$ does
not encounter any anomaly, hence it drops the pebble at its $home$, changes to
state Wait2, waits at $home$ for $2n-size-1$ rounds and then changes to state
Forward again. So, while executing the same execution, after reaching the
clockwise nearest $home$, i.e., $home$ of $a_{3}$, it again changes its state
to Wait1, waits for $n-size-1$ rounds, and further changes its state to Fetch.
Note that, here at the $home$ of $a_{3}$, there exists a pebble which was
earlier dropped by $a_{3}$, while it changed its state from Fetch to Wait2.
So, $a_{2}$ carries this pebble and reaches its own $home$, where it finds the
anomaly. It is because, as $a_{1}$ has been consumed by the black hole, it is
unable to carry the pebble dropped by $a_{2}$ during its last state change
from Fetch to Wait2. This phenomenon triggers $a_{2}$ to change its state to
Gather1. Note that, since $a_{1}$ has been consumed by the black hole, it
takes an additional $(size-1)+1+(2n-size)+size+1+(n-size)+size+1=3n+size+2$
222calculates the number of rounds it took $a_{2}$ to change to state Gather1,
where $size-1$ rounds required in state Fetch after $a_{1}$ gets consumed by
the black hole, 1 round for changing its state from Fetch to Wait2, after this
the agent waits for $2n-size-1$ rounds and in one additional round changes to
state Forward, in this state it takes $size$ rounds, 1 round required to
change to state Wait1, then $n-size-1$ rounds the agent waits, whereas 1 more
round required to change to state Fetch, finally $size$ rounds in state Fetch,
and lastly 1 round for changing its state to Gather1rounds to change $a_{2}$’s
state to Gather1. And as shown for the first case it can be similarly showed
that except $a_{2}$ no other agent changes state to Gather1

######  Lemma 5.5.

After the first agent changes its state to Gather1, it takes an additional at
most $2n-2$ rounds, for the remaining agents to gather at a single node (i.e.,
the nearest counter-clockwise $home$ of the black hole node) along with their
pebbles.

######  Proof 5.6.

Let $a_{2}$ be the agent which changes to state Gather1 at $t$-th round (where
$t>0$), due to the fact that it encounters an anomaly at its $home$ because
$a_{1}$ (w.l.o.g) has been consumed by the black hole, and the length of the
segment it explores be denoted by $size$ (i.e., length of $Seg(a_{2})=size$).
Also, let $t_{0}$ ($0<t_{0}<t$) be the last round when each agent changed
their states to Forward. Note that $t$ should be exactly equal to
$t_{0}+size+1+(n-size-1)+1+size+1=t_{0}+n+size+2$ 333movement in state Forward
for $size$ rounds, then one round for change to state Wait1, then stay in
state Wait1 for $n-size-1$ rounds, after which change to state Fetch for one
round, and move in state Fetch for $size$ rounds, and finally change to state
Gather1 for one round. Note that $a_{2}$ after changing its state to Gather1
(current round is $t_{0}+n+size+2$, which is also the $t-$th round according
to our definition of $t$), further waits for $n-size-1(\leq n-2$, as $size\geq
1$ ) rounds (current round $t_{0}+2n+1$), and starts moving clockwise from
$(t_{0}+2n+2)-$th round. On the other hand, an alive agent which was in state
Fetch at $t-$th round, must have changed its own state to Fetch at
$(t_{0}+n+1)-$th round (refer Observation 5.1). From Fetch, it takes further
at most $n$ (since length of a segment can be at most $n-1$) rounds to change
to state Wait2. Note that any other alive agent except $a_{2}$ must change to
state Wait2 after completion of state Fetch as by Lemma 5.3, exactly one agent
(here $a_{2}$) already changed its state to Gather1 from Fetch at round
$t=t_{0}+n+size+2$). So, any agent except $a_{2}$ at the round
$(t_{0}+2n+1)-$th round must be in state Wait2, and should remain in this
state until $(t_{0}+3n+2)-$th round, if no anomaly is detected (refer
Observation 1) or meets with other agents. So, any alive agent except $a_{2}$
remains at their $home$ within $t_{0}+2n+1$ to $t_{0}+3n+2$ rounds. This is by
Lemma 5.3, only $a_{2}$ being the first agent to detect anomaly can change its
state to Gather1, whereas the remaining agent can only change its state to
Gather2 or Coloc, when they meet with $a_{2}$, while in state Wait2. Further,
note that an alive agent except $a_{2}$, waits at their respective $home$ for
$n+1$ rounds since, $a_{2}$ starts moving clockwise being in state Gather1
(after $(t_{0}+2n+1)-$th round). Now, when $a_{2}$ reaches its clockwise
neighbor (say) $a_{3}$, at its $home$. $a_{3}$ must be at state Wait2, in this
case, $a_{3}$ changes its state to Gather2, and starts moving clockwise along
with $a_{2}$ carrying their respective pebbles, until they meet another agent,
(say) $a_{4}$, at its $home$, while in state Wait2. After which they all
change to state Coloc, which also guarantees that they have at least 3 pebbles
at the current node (since $a_{2}$ carried at least 2 pebbles from its own
$home$ where it detects the anomaly, $a_{3}$ also carried its one pebble
present at its own $home$). Now since no agent can change to state Gather1
from Gather2 or Coloc, $a_{2}$ is the only agent that changes to state
Gather1. Note that, before gathering $a_{2}$, $a_{3}$ and $a_{4}$ can never be
destroyed, as they traverse only the nodes in $\cup^{4}_{i=2}Seg(a_{i})$,
whereas the black hole is in $Seg(a_{1})\backslash\\{home$ of $a_{1}$, $home$
of $a_{2}\\}$.

######  Remark 5.7.

In the discussion of our Algorithm 3, we have considered that 4 agents are
scattered along 4 distinct nodes (i.e., each node with multiplicity 1). Here
we describe how our algorithm (Algorithm 3) works for the remaining cases,
(i.e., when 4 agents are scattered among 3 or 2 nodes initially) by slight
modification. Observe that, in these remaining cases there exists at least one
node, where multiplicity is greater than 1 initially. Let there exists a node
with multiplicity $3$, in this case, these agents directly start executing
PerpExplore-Coloc-Pbl, while execution if they encounter the fourth agent
somewhere along $R$, they just ignore this agent (note that the IDs, of all
the 3 initially co-located agents are already collected by each other) while
executing their current algorithm. On the other hand, if initially there
exists a node with multiplicity greater than 1 and less than 3, then in that
case, only the lowest ID agent (say $a_{1}$) at the current node, changes its
state Forward, whereas the other agent at the current node (say $a_{2}$)
changes its state Backup-Wait at some round say $t_{0}$ $(>0)$. The agent in
state Forward, continue executing the algorithm PerpExplore-Scat-Pbl, whereas
the agent in state Backup-Wait, waits at the current node for $2n+1$ rounds
(i.e., until $t_{0}+2n+1$-th round) and then checks for anomaly in the next
round (i.e., if the current node has more pebble than current number of
agents). If such anomaly exists after $t_{0}+2n+1$ round, then that implies
that $a_{1}$ is already in state Gather1. It is because, $a_{1}$ while it
returned back to its $home$ carrying a pebble in state Fetch at round
$t_{0}+n+size+2$ round (where $size$ is the length of $Seg(a_{1})$),
encounters the first anomaly, i.e., the number of pebble is more than number
agents. In that case, it directly changes its state to Gather1, and further
waits at $home$ for $n-size-1$ rounds, i.e., till $t_{0}+2n+1$ rounds. After
which it starts to move clockwise, and on the other hand $a_{2}$ also starts
moving clockwise, while changing its state to Gather2 from Backup-Wait. This
guarantees that if the anomaly is detected at a multiplicity then both $a_{1}$
and $a_{2}$ moves together to gather, along with the third agent which is in
state Wait2 (as described in Lemma 5.5) and changes its state to Gather2
whenever it finds $\\#Agent$ at its $home$ is more than one. Now if the
anomaly is not detected at the multiplicity, that is $a_{2}$ at round
$t_{0}+2n+1$ finds no anomaly then it moves into state Backup whereas $a_{1}$
is in state Wait2 at the same node. Both of them waits until round $3n+1$ and
at round $3n+2$, $a_{1}$ changes its state to Forward again (refer to
Observation 1) and $a_{2}$ changes its state to Backup-Wait again. If some
other agent detects anomaly it must meet $a_{1}$ and $a_{2}$ at their $home$
at some round $t$ where $t_{0}+2n+2\leq t\leq t_{0}+3n+1$. In that case they
find that there are 3 agents at their $home$ and all of them change to state
Coloc and executes algorithm PerpExplore-Coloc-Pbl.

Next we can have the following theorem

######  Theorem 5.8.

A set of 4 synchronous scattered agents with one pebble each is necessary and
sufficient to solve the PerpExploration-BBH problem on a ring $R$, when the
initial starting locations of the agents are different along $R$.

###  5.2 Communication: Whiteboard

In this section, we discuss the algorithm PerpExplore-Scat-WhitBrd, which
achieves PerpExploration-BBH, with the help of three agents on a ring $R$ with
$n$ nodes, where each node has a whiteboard that can store $O(\log n)$ bits of
data. Note that, in this model as well we have considered that the agents are
placed arbitrarily placed along the nodes of the ring $R$ (each such node is a
‘safe node’). So, there can be two cases, first, all the three agents are
initially placed at three different positions, second, two agents are together
whereas the third agent is in a different position. We will provide algorithm
for the first case only, as an algorithm for the second case can be easily
designed by modifying and merging the algorithms for the first case and
algorithm PerpExplore-Coloc-Pbl.

The idea of our algorithm PerpExplore-Scat-WhitBrd is as follows: the three
agents separately explore three segments of the ring $R$, such that, their
union is the whole ring $R$ and intersection of any two segment contains only
a safe node (which is a $home$ for one agent). Thus, while exploring, only one
agent can be consumed by the black hole, and in an additional finite number of
rounds another agent can learn,the consumption of the earlier agent by the
black hole (this agent is precisely the agent whose segment has a safe node
common with the segment of the consumed agent. Also it learns about this
consumption from the whiteboard of the common node). In which case, this agent
gathers with the other alive agent, and locates the exact segment in which the
earlier agent was exploring before its consumption by the black hole. After
locating this segment, both these agents starts performing Cautious-Walk
either in clockwise or counter-clockwise direction, based on the information
they gained about the earlier agents movement direction before getting
consumed by the black hole. The agents before getting consumed, marks each
node of their corresponding segment with different markings (i.e., more
precisely writes either left or right, after erasing the earlier direction
marking at the current node) based on the direction of their movement. So, the
two agents performing Cautious-Walk, search for the first node, which does not
have the direction marking w.r.to the direction the earlier consumed agent was
moving. This node which is devoid of this direction marking is indeed the
black hole node, and at least one agent, among the agents performing Cautious-
Walk detects it, and remains alive, which further perpetually explores the
ring $R$, avoiding this node.

Let us consider the three agents (say, $a_{1}$, $a_{2}$ and $a_{3}$) are
initially placed at three nodes of the ring $R$, which are not only safe nodes
but are also recognised as the $home$ of these agents. Initially, the agents
starting from their respective $home$ are assigned the task to explore a set
of nodes, which we term as a segment of the corresponding agents. More
precisely, a segment for an agent $a_{i}$ is defined as the set of consecutive
nodes, starting from its $home$ and ending at the nearest clockwise $home$
(i.e., the $home$ of first clockwise placed agent), which is also termed as
$Seg(a_{i})$. Note that $\cup^{3}_{i=1}Seg(a_{i})=R$. So if none of the agents
are ever destroyed the ring will still be perpetually explored.

Let us first discuss the case, in which we describe the possible movements of
the agent and the respective state changes they perform, until one agent gets
consumed by the black hole, and another agent gets to know that an agent is
already consumed by the black hole. After which, we will describe all the
possible movements and state changes performed by the remaining two alive
agent, between getting to know that already one has been consumed by the black
hole, and finally detecting the black hole position.

Initially all agents start from state Initial at their respective $home$. In
state Initial, an agent ( without loss of generality, say $a_{1}$) first
clears the already present data (if at all) at the whiteboards of their
respective $home$, then initializes $T_{time}=0$ ($T_{time}$ stores the number
of rounds elapsed since the start of state Initial), and writes a message of
the form (home, ID) at its $home$, where ID is the ID of the agent. This type
of message is termed as “home" type message, which consists of two components,
first component stores the message home and second component stores the ID of
the agent writing, i.e., ID of the agent whose $home$ is the $Current-Node$.
Further, it changes its state to Forward, and moves in clockwise direction.

In state Forward, the agent moves in clockwise direction while erasing the
earlier direction marking (if exists), i.e., left and then writes the new
direction marking, i.e., right in each node. The agent also increases the
$T_{time}$ variable by one in each round. This process continues until the
agent encounters a node which has a “home" type message. This “home" type
message signifies that the agent has reached the end of segment $Seg(a_{1})$,
i.e., in other words it has reached the nearest clockwise $home$, say $v_{c}$.
Note that the length of a segment can be at most $n-2$, hence within
$T_{time}=n-1$, an agent $a_{1}$ is bound to reach the last node of its own
segment i.e., $v_{c}$. In any case irrespective of the current $T_{time}$, the