Perpetual Exploration in Anonymous Synchronous Networks with a Byzantine Black Hole

$L,I_1,I_2$ and $F$ takes part in this step from the very first round of any phase, starting from $h$. In the first round, $L,I_1$ and $I_2$ moves to the next node. Then in the next round only $I_2$ returns back to home to meet with $F$. Note that, in this configuration the agents $L$, $I_1$, $I_2$ and $F$ are at two adjacent nodes while $F$ and $I_2$ are together and $L$ and $I_1$ are together on the same node. We call this particular configuration the pattern. We name the exact procedure as Make_Pattern.

After the pattern is formed in first two rounds of a phase, the agents translate the pattern to the next node until the agent $L$ reaches either at one end of the path graph $P$, or, reaches a node at a distance $2^i$ from $h$ in the $i$-th phase. Let, $v_0,v_1,v_2$ be three consecutive nodes on $P$, where, suppose $L$ and $I_1$ is on $v_1$ and $F$ and $I_2$ is on $v_0$. This translation of the pattern makes sure that after 5 consecutive rounds $L$ and $I_1$ is on $v_2$ and $F$ and $I_2$ is on $v_1$, thus translating the pattern by one node. We call these 5 consecutive rounds where the pattern translates starting from a set of 2 adjacent nodes, say $v_0,v_1$, to the next two adjacent nodes, say $v_1,v_2$, a sub-phase in the current phase. The description of the 5 consecutive rounds i.e., a sub-phase without the intervention of the BBH at $𝔟$ (such that $𝔟\in \{v_0,v_1,v_2\}$) are as follows.

Round 1:

$L$ moves to $v_2$ from $v_1$.

Round 2:

$I_2$ moves to $v_1$ from $v_0$ and $L$ moves to $v_1$ back from $v_2$.

Round 3:

$I_2$ moves back to $v_0$ from $v_1$ to meet with $F$. Also, $L$ moves back to $v_2$ from $v_1$.

Round 4:

$F$ and $I_2$ moves to $v_1$ from $v_0$ together.

Round 5:

$I_1$ moves to $v_2$ from $v_1$ to meet with $L$.

So after completion of round 5 the pattern is translated from nodes $v_0$, $v_1$ to $v_1$, $v_2$. The pictorial description of the translate pattern is explained in Fig. 1.

Now, suppose $v_2$ is the node upto which the pattern was supposed to translate at the current phase (or, it can be the end of the path graph also). So, when $L$ visits $v_2$ for the first time, in round 1 of some sub-phase it knows that it has reached the end of the path graph for the current phase. Then in the same sub-phase at round 2 it conveys this information to $I_2$ and $I_1$. In round 3 of the same sub-phase, $F$ gets that information from $I_2$. So at the end of the current sub-phase all agents has the information that they have explored either one end of the path graph or the node upto which they were supposed to explore in the current phase. In this case, they interchange the roles as follows: the agent which was previously had role $L$ changes role to $F$, the agent having role $F$ changes it to $L$, $I_1$ changes role to $I_2$ and $I_2$ changes role to $I_1$ (refer to Fig. 2). Then from the next sub-phase onwards they start translating the pattern towards $h$. It may be noted that, once $L$ (previously $F$) reaches $h$ in round 1 of a sub-phase, it conveys this information to the remaining agents in similar manner as described above. So, at round 5 of this current sub-phase, $F$ (previously $L$) and $I_2$ (previously $I_1$) also reaches $h$, and meets with $L$ (previously $F$) and $I_1$ (previously $I_2$). We name the exact procedure as Translate_Pattern.

Now we describe the behaviour of the agents while the BBH kills at least one exploring agent during create pattern or, during translate pattern. We first claim that, however the BBH intervenes while the four agents are executing creating pattern or translating pattern, there must exists at least one agent, say $A_{alive}$ which knows the exact location of the BBH. The justification of the claim is immediate if we do case by case studies fixing a BBH position and the round it is intervening with the agents. This can be during creating pattern or in a particular sub-phase of translating pattern. Now, there can be two cases:

Case-I:

Let $A_{alive}\in C_1$ ($C_1$ being the connected component of $G-𝔟$ that contains $h$) then it can perpetually explore every vertex in $C_1$ satisfying the requirement.

Case-II:

Let $A_{alive}\in C_2$ ($C_2$ being the connected component of $G-𝔟$ such that $h\notin C_2$). In this case $A_{alive}$ places itself to the adjacent node of the BBH on $C_2$. Let $T_i$ be the maximum time, required for the 4 agents (i.e., $L,I_1,I_2$ and $F$) to return back to $h$ in $i-$th phase if BBH does not intervene. Let us denote the aing agents at $h$, i.e., $a_4,a_5$ as $F_1,F_2$. Starting from the $i$-th phase, they wait for $T_i$ rounds for the other agents to return. Now, if the set of agents $L,I_1,I_2$ and $F$ fail to return back to home within $T_i$ rounds in phase, $i$, the agents $F_1$ and $F_2$ starts moving cautiously. In the cautious move, first $F_1$ visits the next node and in the next round, returns back to the previous node to meet with $F_2$, that was waiting there for $F_1$. If $F_1$ fails to return then $F_2$ knows the exact location of $𝔟$, which is the next node $F_1$ visited. In this case, $F_2$ remains in the component of $h$, hence can explore it perpetually. Otherwise, if $F_1$ returns back to $F_2$, then in the next round both of them moves together to the next node.

It may be noted that, $A_{alive}$ knows which phase is currently going on and so it knows the exact round at which $F_1$ and $F_2$ starts moving cautiously. Also, it knows the exact round at which $F_1$ first visits $𝔟$, say at round $r$. $A_{alive}$ waits till round $r-1$, and at round $r$ it moves to $𝔟$. Now at round $r$, if adversary activates $𝔟$, it destroys both $F_1$ and $A_{alive}$ then, $F_1$ fails to return back to $F_2$ in the next round. This way, $F_2$ knows the exact location of $𝔟$, while it remains in $C_1$. So it can explore $C_1$ by itself perpetually. The right figure in Fig. 3, represents the case where $L$ detects $𝔟$ at round $r_0+2$, and waits till round $r_1+3$. In the meantime, at round $r_1$ (where $r_1=r_0^{\prime }+T_i$, and $r_0^{\prime }$ is the first round of phase $i$), $F_1$ and $F_2$ starts moving cautiously. Notably, along this movement, at round $r_1+4$, $F_1$ visits $𝔟$, and at the same time $L$ as well visits $𝔟$ from $v_{j+3}$. The adversary activates $𝔟$, and both gets destroyed. So, at round $r_1+5$, $F_2$ finds failure of $F_1$’s return and understands the next node to be $𝔟$, while it is present in $C_1$. Accordingly, it perpetually explores $C_1$.

On the other hand, if at round $r$, adversary doesn’t activate $𝔟$, then $F_1$ meets with $A_{alive}$ and knows that they are located on the inactivated $𝔟$. In this case they move back to $C_1$ and starts exploring the component $C_1$, avoiding $𝔟$. The left figure in Fig. 3 explores this case, where $L$ detects the position of $𝔟$ at round $r_0+2$, and stays at $v_{j+3}$ until $r_1+3$, then at round $r_1+4$, when $F_1$ is also scheduled to visit $𝔟$, $L$ also decides to visit $𝔟$. But, in this situation, the adversary does not activate $𝔟$ at round $r_1+4$, so both $F_1$ and $L$ meets, gets the knowledge from $L$ that they are on $𝔟$. In the next round, they move to $v_{j+1}$ which is a node in $C_1$, where they meet $F_2$ and shares this information. After which, they perpetually explore $C_1$.

The correctness of the algorithm follows from the description of the algorithm and the case by case study of all possible interventions by the BBH. We have thus established the sufficiency part of Theorem 5.

For a fixed $\mathrm{\Delta }\ge 4$, we construct the corresponding graph class $𝒢$ by taking an underlying path $𝒫$, consisting of two types of vertices $\{v_i:1\le i\le \mathrm{\Delta }\}$ and, for each $i\le \mathrm{\Delta }$, the nodes $\{u_j^i:1\le j\le l_i\}$, where $l_i\ge 1$. The nodes $\{u_j^i\}$ form a subpath of length $l_i+1$ connecting $v_i$ to $v_{i+1}$. The nodes $v_i$ (for $\in \{1,2,\mathrm{\dots },\mathrm{\Delta }-1\}$) are special along $𝒫$, because they are connected to the BBH $𝔟$ either directly or via a new node $w_i$. Every node of $𝒫$, as well as $𝔟$, now completes its degree up to $\mathrm{\Delta }$ by connecting to at most $\mathrm{\Delta }-1$ trees of height $2$ (see example in Figure 4). Every node $w_i$ completes its degree up to $\mathrm{\Delta }$ by connecting to $\mathrm{\Delta }-2$ new nodes.

