Self-Stabilizing Weakly Byzantine Perpetual Gathering of Mobile Agents

Mobile agents, or simply agents, are software programs that can autonomously traverse a network, modeled as an undirected graph. We focus on the gathering problem which requires multiple agents, initially scattered throughout the network, to eventually terminate at a single node simultaneously. This problem is crucial for information exchange and enabling more complex behavior, and has been studied extensively [20].

In the literature, transient and Byzantine faults are considered in the gathering problem. The transient fault model involves temporary memory corruption, erroneous initialization, or other similar issues in faulty agents. To overcome transient faults, Ooshita, Datta, and Masuzawa [18] proposed a self-stabilizing algorithm that enables agents to gather from arbitrary (inconsistent) initial states, specifically addressing the gathering problem for two agents ($k=2$), known as the rendezvous problem. They also claim that the algorithm can be extended to a self-stabilizing algorithm for cases where $k\ge 2$, if $k$ is given to agents as global knowledge. In the Byzantine fault model, some agents incur Byzantine faults, which are called Byzantine agents, and they can behave arbitrarily against their algorithms; thus, this fault model includes other agent faults. In this paper, we assume that Byzantine agents cannot falsify their identifiers (IDs), which is a common assumption in many existing works. Byzantine agents under this restriction are sometimes referred to as weakly Byzantine agents in the literature, but we simply refer to them as Byzantine agents throughout this paper for simplicity. To tolerate Byzantine faults, many gathering algorithms [8, 11, 12] have been proposed. These algorithms require that agents initially know the number $n$ of nodes or a given upper bound $N$ on $n$. In particular, Dieudonné, Pelc, and Peleg [8] proposed an algorithm for the Byzantine environment if agents know $n$.

Both algorithms in [8] and [18] share a common characteristic: they require global knowledge of the network size or the number of agents to solve the problem. The authors in [18] show that without $k$, no self-stabilizing algorithm can solve the gathering problem. In the Byzantine fault model, it is unclear if the problem is solvable without $n$ or $F$. Additionally, although these faults have received much attention so far, to the best of our knowledge, no studies consider both fault models simultaneously for agent systems.

In this paper, we investigate the following questions: (1) is the gathering problem solvable in Byzantine environments without global knowledge of the network size or the number of (Byzantine) agents? (2) is there a self-stabilizing algorithm for the gathering problem? (3) if not, is there a relaxed variant of the gathering problem that allows the existence of the self-stabilizing algorithm?

For the first two questions, we demonstrate the following impossibility results for the gathering problem in Byzantine environments: (i) for any number of non-Byzantine agents, no algorithm can solve this problem without any global knowledge of the network size or the number of agents, and (ii) when $k\le 2f$, no self-stabilizing algorithm exists for this problem, even if agents know the number $n$ of nodes, the number $k$ of agents, the number $f$ of Byzantine agents, and the length ${\mathrm{\Lambda }}_g$ of the largest ID among IDs of non-Byzantine agents. Note that the impossibility proof for (i) is based on the scenario where only one non-Byzantine agent exists in the network, the agent should claim the termination of the algorithm. This assumption is common in fault-tolerant gathering problems (e.g., [8, 19]).

Based on these impossibilities, we propose a relaxed variant of the gathering problem, called perpetual gathering problem, in Byzantine environments. This problem requires that all non-Byzantine agents always be co-located from a certain time $t$ onwards. Unlike the original gathering problem, this does not require the agents to stay at a single node permanently from some time; they may move but must do so together along the same edge after time $t$. The term “perpetual gathering” is inspired by the famous “perpetual exploration” problem, where an agent repeatedly visits all nodes in the graph (cf. [6]).