Note that, to reach $𝔟$ from a vertex of the form $u_j^i$, it is required to visit either $v_i$ or $v_{i+1}$. In the example of Figure 4, we have $\mathrm{\Delta }=4$, $l_1=l_2=2$ and $l_3=1$, so in $𝒫$ there are two vertices $u_1^1,u_2^1$ between $v_1$ and $v_2$, two vertices $u_1^2,u_2^2$ between $v_2$ and $v_3$, and one vertex $u_1^3$ between $v_3$ and $v_4$. In addition, $v_2$ is directly connected to $𝔟$ (or BBH) whereas $v_1$ and $v_3$ are connected to $𝔟$ via a path of length 2.

Given an algorithm $𝒜$ which claims to solve PerpExploration-BBH with $2\mathrm{\Delta }-2$ co-located agents, the adversary returns a port-labeled graph $G=(V,E,\lambda )\in 𝒢$ in which $𝒜$ fails, by choosing the lengths $l_i$ and the connection between $v_i$ and $𝔟$ (direct or through $w_i$). A high-level idea of the proof is as follows. First, it can be ensured that, $𝒜$ must instruct at least one agent to visit a node which is at 2 hop distance from $v_i$, for all $i\in \{1,2,\mathrm{\dots },\mathrm{\Delta }-1\}$. Let the agent which first visits a node which is at 2 hop distance from $v_i$, starts from $v_i$ at time $t_i$. Case-1: Now, based on $𝒜$, if at $t_i$, at least 2 agents are instructed to move from $v_i$ along the same port, then the adversary chooses a graph from $𝒢$, such that $v_i$ is connected to $𝔟$, and returns a port labeling, such that at $t_i+1$, these agents reach $𝔟$. Case-2: Otherwise, the adversary chooses a graph from $𝒢$ such that, either $v_i$ is connected to $𝔟$ or there exists an intermediate vertex $w_i$ connecting $v_i$ with $𝔟$. In this case also, the adversary returns the port labeling such that, the agent must move to $𝔟$ (or $w_i$) at $t_i+1$ and to some vertex $z$ (or $𝔟$) at $t_i^{\prime }$ (where $t_i^{\prime }>t_i+1$).

In addition, the graph chosen by the adversary sets the distance between $v_{i-1}$ and $v_i$ in a way to ensure that, within the time interval $[t_i,t_i^{\prime }]$, no agent from any $v_{\alpha }$ ($\alpha \in \{0,1,\mathrm{\dots },i-1\}$) attempts to visit $𝔟$. So, for Case-1, two agents directly gets destroyed. For Case-2, after the first agent is destroyed, remaining agents do not understand which among the next 2 nodes from $v_i$ is $𝔟$. Now, for $𝒜$ to succeed, at least one other agent from $v_i$ gets destroyed, at some round $t_i^{\prime \prime }$. This shows that from each $v_i$, for all $i\in \{1,2,\mathrm{\dots },\mathrm{\Delta }-1\}$ at least 2 agents each, are destroyed. Thus, $𝒜$ fails. $◀$

The members (or agents) in SG works in phases, where in each phase the movement of these agents are based on the algorithms Make_Pattern and Translate_Pattern (both of these algorithms are described in Section 3.2). Irrespective of which, the node that they choose to visit during making pattern or translating pattern is based on the underlying algorithm BFS-Tree-Construction.

More specifically, the $i$-th phase (for some $i>0$) is divided in two sub-phases: $i_1$-th phase and $i_2$-th phase. In the $i_1$-th phase, the members of SG makes at most $2^i$ translations, while executing the underlying algorithm BFS-Tree-Construction. Next, in the $i_2$-th phase, irrespective of their position after the end of $i_1$-th phase, they start translating back to reach $h$. After they reach $h$ during the $i_2$-th phase, they start $(i+1)$-th phase (which has again, ${(i+1)}_1$ and ${(i+1)}_2$ sub-phase). Note that, while executing $i_1$-th phase, if the members of SG reach $h$, in that case they continue executing $i_1$-th phase. We already know as per Section 3.2, each translation using Translate_Pattern requires 5 rounds and for creating the pattern using Make_Pattern it requires 2 rounds. This concludes that, it requires at most $T{i}_j=5\cdot 2^i+2$ rounds to complete $i_j$-th phase, for each $i>0$ and $j\in \{1,2\}$.