For the perpetual gathering problem, if the agents know ${\mathrm{\Lambda }}_g$ and upper bounds $N,K,F$ on $n,k,f$, we propose a self-stabilizing algorithm for any $k$ and $f$ with time complexity of $O(K\cdot F\cdot {\mathrm{\Lambda }}_g\cdot X(N))$, where $X(n)$ represents the time required to visit all nodes in a $n$-nodes network. For example, $X(n)=O(n)$ [13] for a cycle, a clique, and a tree. For an arbitrary graph, $X(n)=n^5\log n$ [21]. When each node is equipped with a local memory (i.e., a whiteboard), $X(n)=O(m+nD)$, where $m$ is the number of edges and $D$ is the diameter of the graph [22].

Our results indicate that while no algorithm can solve the original self-stabilizing gathering problem for any $k$ and $f$, even with exact global knowledge of the network size and the number of agents, the self-stabilizing perpetual gathering problem can always be solved with just upper bounds on this knowledge. Note that the (non-self-stabilizing) perpetual gathering problem without global knowledge in Byzantine environments can be solved using an algorithm proposed by Dieudonné et al. [8]. If the termination detection mechanism is removed from this algorithm, global knowledge becomes unnecessary. In this case, agents continue to move, but after a certain time, all non-Byzantine agents meet at the same node. This can be interpreted as solving the perpetual gathering problem without global knowledge. We summarize our contribution and existing results in Table 1.

Many researchers considered rendezvous and gathering problems in various scenarios, such as synchrony, anonymity, network topology, randomness, and so on, and clarified the solvability. They also proposed various solutions to reduce various costs (e.g., time complexity, the number of moves, memory capacity, etc.). In this paper, we focus on deterministic solutions for rendezvous and gathering problems in the scenario where agents have unique IDs and move synchronously; Pelc [20] extensively surveyed these solutions, including those for anonymous agents and asynchronous environments. A comprehensive survey of the randomized solutions can also be found in the book by Alpern and Gal [1].

In such a scenario, the majority of the results are for fault-free settings. These results exploited agent IDs to break the symmetry. Several studies [7, 14, 23] proposed algorithms to solve rendezvous problems for arbitrary graphs if agents do not know the number of nodes $n$ and start with a delay of at most $\tau$ rounds. Dessmark et al. [7] presented the first deterministic algorithm, with polynomial time in $n$, $\tau$, and $\lambda$, where $\lambda$ is the length of the smallest ID among agent IDs. Kowalski and Malinowski [14] proposed an algorithm whose time complexity is independent of $\tau$ and is polynomial in $n$ and $\lambda$. Ta-Shma and Zwick [23] provided an algorithm with lower time complexity that is polynomial in $n$ and $\lambda$. Miller and Pelc [15] investigated tradeoffs between the number of rounds and the total number of edge traversals until the meeting.

Elouasbi and Pelc [9] introduced a new problem (called gathering with detection), which requires agents to declare the termination simultaneously when the meeting is perceived only through communication. They proposed an algorithm for this problem on arbitrary graphs in polynomial time in $n$ and $\lambda$ if agents use beeps as their communication method and do not know $n$. Bouchard et al. [4] considered a weaker model where each agent only detects the number of agents located at the same node in a round. They provided two types of algorithms to achieve the gathering with detection on arbitrary graphs in this model: one in polynomial time in $N$ and $\lambda$ when agents know the upper bound $N$ of $n$, and the other in exponential time in $n$ when agents do not know $n$. Molla et al. [17] proposed a faster algorithm to solve the gathering with detection on arbitrary graphs. Their algorithm is faster than the existing algorithms for even just gathering if agents do not know $n$ and start simultaneously, with polynomial time in $n$.