If at any point, along their traversal, the adversary activates the BBH, such that it interrupts the movement of SG. In that scenario, at least one member of SG must remain alive, exactly knowing the position of the BBH from its current node (refer to the discussion of Intervention by the BBH in Section 3.2 ). The agent (or agents) which knows the exact location of the BBH, stays at the node adjacent to the BBH, such that from its current node, it knows the exact port that leads to the BBH, or in other words they act as anchors with respect to one port, leading to the BBH. In particular, let us suppose, the agent holds the adjacent node of BBH, with respect to port $\alpha$ from BBH, then this agent is termed as Anchor($\alpha$).

These group members stay at $h$ with Marker, until the members of SG are returning back to $h$ in the $i_2$-th phase, for each $i>0$. If all members of SG do not reach $h$, in the $i_2$-th phase, i.e., within $T{i}_2$ rounds since the start of $i_2$-th phase, then the members of LG₀ start their movement.

Starting from $h$, the underlying movement of the members of LG₀ is similar to BFS-Tree-Construction, but while moving from one node to another they do not execute neither Make_Pattern nor Translate_Pattern, unlike the members of SG. In this case, if all members of LG₀ are currently at a node $u\in V$, then three lowest ID members of LG₀ become the explorers, they are termed as $E_1^0$, $E_2^0$ and $E_3^0$ in increasing order of their IDs, respectively. If based on the BFS-Tree-Construction, the next neighbor to be visited by the members of LG₀ is $v$, where $v\in N(u)$, then the following procedure is performed by the explorers of LG₀, before LG₀ finally decides to visit $v$.

Suppose at round $r$ (for some $r>0$), LG₀ members reach $u$, then at round $r+1$ both $E_2^0$ and $E_3^0$ members reach $v$. Next at round $r+2$, $E_3^0$ traverses to the first neighbor of $v$ and returns to $v$ at round $r+3$. At round $r+4$, $E_2^0$ travels to $u$ from $v$ and meets $E_1^0$ and then at round $r+5$ it returns back to $v$. This process iterates for each neighbor of $v$, and finally after each neighbor of $v$ is visited by $E_3^0$, at round $r+4\cdot ({\delta }_v-1)+1$ both $E_2^0$ and $E_3^0$ returns back to $u$. And in the subsequent round each members of LG₀ visit $v$. The whole process performed by $E_1^0$, $E_2^0$ and $E_3^0$ from $u$ is termed as Explore$(v)$, where $v$ symbolizes the node at which the members of LG₀ choose to visit from a neighbor node $u$. After the completion of Explore$(v)$, each member of LG₀ (including the explorers) visit $v$ from $u$. A pictorial description is explained in Fig. 5.

It may be noted that, if the members of LG₀ at the node $u$, according to the BFS-Tree-Construction algorithm, are slated to visit the neighboring node $v$, then before executing Explore$(v)$, the members of LG₀ checks if there exists an anchor agent blocking that port which leads to $v$. If that is the case, then LG₀ avoids visiting $v$ from $u$, and chooses the next neighbor, if such a neighbor exists and no anchor agent is blocking that edge. If no such neighbor exists from $u$ to be chosen by LG₀ members, then they backtrack to the parent node of $u$, and start iterating the same process.

From the above discussion we can have the following remark.

During the execution of Explore$(v)$ from $u$, the agent $E_3^0$ can face one of the following situations:

• $\mathrm{■}$

  It can find an anchor agent at $v$, acting as Anchor$(\beta )$, for some $\beta \in \{1,\mathrm{\dots },{\delta }_v\}$. In that case, during its current execution of Explore$(v)$, $E_3^0$ does not visit the neighbor of $v$ with respect to the port $\beta$.

• $\mathrm{■}$

  It can find an anchor agent at a neighbor $w$ (say) of $v$, acting as Anchor$({\beta }^{\prime })$, where ${\beta }^{\prime }\in \{1,\mathrm{\dots },{\delta }_w\}$. If the port connecting $w$ to $v$ is also ${\beta }^{\prime }$, then $E_3^0$ understands $v$ is the BBH, and accordingly tries to return to $u$, along the path $w\to v\to u$, and if it is able to reach to $u$, then it acts as an anchor at $u$, with respect to the edge $(u,v)$. On the other hand, if port connecting $w$ to $v$ is not ${\beta }^{\prime }$, then $E_3^0$ continues its execution of Explore$(v)$.

The agent $E_2^0$ during the execution of Explore$(v)$, can encounter one of the following situations, and accordingly we discuss the consequences that arise due to the situations encountered.