Recently, the gathering under various types of agent faults has been studied, particularly the gathering problem in the presence of Byzantine agents. This problem assumes that the network topology is arbitrary, there are $k$ agents, and $f$ of them are Byzantine. Studies addressing these problems considered two types of Byzantine agents: strongly and weakly Byzantine. Strongly Byzantine agents can ignore the algorithm and behave arbitrarily, while weakly Byzantine agents can do the same except falsify their own IDs. Dieudonné et al. [8] designed the first gathering algorithms to tolerate Byzantine agents. They proposed algorithms to solve the gathering for weakly Byzantine agents in polynomial time in $n$ and ${\mathrm{\Lambda }}_g$, where ${\mathrm{\Lambda }}_g$ is the length of the largest ID among IDs of non-faulty agents, both if agents know $n$ and $k\ge f+1$ holds, and if agents know the upper bound $F$ of $f$ and $k\ge 2F+2$ holds. These algorithms match the lower bounds on the number of non-faulty agents required. They also provided algorithms to solve the gathering for strongly Byzantine agents in exponential time in $n$ and ${\mathrm{\Lambda }}_g$, both if agents know $n$ and $F$ and $k\ge 3F+1$ holds, and if agents know $F$ and $k\ge 5F+2$ holds. However, the lower bounds in these cases are $F+1$ and $F+2$, respectively, which means that the required numbers of non-faulty agents required by these algorithms do not match these lower bounds. Bouchard et al. [2] improved the upper bounds to $k\ge 2F+1$ if agents know $n$ and $F$, and to $k\ge 2F+2$ if agents know $F$. Bouchard et al. [3] provided an algorithm that achieves the gathering in the presence of strongly Byzantine agents in polynomial time in $N$ and $\lambda$ if agents have global knowledge of $O(\log \log \log N)$ and $k\ge 5f^2+7f+2$ holds. Hirose et al. [11] shown a gathering algorithm that tolerates weakly Byzantine agents if agents know $N$ and $k\ge 4f^2+9f+4$ holds, with time complexity smaller than [8] and polynomial in $N$, $f$, and ${\mathrm{\Lambda }}_a$, where ${\mathrm{\Lambda }}_a$ is the length of the largest ID among agent IDs. Additionally, Hirose et al. [12] proposed a similar algorithm if agents know $N$ and $k\ge 9f+8$ holds, with time complexity greater than [11] but smaller than [8]. Tsuchida et al. [24] reduced the time complexity of the gathering algorithm to tolerate weakly Byzantine agents by assuming authenticated whiteboards, where each node has dedicated memory for each agent to leave information if agents know $F$ and $k\ge F$ holds. Their algorithm works in polynomial time in $F$ and $m$, where $m$ is the number of edges. Tsuchida et al. [25] showed an algorithm to solve the gathering problem in asynchronous environments with weakly Byzantine agents by using authenticated whiteboards. Miller and Saha [16] considered the case where agents can obtain information in the subgraph induced by nodes within a radius of the network from their current node. Their proposed algorithm solves the gathering problem in the presence of strongly Byzantine agents in polynomial time in $k$ and $n$ if $k\ge 2f+1$ holds.

Several studies looked at other types of agent faults. Chalopin et al. [5] studied delay faults, where faulty agents remain at the current node for a finite number of rounds regardless of their plans to move. Pelc [19] considered the gathering problem with crash faults, where some agents suddenly become immobile at the node in some round, for systems where each agent moves at constant speed but their speeds differ. Ooshita et al. [18] proposed a self-stabilizing algorithm to achieve the rendezvous when agents start with arbitrary states of their memory. This self-stabilizing algorithm guarantees that agents eventually meet at a single node even if their memory experiences any kind of corruption, i.e., it counteracts transient faults in agent memory.

The system is represented as a simple, connected, and undirected graph $G=(V,E)$ with $n=|V|$ nodes. Nodes have no ID. Each node $v\in V$ assigns unique port numbers in $\{1,\mathrm{\dots },d(v)\}$ to its edges, where $d(v)$ is the degree of $v$. Port numbers are local, meaning edges $(v,u)$ and $(u,v)$ for nodes $v$ and $u$ may have different numbers.

There are $k$ agents in the system, denoted by set $A$. Each agent $a\in A$ has a unique ID $a.id$ but knows only its own ID. We denote “an agent with an ID in an ID set $S_{id}$” as “an agent in $S_{id}$” for brevity. Agents have unbounded memory but cannot leave any information on nodes or edges. Among the $k$ agents, exactly $f$ are Byzantine, which means they can act arbitrarily but cannot falsify their IDs; thus, when a Byzantine agent $b$ communicates with another agent $a$, $a$ can correctly identify $b$’s ID. These agents are commonly referred to as weakly Byzantine agents and have been studied in the literature, including [8, 11, 12]. We call all the non-Byzantine agents good agents. We denote the length of the largest ID in IDs of good agents as ${\mathrm{\Lambda }}_g$.

An algorithm $𝒜$ for an agent $a$ is defined as $𝒜(a.id,n^{\prime },k^{\prime },f^{\prime },{\mathrm{\Lambda }}_g^{\prime })=(S,\delta ,s_{ini},S_{ter})$, where $S$ is a set of states, $\delta$ is a function for transitioning its state, $s_{ini}\in S$ is the special state, and $S_{ter}$ is a set of terminal states. Algorithm $𝒜$ takes five arguments, which are assigned integer values. The last four arguments correspond to $n,k,f$, and ${\mathrm{\Lambda }}_g$, and each value is assumed to be assigned if required by the algorithm. We refer to the arguments $n^{\prime },k^{\prime },f^{\prime }$ and ${\mathrm{\Lambda }}_g^{\prime }$ as global knowledge, and we assume that each of these arguments takes the same value for all agents in the system. In the above tuple, only the function $\delta$ depends on $a.id$, which means that the states of all agents are identical. States are represented by a tuple of variables of $a$; if its variables contain associative arrays, we refer to these simply as arrays. State $s_{ini}$ represents one where all variables of $a$ are initialized. A subset $S_{ter}$ will be defined later.

A configuration in the system is defined as a combination of the locations, the states, and the IDs of all agents in $A$. We define $C_{all}$ as the set of all possible configurations in which at least one good agent is not in a dormant state. An agent in a dormant state, or simply a dormant agent, transitions into $s_{ini}$ when (a) the adversary wakes up the dormant agent, or (b) a non-dormant agent visits the node with the dormant agent. Non-dormant agents execute a common algorithm in synchronous and discrete time steps, called rounds. We let $C_{ini}$ be a set of configurations in $C_{all}$ where each agent is either dormant or in $s_{ini}$.

In each round $r$, each non-dormant agent $a_i$ at $v$ performs the following operations sequentially:

1. (1)

   It acquires $d(v)$, the port number $p_{in}$ through which it arrived at $v$ in $r-1$ (if it stayed in $r-1$, $p_{in}=\perp$), and states of agents (including $a_i$) at $v$. We define ${\mathrm{𝑀𝐺}}_i$ as the set of $a_i$ and agents that $a_i$ observes at $v$ in $r$.

2. (2)

   It updates its next state $s^{\prime }$ using $\delta$ with $d(v)$, $p_{in}$, the states of all agents in ${\mathrm{𝑀𝐺}}_i$, and the arguments of $𝒜$, deciding whether to stay or leave, and determining the outgoing port $p_{out}$. If it decides to stay, $p_{out}=\perp$.

3. (3)

   It either stays at $v$ or moves to the destination node via $p_{out}$ by $r+1$.

Note that in Operation (1), every agent in ${\mathrm{𝑀𝐺}}_i$ has to share its states with others before any agent in ${\mathrm{𝑀𝐺}}_i$ computes $\delta$, but Byzantine agents in ${\mathrm{𝑀𝐺}}_i$ can falsify the values of their variables to others. We assume that all agents in ${\mathrm{𝑀𝐺}}_i$ observe the same state from any Byzantine agent in ${\mathrm{𝑀𝐺}}_i$, i.e., Byzantine agents share the same (possibly falsified) states with all co-located agents. This assumption is known as shouting and has been adopted in previous studies on Byzantine gathering (e.g., [2, 3, 8, 11, 12]). Without this assumption, a Byzantine agent could send different states to different co-located agents. This makes it significantly harder for co-located good agents to detect inconsistencies or coordinate their actions. Note also that in Operation (3), if two agents pass the same edge in opposite directions simultaneously, they do not notice this fact. If an agent enters a state in $S_{ter}$ at node $v$ in round $r$, $\delta$ outputs $p_{out}=\perp$ and $s^{\prime }\in S_{ter}$ in every round from $r$ onwards. Since the terminal states depend on the global knowledge, we sometimes denote $S_{ter}$ by $S_{ter}(n^{\prime },k^{\prime },f^{\prime },{\mathrm{\Lambda }}_g^{\prime })$ if needed. An execution starting from $c_0\in C_{all}$ is a sequence $c_0,c_1,c_2,\mathrm{\dots }$, such that each configuration at round $r$ is determined (deterministically) by applying the procedures described above to all the good agents and determining the behavior of the Byzantine agents by the adversary.