• $\mathrm{■}$

  It can find an anchor agent at $v$ where the anchor agent is not $E_3^0$, in which case it continues to execute Explore$(v)$.

• $\mathrm{■}$

  It can find an anchor agent at $v$ and finds the anchor agent to be $E_3^0$. In this case, $E_2^0$ returns back to $u$, where LG₁ is formed, where LG${}_1{}^{}={\text{LG}}_0\setminus \{E_3^0\}$. Next, the members of LG₁ start executing the same algorithm from $u$, with new explorers as $E_1^1$, $E_2^1$ and $E_3^1$.

• $\mathrm{■}$

  $E_2^0$ can find that $E_3^0$ fails to return to $v$ from a node $w$ (say), where $w\in N(v)$. In this case, $E_2^0$ understands $w$ to be the BBH, and it visits $u$ in the next round to inform this to remaining members of LG₀ in the next round, and then returns back to $v$, and becomes Anchor$(\beta )$, where $\beta \in \{1,\mathrm{\dots },{\delta }_v\}$ and $\beta$ is the port for $(v,w)$. On the other hand, LG₀ after receiving this information from $E_2^0$, transforms to LG₁ (where LG${}_1{}^{}={\text{LG}}_0\setminus \{E_2^0,E_3^0\}$) and starts executing the same algorithm, with $E_1^1$, $E_2^1$ and $E_3^1$ as new explorers.

Lastly, during the execution of Explore$(v)$ the agent $E_1^0$ can face the following situation.

• $\mathrm{■}$

  $E_2^0$ fails to return from $v$, in this situation $E_1^0$ becomes Anchor$(\beta )$ at $u$, where $\beta$ is the port connecting $u$ to $v$. Moreover, the remaining members of LG₀, i.e., LG${}_0{}^{}\setminus \{E_1^0,E_2^0,E_3^0\}$ forms LG₁ and they start executing the same algorithm from $u$, with new explorers, namely, $E_1^1$, $E_2^1$ and $E_3^1$, respectively.

For each $E_1^0$, $E_2^0$ and $E_3^0$, if they do not face any of the situations discussed above, then they continue to execute Explore$(v)$.

A pictorial explanation of two scenarios, of how an anchor settles at neighbor nodes of BBH is explained in Fig. 6.

In order to prove the correctness of the algorithm Graph_PerpExplore-BBH-Home, we give a brief sketch of the proof of the following theorem.

We first show that if $𝔟$ (i.e., BBH) never destroys any agent then the problem PerpExploration-BBH-Home is solved only by the four agents in SG (follows from the correctness of BFS-Tree-Construction). On the otherhand if BBH destroys any agent, then we prove that there exists an agent from SG acting as an anchor at a node in $N(𝔟)$, where $N(𝔟)$ indicates the neighbors of $𝔟$. The node can be either in $C_1$ or $C_j$, where $G-𝔟=C_1\cup \mathrm{\cdots }\cup C_t$ for some $t\ge 1$ and $home\in C_1$ and $j\ne 1$. Now if we assume, BBH destroys at least one agent then, we define a set $𝒰$ of nodes in $G$, where $𝒰\subseteq N(𝔟)\cap C_1$ such that no vertex in $𝒰$ contains an anchor. A node $u\in 𝒰$ ceases to exist in $𝒰$, whenever an agent visits $u$ and blocks the edge $(u,𝔟)$, by becoming an anchor. We show that during the execution of our algorithm, $𝒰$ eventually becomes empty. In addition to that, we also show that, the agents in LG_i (for some $i\ge 0$) never visit a node which is not in $C_1$. By LG_i visiting a node, we mean to say that all agents are located at that node simultaneously. This concludes that, all neighbors in $C_1$ of $𝔟$, gets anchored by an anchor agent. So, eventually all the agents, which are neither an anchor nor a Marker, can perpetually explore $C_1$. Also, to set up an anchor at each neighbor of $𝔟$, at most 2 agents are destroyed. So, this shows that $3(\mathrm{\Delta }-1)$ agents are required to anchor each neighbor of $C_1$ by the members of LG_i (for any $i\ge 0$). So, in total $3\mathrm{\Delta }+3$ agents are sufficient to execute Graph_PerpExplore-BBH-Home, including Marker, 4 agents in SG₀, and one agent which is neither a Marker nor an anchor, i.e., the one which perpetually explores $C_1$. Moreover, to execute BFS-Tree-Construction as stated in [2, Proposition 9], each agent requires $𝒪(n\mathrm{\Delta }\log n)$ memory. This concludes the proof. $◀$