In the proposed algorithm, we incorporate a rendezvous algorithm as a subroutine to ensure that an agent meets other agents. This algorithm, due to Ta-Shma and Zwick [23], enables two agents to meet in any undirected and connected graph of $n$ nodes, starting from different nodes. We refer to this algorithm as $\mathrm{𝖱𝖤𝖭}(\mathrm{𝑙𝑎𝑏𝑒𝑙})$, where $\mathrm{𝑙𝑎𝑏𝑒𝑙}$ is a positive integer given as input. When an agent $a_i$ starts $\mathrm{𝖱𝖤𝖭}({\mathrm{𝑙𝑎𝑏𝑒𝑙}}_i)$ for some positive integer ${\mathrm{𝑙𝑎𝑏𝑒𝑙}}_i$, it alternates between exploring and waiting periods based on ${\mathrm{𝑙𝑎𝑏𝑒𝑙}}_i$. The agent executes an exploring algorithm using a universal exploration sequence, due to Reingold[21], during the exploring period and waits at the node for the duration required by the exploring algorithm during the waiting period. The scheduling of these periods ensures that two agents with different positive integers meet, typically when one agent waits while the other explores. When two agents with distinct positive integers ${\mathrm{𝑙𝑎𝑏𝑒𝑙}}_i$ and ${\mathrm{𝑙𝑎𝑏𝑒𝑙}}_j$ execute this procedure, this time complexity of $\mathrm{𝖱𝖤𝖭}(\mathrm{𝑙𝑎𝑏𝑒𝑙})$, denoted by $t_{\text{REN}}(\mathrm{𝑙𝑎𝑏𝑒𝑙})$, is $\tilde{O}(n^5\cdot \lambda )$, where $\lambda$ is the length of $\min ({\mathrm{𝑙𝑎𝑏𝑒𝑙}}_i,{\mathrm{𝑙𝑎𝑏𝑒𝑙}}_j)$, and $\tilde{O}$ hides a poly-logarithimic factor of $n$. We have the following theorem for this algorithm.

We denote the $t$-th round of $\mathrm{𝖱𝖤𝖭}(id)$ by $\mathrm{𝖱𝖤𝖭}(id,t)$ for integer $t\ge 0$.

In this section, we show that no algorithm solves the GAT without global knowledge. To establish this result, we prove that without global knowledge, an agent cannot visit all nodes of a ring and declare the termination. While this proof is well-known, we provide a rigorous proof for the result since it is critical for demonstrating the impossibility of solving the GAT.

In this section, we prove that no algorithm can solve SS-GAT with $n$, $k$, $f$, and ${\mathrm{\Lambda }}_g$.

We present the underlying idea of the proposed algorithm. We first show two solutions for the PGAT: one in non-Byzantine environments, where no Byzantine agents exist, and another in Byzantine environments. The latter solution is based on an idea by Dieudonné et al. [8]. We then extend the latter solution to solve the SS-PGAT. We assume that agents start from any of $C_{ini}$ when explaining the solutions for the PGAT.

To solve the PGAT in non-Byzantine environments, agents behave as follows: if an agent $a_i$ is alone at the current node, it starts $\mathrm{𝖱𝖤𝖭}(\mathrm{𝑠𝑒𝑒𝑑})$, using $a_i.id$ as the input $\mathrm{𝑠𝑒𝑒𝑑}$ for the rendezvous algorithm. Whenever $a_i$ meets other agents, $a_i$ stops the execution of the current rendezvous algorithm and starts it using the smallest ID among IDs in ${\mathrm{𝑀𝐺}}_i$ as $\mathrm{𝑠𝑒𝑒𝑑}$. According to Theorem 4, the number of agents traveling together grows, eventually ensuring that all good agents stay at the same node. However, this approach fails in a Byzantine environment. Consider a Byzantine agent $b$ with an ID smaller than the smallest ID among the good agent IDs. Agent $b$ repeatedly meets some good agents and leaves them. As a result, those good agents restart the rendezvous algorithm each time this action of $b$ occurs. Those good agents cannot meet the remaining good agents because this repeated restarting prevents uninterrupted execution for a sufficiently long period. Moreover, it is also ineffective for agents to record the IDs of previously left agents and then exclude those recorded IDs when selecting $\mathrm{𝑠𝑒𝑒𝑑}$. Agent $b$ could leave some good agents and then travel with the remaining good agents. This causes the good agents to divide into two groups.

This problem can be resolved using the idea of Dieudonné et al. [8]. This idea extends the approach in non-Byzantine environments by modifying the determination of $\mathrm{𝑠𝑒𝑒𝑑}$, as follows, to mitigate the influence of Byzantine agents. In this idea, a group is defined as a set of agents at a single node executing the rendezvous algorithm using the same $\mathrm{𝑠𝑒𝑒𝑑}$. To ignore Byzantine agents, when the group members change, the agents in the group compute the largest subset $S_b$ of agents at the current node such that every agent outside of $S_b$ has observed each member of $S_b$ leaving the group at some point in the past. Then, if the group meets agents neither in the group nor in $S_b$, or agents not in $S_b$ leave the group, the group stops the execution of the current rendezvous algorithm and starts it using the smallest ID among IDs in ${\mathrm{𝑀𝐺}}_i$ and not in $S_b$ as $\mathrm{𝑠𝑒𝑒𝑑}$.

In this paper, for future extensions, we represent this idea using a labeled graph $G_{CG}=(V_{CG},E_{CG})$, called confidence graph, where for an agent $a_i$, $|V_{CG}|=|{\mathrm{𝑀𝐺}}_i|$, each node label corresponds one-to-one with the ID of an agent in ${\mathrm{𝑀𝐺}}_i$, and each edge $(u,w)\in E_{CG}$ indicates that the two agents with the labels of nodes $u$ and $w$ trust each other. The detailed behaviors using this graph in each round are as follows: Agent $a_i$ first checks whether each agent $a_j$ at the current node is trustworthy. If $a_i$ detects fraud by $a_j$, $a_i$ does not trust $a_j$; otherwise, $a_i$ trusts $a_j$. Agent $a_i$ then simulates how $a_j$ would evaluate trust relationships. Once $a_i$ completes the above simulation for all agents in ${\mathrm{𝑀𝐺}}_i$, it derives the trust relationships among those agents in ${\mathrm{𝑀𝐺}}_i$. Next, $a_i$ maps the trust relationships onto a confidence graph and calculates the IDs reachable from the node with $a_i.id$ in the graph to determine the group members. If the group members change from the previous round, $a_i$ updates $\mathrm{𝑠𝑒𝑒𝑑}$; otherwise, it continues using the same $\mathrm{𝑠𝑒𝑒𝑑}$. This behavior ensures that good agents at the same node make the same confidence graph, as they base it on the states of agents at the same node at the beginning of the current round. Thus, good agents at the same node always select the same ID as $\mathrm{𝑠𝑒𝑒𝑑}$. Consequently, after meeting, good agents travel together, and eventually, all good agents stay at the same node from a certain round.

While this approach solves the PGAT without global knowledge, it cannot be directly applied to the SS-PGAT, as agents start from a configuration of $C_{all}$, that is, each agent may start with a different state. In cases where some good agents already have a memory of traveling together with other good agents in the initial configuration, they may never trust those agents. As a result, the good agents remain divided into several groups.

To address this issue, the proposed algorithm restricts the length $\tau$ of the period that an agent suspects the other agents. In the proposed algorithm, each agent derives $\tau$ from global knowledge. All good agents stop suspecting the other good agents after the first $\tau$ rounds. By appropriately setting $\tau$, we will prove that a good agent meets another good agent within $\tau$ rounds, i.e., before a Byzantine agent suspected by the good agent can regain the trust of the good agent. Thus, the proposed algorithm ensures that all good agents stay at the same node within $2\tau$ rounds.

Algorithm 1 outlines the behavior for each round of Algorithm ${𝒜}_{sspg}(id,n^{\prime },k^{\prime },f^{\prime },{\mathrm{\Lambda }}_g^{\prime })$ and uses Algorithms 2 and 4 as sub-routines. Tables 2 and 3 summarize the variables used by an agent $a_i$ in ${𝒜}_{sspg}(id,n^{\prime },k^{\prime },f^{\prime },{\mathrm{\Lambda }}_g^{\prime })$ and functions for arrays in ${𝒜}_{sspg}(id,n^{\prime },k^{\prime },f^{\prime },{\mathrm{\Lambda }}_g^{\prime })$, respectively. In ${𝒜}_{sspg}(id,n^{\prime },k^{\prime },f^{\prime },{\mathrm{\Lambda }}_g^{\prime })$, $i\in S_1$ for an index $i$ and an array $S_1$, and $j\in S_2$ for an index $j$ and a two-dimensional array $S_2$, indicates that $i$ is included in the indices of $S_1$ and $j$ is included in the indices of first dimension of $S_2$, respectively. Additionally, when an agent assigns a value $c$ to $S[i]$ for an array $S$ and a non-existent index $i$, we simply describe $S[i]\leftarrow c$. Each agent calculates $\tau =(6KF+1)\cdot t_{\text{REN}}(2^{{\mathrm{\Lambda }}_g+1})$ based on global knowledge $N$, $K$, $F$, and ${\mathrm{\Lambda }}_g$.

We focus on the process of each round by an agent $a_i$. First, $a_i$ increments the value of $a_i.\mathrm{𝑛𝑢𝑚𝑅𝑜𝑢𝑛𝑑}$ by one. If the value assigned to $a_i.\mathrm{𝑛𝑢𝑚𝑅𝑜𝑢𝑛𝑑}$ exceeds $t_{\text{REN}}(2^{{\mathrm{\Lambda }}_g+1})$, $a_i$ stores the value modulo $t_{\text{REN}}(2^{{\mathrm{\Lambda }}_g+1})$ in $a_i.\mathrm{𝑛𝑢𝑚𝑅𝑜𝑢𝑛𝑑}$. Next, using Algorithm 2, $a_i$ calculates the trust relationship of all agents in ${\mathrm{𝑀𝐺}}_i$. Then, using Algorithm 4, $a_i$ selects an ID $i{d}_{seed}$ as the input of the rendezvous algorithm and reaches a consensus on $\mathrm{𝑛𝑢𝑚𝑅𝑜𝑢𝑛𝑑}$ among agents in ${\mathrm{𝑀𝐺}}_i$ with the same $i{d}_{seed}$. This prevents them from staying at different nodes in the next round. Finally, using $a_i.\mathrm{𝑠𝑒𝑒𝑑}$ and $a_i.\mathrm{𝑛𝑢𝑚𝑅𝑜𝑢𝑛𝑑}$, $a_i$ executes a rendezvous algorithm to meet other good agents.

In this subsection, we prove the correctness and complexity of the algorithm proposed in Section 4. To do this, we first prove that two good agents at the same node make the same confidence graph. For simplicity of discussion, we define the time at $c_0\in C_{all}$ as round 1.

Owing to space limitations, several proofs have been omitted. The complete proofs are available in the full version of this paper [10].