1 Introduction↩︎

Consensus is a process where multiple agents agree to a common value. However, standard consensus protocols are vulnerable to adversarial agents that transmit false information to the network, potentially causing significant performance degradation or even failure. This has motivated extensive research on resilient consensus, which ensures consensus in the presence of adversaries [1]–[12].

Many works rely on Mean Subsequence Reduced (MSR)-type algorithms [1], [3], [8], [13]. In the algorithms, each non-adversarial (normal) agent discards some extreme values from its neighbors before updating its state, thereby ensuring that the updated value is not influenced by the adversaries. For many MSR-type algorithms to succeed, the communication graph is assumed to satisfy topological conditions called \(\textit{r-robustness}\) or \((r,s)\)-robustness, which are sufficient (and necessary) conditions for normal agents to achieve consensus within the convex hull of their initial values [1], [2].

A closely related problem is that of resilient leader-follower consensus, where a subset of agents (leaders) propagate a reference signal that the rest of the network (followers) aims to track, despite the presence of adversaries [4], [14], [15]. Resilient broadcasting problems have also been studied [2], [16], [17], where algorithms such as the Certified Propagation Algorithm (CPA) were proposed to enable trustworthy leader to reliably broadcast information despite the presence of faulty nodes. In [18], the authors addressed the problem of resilient distributed estimation by leveraging reliable agents that are directly connected to others. Additionally, [19] established conditions under which information can be resiliently transmitted from a set of source nodes to other nodes without direct access to the information.

These leader-follower results similarly depend on robustness conditions of the entire network. One of the most studied is the strong \(r\)-robustness [2], which roughly quantifies the redundant information flow from a designated subset of nodes to the rest of the network. This condition was later extended to time-varying graphs [4]. A related concept, termed \(r\) leader-follower robustness, was introduced in [7] for time-invariant networks, but it assumes there exists a trustworthy leader. More recently, the notion of joint \(r\)-robust following was proposed in [20], providing necessary and sufficient conditions for resilient leader-follower consensus in time-varying graphs with multi-hop communication. These robustness notions have served as the foundation for numerous future studies [21]–[25].

Despite these efforts, the system behavior under MSR algorithms in non-ideal settings — where these robustness conditions of the entire network fail — remains poorly understood. Some progress has been made in this direction for leaderless settings. For example,[26], [27] study community or cluster consensus, where multiple sets of agents converge to multiple distinct values when the robustness of the entire network is not sufficient. However, they also assume certain robustness within communities (clusters) and do not study cases where these conditions fail. In another line of work,[28] investigates the non-resiliency of a graph by examining the number of possible non-convergent nodes (agents that fail to reach consensus with any other nodes) when the network lacks sufficient robustness, but these results are limited to specific classes of graphs.

Contributions: This paper studies the behavior of multi-agent systems under insufficient network robustness for resilient leader-follower consensus in arbitrary time-varying graphs. Our main contributions are:

• We develop a novel Bootstrap Percolation and MSR (BP-MSR) algorithm, that guarantees partial resilient leader-follower consensus, where a subset of normal followers achieve consensus.

• We establish sufficient conditions for followers to achieve consensus via the BP-MSR algorithm. Unlike previous work [2], [4], [7], [20] that relies on robustness of the entire network to guarantee convergence of all followers, our conditions apply to each follower, focusing on convergence of individual followers.

• We validate our approach through simulations, showing that the BP-MSR algorithm guarantees partial resilient leader-follower consensus even when traditional resilient consensus algorithms fail to do so.

2 Preliminaries↩︎

We denote a simple time-varying digraph as \(\mathcal{G}[t] = (\mathcal{V},\mathcal{E}[t])\) where \(\mathcal{V}\) and \(\mathcal{E}[t]\) are the finite vertex set and the time-varying directed edge set, respectively. We also denote \(\mathbb{G}=(\mathcal{G}[t])_{t\in \mathbb{Z}_{\geq 0}}\) as a sequence of time-varying graphs. Within the set \(\mathcal{V}\), we have leaders \(\mathcal{L}=\{1,\dots, l\} \subset \mathcal{V}\) that propagate the reference state according to the same function \(f_r:\mathbb{Z}_{\geq 0} \to \mathbb{R}\) to followers \(\mathcal{F} = \{l+1,\dots, n\} = \mathcal{V} \setminus \mathcal{L}\). We denote \(|\mathcal{L}|=l\) and \(|\mathcal{F}|=f\). A directed edge \((i,j)\in \mathcal{E}[t]\) indicates that agent \(j\) is able to receive information from agent \(i\) at time \(t\). This implies agent \(i\) is an in-neighbor of agent \(j\), and agent \(j\) is an out-neighbor of agent \(i\). The in-neighbor and out-neighbor sets of agent \(i\) are denoted as \(\mathcal{N}_i[t] =\{j\in \mathcal{V} \;|\; (j,i) \in \mathcal{E}[t]\}\) and \(\mathcal{N}_i^o[t] =\{j\in \mathcal{V} \;|\; (i,j) \in \mathcal{E}[t]\}\), respectively. The extended in-neighbor set is given as \(\mathcal{B}_i[t] = \mathcal{N}_i[t]\cup \{i\}\). We denote the cardinality of a set \(\mathcal{S}\) as \(|\mathcal{S}|\). We denote the set of non-negative and positive integers as \(\mathbb{Z}_{\geq 0}\) and \(\mathbb{Z}_{>0}\).

2.1 Bootstrap Percolation↩︎

At a fixed time step \(t\in \mathbb{Z}_{\geq 0}\), bootstrap percolation (BP) models the spread of activation of nodes of \(\mathcal{G}[t]\) from a set of initial active nodes \(\mathcal{L}\subset \mathcal{V}\), given user-defined threshold \(r\in \mathbb{Z}_{>0}\) [29]. In BP, each node is either active or inactive. At each iteration of BP, each agent \(i \in \mathcal{V}\) becomes active if it has at least \(r\) active neighbors and remains active until the process terminates, which happens after at most \(f\) iterations.

We modify BP process slightly such that each agent’s update occurs locally. Formally, let \(q_i[t,k]\in \{0,1\}\) be the true activation state of node \(i\) at time \(t\) and BP iteration \(k\in \{0,\dots, f\}\), where \(q_i[t,k]=1\) if active and inactive otherwise. Also, let \(q_i^j[t,k]\) be the activation state of agent \(i\) received by agent \(j\). For \(k\in\{1,\dots,f\}\), agent \(i\) shares its activation state \(q_i[t,k]\) with its out-neighbors and updates as \[q_i[t,k]= \begin{cases} 1 & \text{if q_i[t,k-1]=1},\\ 1 & \text{if \sum_{j \in \mathcal{N}_i[t]} q_j^i[t,k-1]\geq r},\\ 0 & \text{if \sum_{j \in \mathcal{N}_i[t]} q_j^i[t,k-1] < r}, \end{cases} \label{eq:percolation}\tag{1}\] where \(q_i[t,0]=1\) \(\forall i \in \mathcal{L}\) and \(q_i[t,0]=0\) \(\forall i \in \mathcal{F}\). For brevity, we denote \(q_i[t]:=q_i[t,f]\).

2.2 Resilient Consensus↩︎

We review resilient leader-follower consensus when agents cannot distinguish between leaders and followers. Let \(x_i[t]\in \mathbb{R}\) denote the consensus state of agent \(i\) at time \(t\), and \(x_i^j[t]\) the copy received by agent \(j\). Each agent \(i\) shares \(x_i[t]\) with its out-neighbors and updates \[x_i[t+1]= \begin{cases} f_r[t], & i\in \mathcal{L}, \\ \sum_{j\in \mathcal{B}_i[t]} w_{ij}[t]x_j^i[t], & i \in \mathcal{F}, \end{cases} \label{eq:linear}\tag{2}\] where \(w_{ij}[t]\) is the weight assigned to \(x_j^i[t]\) by agent \(i\). We assume \(\exists \alpha \in(0,1)\) such that \(\forall i \in \mathcal{V}\),

• \(w_{ij}[t]\geq \alpha\) if \(j\in \mathcal{B}_i[t]\), or \(w_{ij}[t]=0\) otherwise,

• \(\sum_{j=1}^n w_{ij}[t]=1\).

However, as shown in [30], the protocol 2 does not guarantee consensus with adversaries, which we define below:

The adversaries in this paper are a slight modification of the well-known Byzantine agents [1], [4]: each \(a\in \mathcal{A}\) may manipulate both its consensus state \(x_a^u[t]\) and activation state \(q_a^u[t,k]\). Both followers and leaders can be adversaries. Non-adversarial agents are called normal agents. We denote \(\mathcal{A}\) as the set of adversaries and \(\mathcal{M}= \mathcal{V}\setminus \mathcal{A}\) as the set of normal agents, with \(\mathcal{F}_{\mathcal{M}} = \mathcal{F}\cap \mathcal{M}\neq \emptyset\) and \(\mathcal{L}_{\mathcal{M}} = \mathcal{L}\cap \mathcal{M}\neq \emptyset\).

Hence, an adversary cannot (i) transmit non-binary values or (ii) switch \(q_a^u[t,k]\) from \(1\) to \(0\) during BP process. These are direct violations of 1 that would lead to detections, which adversaries would try to avoid. In addition, we consider the following scope of threat:

In response to adversaries, works like  [4], [7], [20], [30] studied how to achieve full resilient leader-follower consensus, whose definition is as follows:

Their results, however, hold only under certain topological conditions specified below.

If a network is strongly \((2F+1)\)-robust with respect to \(\mathcal{L}\) \(\forall t\in \mathbb{Z}_{\geq 0}\), then followers in \(\mathcal{F}_{\mathcal{M}}\) achieve full resilient leader-follower consensus via the W-MSR algorithm [30]. This was later extended to incorporate a union of time-varying graphs over a time horizon in [4]. Similar conditions appear in [7], [20]. However, in contrast to those conditions, there exists a useful result in regard to strong \(r\)-robustness:

3 Problem Statement↩︎

Much of the existing work on resilient leader-follower consensus [4], [7], [20] relies on the assumption that the entire network always satisfies certain topological robustness conditions. In general, these conditions require dense network structures which might be difficult to maintain in practice. Therefore, our goal is to study the system’s behavior over an arbitrary sequence of graphs, even when robustness conditions are not met.

To this end, rather than focusing on full resilient leader-follower consensus, where all normal followers are required to converge, we introduce the notion of partial resilient leader-follower consensus:

Although adversaries may manipulate both their consensus and activation states, our focus is on the convergence of the consensus states. That is, we do not require the activation states received by a normal agent to be correct. Nevertheless, as we demonstrate in later sections, how adversaries share their activation states influence which followers ultimately achieve convergence (see 4.2).

We now formally state our problem:

4 Partial Resilient Leader-Follower Consensus↩︎

Consider a network \(\mathcal{G}[t]=(\mathcal{V}, \mathcal{E}[t])\) that fails to be strongly \(r\)-robust at time \(t\). Since robustness conditions are defined over the entire network topology, that implies there exists a nonempty subset \(\mathcal{F}_{\mathcal{W}}[t] \subset \mathcal{F}\) whose members lack sufficient connections to satisfy the robustness conditions. However, the remaining followers in \(\mathcal{F}_{\mathcal{R}}[t]=\mathcal{F}\setminus \mathcal{F}_{\mathcal{W}}[t]\) (if nonempty) are indeed sufficiently connected. In other words, the subgraph induced by a set \(\mathcal{L}\cup \mathcal{F}_{\mathcal{R}}[t]\subseteq \mathcal{V}\) is strongly \(r\)-robust with respect to \(\mathcal{L}\). Using this observation, we propose a novel distributed algorithm, which we refer to as the BP-MSR algorithm.

The key idea of the BP-MSR algorithm is that agents engage in a consensus update only at time \(t\) when they can locally verify that they belong to strongly \(r\)-robust subgraphs. For each \(t\geq \mathbb{Z}_{\geq 0}\), all agents \(i\in \mathcal{M}\) first compute their activation states \(q_i[t]\) synchronously via BP 1 with \(r=2F+1\) (lines 3-8). Then, leaders \(i\in \mathcal{L}\) transmit their states and update them using \(f_r\) (lines 9-11), while followers \(i\in \mathcal{F}\) use \(q_i[t]\) to locally decide whether to engage in consensus protocol synchronously (lines 12-21). If \(q_i[t]=1\), i.e., followers \(i\) belong to a strongly \((2F+1)\)-robust subgraph with respect to \(\mathcal{L}\cup \mathcal{A}\) at time \(t\) (shown in 2), they transmit \(x_i[t]\) and update \(x_i[t+1]\) via the W-MSR algorithm; otherwise, they remain inactive for that time.

4.1 Analysis of the BP-MSR Algorithm↩︎

Now, we present the analysis for our algorithm.

By definition of \(\mathcal{F}_{\mathcal{R}}[t]\), for all \(i\in\mathcal{F}_{\mathcal{R}}[t]\) the following inequality must hold: \(\sum_{j \in \mathcal{N}_i[t]\setminus \mathcal{A}} q_j^i[t,f-1] + \sum_{a \in \mathcal{A}} q_a^i[t,f-1] \geq 2F+1\). Because \(q_a^i[t,k]\in \{0,1\}\) for all \(a \in \mathcal{A}\), \(i \in \mathcal{M}\), and \(k\in[0,f]\) by 1, setting \(q_a^i[t,k]=1\) for all \(a\in \mathcal{A}\), \(i\in \mathcal{M}\), and \(k\in[0,f]\) would still ensure the inequality. Note setting \(q_a^i[t,k]=1\) for all \(i \in \mathcal{M}\) and \(k\in[0,f]\) is equivalent to making an adversary \(a\in \mathcal{A}\) a leader at time \(t\). Then, applying 1 with the threshold \(r=2F+1\) and initial set \(\mathcal{L}\cup \mathcal{A}\), \(\mathcal{G}_{\mathcal{R}}[t]\) is strongly \((2F+1)\)-robust with respect to \(\mathcal{L}\cup \mathcal{A}\).

The lemma shows that, through lines 3-8 of the BP-MSR algorithm, each follower \(i \in \mathcal{F}_{\mathcal{M}}\) can use \(q_i[t]\) to locally determine whether it belongs to a strongly \((2F+1)\)-robust subgraph with respect to \(\mathcal{L}\cup \mathcal{A}\) at time \(t\). This local verification step enables each follower to decide whether to participate in the consensus in later parts of the algorithm (lines 12-21). Now, let \(m[t] = \min_{i \in \mathcal{M}} x_i[t]\) and \(M[t] = \max_{i \in \mathcal{M}} x_i[t]\) be the minimum and maximum states of normal agents at time \(t\), respectively. Then, we have:

First Claim: Here we show that \(x_i[t] \in [m[t_C], M[t_C]]\) \(\forall i \in \mathcal{F}_{\mathcal{M}}\) \(\forall t \geq t_C\). Let \(\mathcal{F}_{\mathcal{R}}[t] = \{i \in \mathcal{F}_{\mathcal{M}} \mid q_i[t]=1\}\). Note at each time \(t\geq t_C\), only \(i\in \mathcal{F}_{\mathcal{R}}[t]\) updates its value \(x_i[t+1]\) with their in-neighbors’ states. If \(i \notin \mathcal{F}_{\mathcal{R}}[t]\), then \(x_i[t+1]=x_i[t]\in [m[t], M[t]]\). Now consider the case where \(|\mathcal{F}_{\mathcal{R}}[t]|\neq 0\) and \(i\in \mathcal{F}_{\mathcal{R}}[t]\). Let \(\mathcal{G}_{\mathcal{R}}[t] = (\mathcal{V}_{\mathcal{R}}[t], \mathcal{E}_{\mathcal{R}}[t])\) be a subgraph of \(\mathcal{G}[t]\) induced by \(\mathcal{V}_{\mathcal{R}}[t]= \mathcal{A}\cup \mathcal{L}\cup \mathcal{F}_{\mathcal{R}}[t]\), which is strongly \((2F+1)\)-robust with respect to \(\mathcal{L}\cup \mathcal{A}\) by 2. Also, because follower \(i \in \mathcal{F}_{\mathcal{R}}[t]\) has \(|\mathcal{N}_i[t]\cap \mathcal{A}|\leq F\) by the definition of \(F\)-local model, \(|\mathcal{N}_i[t]\cap\mathcal{F}_{\mathcal{R}}[t]\setminus \mathcal{A}|\geq F+1\). Then if an adversary \(a\in \mathcal{A}\) has a value \(x_a^i[t]> M[t]\) or \(x_a^i[t]<m[t]\), it will be filtered out, since it is one of the highest or lowest values in \(\mathcal{H}_i[t]\) or \(\mathcal{O}_i[t]\). Hence, all values outside the interval \([m[t], M[t]]\) will be excluded from the update. Then, follower \(i\) performs a convex combination of values within \([m[t], M[t]]\) to update \(x_i[t+1]\), which implies \(x_i[t+1] \in [m[t], M[t]]\). Lastly, \(x_i[t]=C_r \in [m[t], M[t]]\) for all \(i \in \mathcal{L}_\mathcal{M}\) and \(t\geq t_C\). Since \(x_i[t+1] \in [m[t], M[t]]\) for all \(i\in \mathcal{M}\) and \(t\geq t_C\), \(x_i[t+1] \in [m[t+1], M[t+1]]\subseteq [m[t], M[t]] \subseteq \cdots \subseteq [m[t_C], M[t_C]]\).

Second Claim: [Monotonicity of Convergent Followers]

Given a sequence \(\mathbb{G}\), \(\mathcal{F}_{\mathcal{C}}\) is fixed and known. Let \(\mathcal{F}_{\mathcal{C}}' = \mathcal{F}_{\mathcal{M}} \setminus \mathcal{F}_{\mathcal{C}}\) and \(\mathcal{M}_{\mathcal{C}} = \mathcal{M}\setminus \mathcal{F}_{\mathcal{C}}'\). Then, \(\forall i \in \mathcal{F}_{\mathcal{C}}' \; \exists \bar t_i\geq t_C\) such that \(q_i[t]=0 \;\forall t \geq \bar t_i\). Now we define \(\overline{m}[t]=\min_{i \in \mathcal{M}_{\mathcal{C}}} x_i[t]\) and \(\overline{M}[t]=\max_{i \in \mathcal{M}_{\mathcal{C}}} x_i[t]\) as the minimum and maximum states of normal agents in \(\mathcal{M}_{\mathcal{C}}\) at time \(t\). We first show that there exists a finite time \(\bar t \geq t_C\) such that \(x_i[t] \in [\overline{m}[\bar t],\overline{M}[\bar t]]\) for all \(i \in \mathcal{F}_{\mathcal{C}}\) and \(\forall t \geq \bar t\). Let \(\bar t = \max_{i\in \mathcal{F}_{\mathcal{C}}'} t_i<\infty\) be the time where \(q_i[t]=0\) \(\forall i \in \mathcal{F}_{\mathcal{C}}'\) \(\forall t \geq \bar t\). By definition, all followers \(i \in \mathcal{F}_{\mathcal{C}}'\) do not transmit their states to its out-neighbors for all \(t\geq \bar t\), which implies removing the nodes in \(\mathcal{F}_{\mathcal{C}}'\) from the graph \(\mathcal{G}[t]\) for \(t\geq \bar t\) does not affect our analysis on the states of \(\mathcal{F}_{\mathcal{C}}\). Then, applying the same reasoning as in the proof for the first claim, we have \(x_i[t] \in [\overline{m}[t],\overline{M}[t]]\subseteq \cdots \subseteq [\overline{m}[\bar t],\overline{M}[\bar t]]\) for all \(i \in \mathcal{F}_{\mathcal{C}}\) and \(t \geq \bar t\).

[Partial Leader-Follower Consensus] We define \[\begin{align} \mathcal{X}_M(t, \overline{\epsilon}) &= \{i \in \mathcal{F}_{\mathcal{C}} \mid x_i[t]> \overline{M}[t] - \overline{\epsilon}\}, \\ \mathcal{X}_m(t, \underline{\epsilon})& = \{i \in \mathcal{F}_{\mathcal{C}} \mid x_i[t]< \overline{m}[t] + \underline{\epsilon}\},\\ \mathcal{S}_X(t, \underline{\epsilon},\overline{\epsilon}) & = \mathcal{X}_M(t,\overline{\epsilon})\cup \mathcal{X}_m(t, \underline{\epsilon}). \end{align}\] We now show that \(|\mathcal{S}_X(t, \underline{\epsilon},\overline{\epsilon})|\) decreases as \(t\to \infty\) with some choices of \(\underline{\epsilon}\) and \(\overline{\epsilon}\).

Recall that \(\mathcal{G}_{\mathcal{R}}[t] = (\mathcal{V}_{\mathcal{R}}[t], \mathcal{E}_{\mathcal{R}}[t])\) is the subgraph induced by \(\mathcal{V}_{\mathcal{R}}[t]= \mathcal{L}\cup \mathcal{A}\cup \mathcal{F}_{\mathcal{R}}[t]\), where \(\mathcal{F}_{\mathcal{R}}[t] = \{i \in \mathcal{F}_{\mathcal{M}} \mid q_i[t]=1\}\). If \(|\mathcal{F}_{\mathcal{R}}[t]|>0\), by 2, \(\mathcal{G}_{\mathcal{R}}[t]\) is strongly \((2F+1)\)-robust with respect to \(\mathcal{L}\cup \mathcal{A}\). For all \(t\geq \bar t\) such that \(|\mathcal{F}_{\mathcal{R}}[t]|>0\), \(\mathcal{F}_{\mathcal{C}}\cap \mathcal{F}_{\mathcal{R}}[t]\neq \emptyset\) and \(\mathcal{F}_{\mathcal{C}}'\cap \mathcal{F}_{\mathcal{R}}[t]=\emptyset\). Let \(t'\geq \bar t\) be the earliest time where \(|\mathcal{F}_{\mathcal{R}}[t']|>0\). Note that \(t'<\infty\) as \(|\mathcal{F}_{\mathcal{C}}|>0\). We define \(\underline{\epsilon} = C_r - \overline{m}[t']\) and \(\overline{\epsilon} = \overline{M}[t'] - C_r\).

We first define a set of all followers who are adjacent to at least \(F+1\) normal leaders in the sequence \(\mathbb{G}\) at any time \(t\geq t'\): \(\mathcal{F}_{\mathcal{L}} = \{i_1 \in \mathcal{F}_{\mathcal{C}} \mid \exists t_1\geq t'\;\text{ s.t. } i_1 \in \mathcal{F}_{\mathcal{R}}[t'+t_1], \;|\mathcal{N}_{i_1}[t'+t_1]\cap \mathcal{L}_{\mathcal{M}}|\geq F+1\}\). By definitions of strong \((2F+1)\)-robustness and \(F\)-local model, for all \(t\geq t_C\) such that \(|\mathcal{F}_{\mathcal{R}}[t]|>0\), there must exist \(i_1 \in \mathcal{F}_{\mathcal{R}}[t]\cap \mathcal{F}_{\mathcal{L}}\). Since \(\mathcal{F}_{\mathcal{C}}\) is finite and \(\mathcal{F}_{\mathcal{L}} \subseteq \mathcal{F}_{\mathcal{C}}\), there must exist a finite \(T_1 \geq 1\) such that \(\mathcal{F}_{\mathcal{L}} \subseteq \bigcup_{t_1=0}^{T_1-1} \mathcal{F}_{\mathcal{R}}[t'+t_1]\). Therefore, for any \(t_1\in [0, T_1-1]\) where \(|\mathcal{F}_{\mathcal{R}}[t'+t_1]|>0\), \(\mathcal{S}_{1,t_1}=\{i_1 \in \mathcal{F}_{\mathcal{C}} \mid \mathcal{N}_{i_1}[t'+t_1]\cap \mathcal{L}_{\mathcal{M}}|\geq F+1\}\) is nonempty. Then, through the BP-MSR algorithm, follower \(i_1\) will use at least one \(C_r\) to update \(x_{i_1}[t'+t_1+1]\).

Due to the monotonicity of the convergent agents’ states, we know \(x_i[t]\in [\overline{m}[t'],\overline{M}[t']]\) for all \(i\in \mathcal{F}_\mathcal{C}\) and \(t\geq t'\). To bound agent \(i_1\)’s state at time \(t'+t_1+1\), we assume the minimum weight possible \(\alpha\) is put on \(C_r\), and the maximum weight is put on \(\overline{m}[t']\) and \(\overline{M}[t']\). Then, we get \[\begin{align} x_{i_1}[t'+t_1+1] & \geq \alpha C_r + (1-\alpha) \overline{m}[t'] \geq \overline{m}[t'] + \alpha\underline{\epsilon}, \end{align}\] \[\begin{align} x_{i_1}[t'+t_1+1] & \leq \alpha C_r + (1-\alpha) \overline{M}[t'] \leq \overline{M}[t'] - \alpha \overline{\epsilon}. \end{align}\] Extending these bounds to time \(t'+T_1\), we get: \[\begin{align} x_{i_1}[t'+t_1+2] & \geq \alpha x_{i_1}[t'+t_1+1] + (1-\alpha) \overline{m}[t'] \\ & \geq \overline{m}[t'] + \alpha^2 \underline{\epsilon}, \\ x_{i_1}[t'+t_1+3] & \geq \alpha x_{i_1}[t'+t_1+ 2] + (1-\alpha) \overline{m}[t'] \\ & \geq \overline{m}[t'] + \alpha^3 \underline{\epsilon}, \\ & \vdots \\ x_{i_1}[t'+t_1+k] & \geq \alpha x_{i_1}[t'+t_1+k-1] + (1-\alpha) \overline{m}[t'] \\ & \geq \overline{m}[t'] + \alpha^{k} \underline{\epsilon}, \end{align}\] and \[\begin{align} x_{i_1}[t'+t_1+2] & \leq \alpha x_{i_1}[t'+t_1+1] + (1-\alpha) \overline{M}[t'] \\ & \leq \overline{M}[t'] - \alpha^2 \overline{\epsilon},\\ x_{i_1}[t'+t_1+3] & \leq \alpha x_{i_1}[t'+t_1+2] + (1-\alpha) \overline{M}[t'] \\ & \leq \overline{M}[t'] - \alpha^3 \overline{\epsilon},\\ & \vdots \\ x_{i_1}[t'+t_1+k] & \leq \alpha x_{i_1}[t'+t_1+k-1] + (1-\alpha) \overline{M}[t'] \\ & \leq \overline{M}[t'] - \alpha^{k} \overline{\epsilon}. \end{align}\] This holds for \(0\leq t_1< t_1+k\leq T_1\). Let \(\mathcal{K}_1 =\{i_1 \in \mathcal{F}_{\mathcal{C}}\mid x_{i_1}[t'+T_1] \in [\overline{m}[t']+\alpha^{T_1}\underline{\epsilon}, \overline{M}[t']-\alpha^{T_1}\overline{\epsilon}]\}\). Since \(\alpha \in [0,1]\), we have \(x_{i_1}[t'+T_1] \in [\overline{m}[t'] +\alpha^{T_1} \underline{\epsilon}, \overline{M}[t'] -\alpha^{T_1} \overline{\epsilon}] \;\forall i_1 \in \mathcal{S}_1 = \cup_{t_1=0}^{T_1-1} \mathcal{S}_{1,t_1}\). Then, because (i) \(\mathcal{S}_1\neq \emptyset\) , (ii) \(\mathcal{S}_1 \subseteq \mathcal{K}_1\), and (iii) \(\mathcal{S}_1 \subseteq \mathcal{F}_{\mathcal{C}}\), \(|\mathcal{S}_X(t'+T_1, \alpha^{T_1}\underline{\epsilon},\alpha^{T_1}\overline{\epsilon})|< |\mathcal{F}_{\mathcal{C}}|\).

We now show that there exists a finite \(T_2 \geq T_1+1\) such that \(|\mathcal{S}_X(t'+T_2, \alpha^{T_2}\underline{\epsilon},\alpha^{T_2}\overline{\epsilon})|<|\mathcal{S}_X(t'+T_1, \alpha^{T_1}\underline{\epsilon},\alpha^{T_1}\overline{\epsilon})|\). Let \(\mathcal{K}_2 =\{i_2 \in \mathcal{F}_{\mathcal{C}}\mid x_{i_2}[t'+T_2] \in [\overline{m}[t']+\alpha^{T_2}\underline{\epsilon}, \overline{M}[t']-\alpha^{T_2}\overline{\epsilon}]\}\). Let \(\mathcal{D}_{i_2}[t'+t_2] = \mathcal{N}_{i_2}[t'+t_2]\cap\mathcal{F}_{\mathcal{R}}[t'+t_2] \setminus \mathcal{S}_X(t'+t_2, \alpha^{t_2}\underline{\epsilon},\alpha^{t_2}\overline{\epsilon})\) for any \(t_2 \in [T_1,T_2-1]\). First, we characterize \(T_2\): let \(T_2\geq T_1+1\) be the earliest time such that \(\mathcal{K}_1 \subseteq \mathcal{K}_2\). Because all \(i \in \mathcal{F}_{\mathcal{M}}\) always use their own states to update, the bounds on the states of followers \(i_1 \in \mathcal{K}_1\) for \(t \in [t'+t_2+1, T_2]\) are: \[\begin{align} x_{i_1}[t'+t_2+1] & \geq \alpha x_{i_1}[t'+t_2] + (1-\alpha) \overline{m}[t'] \nonumber \\ & \geq \overline{m}[t'] + \alpha^{t_2+1} \underline{\epsilon}, \nonumber\\ x_{i_1}[t'+t_2+2] & \geq \alpha x_{i_1}[t'+t_2+ 1] + (1-\alpha) \overline{m}[t'] \nonumber\\ & \geq \overline{m}[t'] + \alpha^{t_2+2} \underline{\epsilon}, \nonumber\\ & \vdots \nonumber\\ x_{i_1}[t'+t_2+k] & \geq \alpha x_{i_1}[t'+t_2+k-1] + (1-\alpha) \overline{m}[t'] \nonumber\\ & \geq \overline{m}[t'] + \alpha^{t_2+k} \underline{\epsilon}, \label{eq:lower95bounds} \end{align}\tag{3}\] and \[\begin{align} x_{i_1}[t'+t_2+1] & \leq \alpha x_{i_1}[t'+t_2] + (1-\alpha) \overline{M}[t'] \nonumber\\ & \leq \overline{M}[t'] - \alpha^{t_2+1} \overline{\epsilon},\nonumber\\ x_{i_1}[t'+t_2+2] & \leq \alpha x_{i_1}[t'+t_2+1] + (1-\alpha) \overline{M}[t'] \nonumber\\ & \leq \overline{M}[t'] - \alpha^{t_2+2} \overline{\epsilon},\nonumber\\ & \vdots \nonumber \\ x_{i_1}[t'+t_2+k] & \leq \alpha x_{i_1}[t'+t_1+k-1] + (1-\alpha) \overline{M}[t'] \nonumber\\ & \leq \overline{M}[t'] - \alpha^{t_2+k} \overline{\epsilon}. \label{eq:upper95bounds} \end{align}\tag{4}\] Note the bound holds for \(T_1\leq t_2<t_2+k\leq T_2\). Then, we know \(x_{i_1}[t'+T_2] \in [\overline{m}[t']+\alpha^{T_2}\underline{\epsilon}, \overline{M}[t']-\alpha^{T_2}\overline{\epsilon}]\) \(\forall i_1 \in \mathcal{K}_1\), and thus \(\mathcal{K}_1 \subseteq \mathcal{K}_2\). Since all \(i_1\in \mathcal{K}_1 \subseteq \mathcal{F}_{\mathcal{C}}\) must belong to \(\mathcal{F}_{\mathcal{R}}[t'+t_2]\) at some \(t_2 \in [T_1, T_2-1]\), such a finite \(T_2\) exists.

Furthermore, by definition, \(\mathcal{G}_{\mathcal{R}}[t]\) is strongly \((2F+1)\)-robust with respect to \(\mathcal{L}\cup \mathcal{A}\) by 2 at \(t\) if \(|\mathcal{F}_{\mathcal{R}}[t]|>0\). Therefore, for any \(t_2\in [T_1, T_2-1]\) where \(|\mathcal{F}_{\mathcal{R}}[t'+t_2]|>0\), \(\mathcal{S}_{2,t_2}=\{i_2 \in \mathcal{S}_X(t'+t_2, \alpha^{t_2}\underline{\epsilon},\alpha^{t_2}\overline{\epsilon}) \mid |\mathcal{D}_{i_2}[t'+t_2]|\geq 2F+1\}\) is nonempty if \(\mathcal{S}_X(t'+t_2, \alpha^{t_2}\underline{\epsilon},\alpha^{t_2}\overline{\epsilon})\neq \emptyset\). If it is nonempty, since \(\mathcal{A}\) is \(F\)-local, \(\mathcal{D}_{i_2}[t'+t_2]\) contains at least \(F+1\) normal agents \(\forall i_2 \in \mathcal{S}_{2,t_2}\). Then, by definition of \(\mathcal{S}_X(t'+t_2, \alpha^{t_2}\underline{\epsilon},\alpha^{t_2}\overline{\epsilon})\), \(x_{i_2}[t'+t_2]>x_j^{i_2}[t'+t_2]\) or \(x_{i_2}[t'+t_2]<x_j^{i_2}[t'+t_2]\) \(\forall j \in \mathcal{D}_{i_2}[t'+t_2]\). This means \(i_2\) will use at least one in-neighbor’s state within \([\overline{m}[t']+\alpha^{t_2}\underline{\epsilon},\overline{M}[t']-\alpha^{t_2}\overline{\epsilon} ]\) to update \(x_{i_2}[t'+t_2+1]\), whose bounds are \(x_{i_2}[t'+t_2+1]\in [\overline{m}[t'] +\alpha^{t_2+1} \underline{\epsilon}, \overline{M}[t'] +\alpha^{t_2+1} \underline{\epsilon}]\) by 3 and 4 , which is also contained by \([\overline{m}[t'] +\alpha^{T_2} \underline{\epsilon}, \overline{M}[t'] +\alpha^{T_2} \underline{\epsilon}]\). Now denote \(\mathcal{S}_2 = \cup_{t_2=T_1}^{T_2-1} \mathcal{S}_{2,t_2}\). Because (i) \(\mathcal{S}_2 \subseteq \mathcal{K}_2\), (ii) \(\mathcal{K}_1 \subseteq \mathcal{K}_2\), (iii) \(\mathcal{S}_{2,T_1}\cap \mathcal{K}_1=\emptyset\), and (iv) \(i_2 \notin \mathcal{S}_X(t'+T_2, \alpha^{T_2}\underline{\epsilon}, \alpha^{T_2}\overline{\epsilon}) \;\forall i_2 \in \mathcal{K}_2\), we get \(|\mathcal{S}_X(t'+T_2, \alpha^{T_2}\underline{\epsilon},\alpha^{T_2}\overline{\epsilon})|<|\mathcal{S}_X(t'+T_1, \alpha^{T_1}\underline{\epsilon},\alpha^{T_1}\overline{\epsilon})|\).

This logic of the existence of finite time \(T_p\geq T_{p-1}+1\) such that \(|\mathcal{S}_X(t'+T_p, \alpha^{T_p}\underline{\epsilon},\alpha^{T_p}\overline{\epsilon})|<|\mathcal{S}_X(t'+T_{p-1}, \alpha^{T_{p-1}}\underline{\epsilon},\alpha^{T_{p-1}}\overline{\epsilon})|\) can be continued iteratively for \(p\geq 2\). We first define \(\mathcal{K}_p =\{i_p \in \mathcal{F}_{\mathcal{R}}[t'+T_p]\mid x_{i_p}[t'+T_p] \in [\overline{m}[t']+\alpha^{T_{p}}\underline{\epsilon}, \overline{M}[t']-\alpha^{T_{p}}\overline{\epsilon}]\}\). Furthermore, we define \(\mathcal{D}_{i_p}[t'+t_p] = \mathcal{N}_{i_p}[t'+t_p]\cap\mathcal{F}_{\mathcal{R}}[t'+t_p] \setminus \mathcal{S}_X(t'+t_p, \alpha^{t_p}\underline{\epsilon},\alpha^{t_p}\overline{\epsilon})\) for any \(t_p \in [T_{p-1},T_p-1]\). Let \(T_p\geq T_{p-1}+1\) be the earliest time where \(\mathcal{K}_{p-1}\subseteq \mathcal{K}_p\). Using the prior arguments, we conclude that \(x_{i_{p-1}}[t'+T_p] \in [\overline{m}[t'] +\alpha^{T_p} \underline{\epsilon}, \overline{M}[t'] +\alpha^{T_p} \underline{\epsilon}]\) \(\forall i_{p-1} \in \mathcal{K}_{p-1}\), and thus \(\mathcal{K}_{p-1} \subseteq \mathcal{K}_p\). Because all \(i_{p-1}\in \mathcal{K}_{p-1} \subseteq \mathcal{F}_{\mathcal{C}}\) must belong to \(\mathcal{F}_{\mathcal{R}}[t'+t_p]\) at some \(t_p \in [T_{p-1}, T_p-1]\), such finite \(T_p\) exists.

Furthermore, using the prior arguments, for any \(t_p\in [T_{p-1}, T_p-1]\) where \(|\mathcal{F}_{\mathcal{R}}[t'+t_p]|>0\), we can have nonempty \(\mathcal{S}_{p,t_p}=\{i_p \in \mathcal{S}_X(t'+t_p, \alpha^{t_p}\underline{\epsilon},\alpha^{t_p}\overline{\epsilon}) \mid |\mathcal{D}_{i_p}[t'+t_p]|\geq 2F+1\}\). If it is nonempty, since \(\mathcal{A}\) is \(F\)-local, \(\mathcal{D}_{i_p}[t'+t_p]\) contains at least \(F+1\) normal agents \(\forall i_p \in \mathcal{S}_{p,t_p}\). Then, by definition of \(\mathcal{S}_X(t'+t_p, \alpha^{t_p}\underline{\epsilon},\alpha^{t_p}\overline{\epsilon})\), \(x_{i_p}[t'+t_p]>x_j^{i_p}[t'+t_p]\) or \(x_{i_p}[t'+t_p]<x_j^{i_p}[t'+t_p]\) \(\forall j \in \mathcal{D}_{i_p}[t'+t_p]\). This means \(i_p\) will use at least one in-neighbor’s state within \([\overline{m}[t']+\alpha^{t_p}\underline{\epsilon},\overline{M}[t']-\alpha^{t_p}\overline{\epsilon} ]\) to update \(x_{i_p}[t'+t_p+1]\), whose bounds are \(x_{i_p}[t'+t_p+1]\in [\overline{m}[t'] +\alpha^{t_p+1} \underline{\epsilon}, \overline{M}[t'] +\alpha^{t_p+1} \underline{\epsilon}]\) with the similar reasoning as 3 and 4 , which is also contained by \([\overline{m}[t'] +\alpha^{T_p} \underline{\epsilon}, \overline{M}[t'] +\alpha^{T_p} \underline{\epsilon}]\). Now denote \(\mathcal{S}_p = \cup_{t_p=T_{p-1}}^{T_p-1} \mathcal{S}_{p,t_p}\). Then, because (i) \(\mathcal{S}_p \subseteq \mathcal{K}_p\), (ii) \(\mathcal{K}_{p-1} \subseteq \mathcal{K}_p\), (iii) \(\mathcal{S}_{p,T_{p-1}}\cap \mathcal{K}_{p-1}=\emptyset\), and (iv) \(i_p \notin \mathcal{S}_X(t'+T_p, \alpha^{T_p}\underline{\epsilon}, \alpha^{T_p}\overline{\epsilon}) \;\forall i_p \in \mathcal{K}_p\), we get \(|\mathcal{S}_X(t'+T_p, \alpha^{T_p}\underline{\epsilon},\alpha^{T_p}\overline{\epsilon})|<|\mathcal{S}_X(t'+T_{p-1}, \alpha^{T_{p-1}}\underline{\epsilon},\alpha^{T_{p-1}}\overline{\epsilon})|\).

Since \(\mathcal{F}_{\mathcal{C}}\) is finite, there must exist a finite time \(\overline{T}\geq 1\) such that \(\mathcal{S}_X(t'+\overline{T}, \alpha^{\overline{T}}\underline{\epsilon},\alpha^{\overline{T}}\overline{\epsilon})=\emptyset\). Then, \(\forall i \in \mathcal{F}_{\mathcal{C}}\), \[\begin{align} m[t']+\alpha^{\overline{T}}\underline{\epsilon}\leq x_i[t'+\overline{T}]\leq M[t']-\alpha^{\overline{T}}\overline{\epsilon}. \end{align}\]

Considering \(V[t]=M[t]-m[t]\), we get: \[\begin{align} V[t'+\overline{T}]&=M[t'+\overline{T}]-m[t'+\overline{T}] \nonumber\\ & \leq M[t']-\alpha^{\overline{T}}\overline{\epsilon} - \left(m[t']+\alpha^{\overline{T}}\underline{\epsilon}\right)\nonumber \\ & = V[t'] - \alpha^{\overline{T}}\left(\overline{\epsilon}+\underline{\epsilon}\right) \label{eq:almost95there}. \end{align}\tag{5}\]

Using the fact that \(\underline{\epsilon}=C_r-m[t']\) and \(\overline{\epsilon}=M[t']-C_r\), from 5 , we get \[\begin{align} V[t'+\overline{T}] &\leq V[t'] - \alpha^{\overline{T}}V[t']\\ & = \left(1-\alpha^{\overline{T}}\right)V[t']. \end{align}\] The above analysis can be repeated to show that \[\begin{align} V[t'+(\sigma+1)\overline{T}] \leq \left(1-\alpha^{\overline{T}}\right)V[t'+\sigma\overline{T}], \end{align}\] for \(\sigma\in \mathbb{Z}_{\geq 0}\), which can be expressed as: \[\begin{align} V[t'+(\sigma+1)\overline{T}] \leq \left(1-\alpha^{\overline{T}}\right)^{(\sigma +1)}V[t']. \label{eq:convergence95equation} \end{align}\tag{6}\] Since \(\left(1-\alpha^{\overline{T}}\right)<1\), \(V[t]\) converges to zero as \(t=t'+(\sigma+1)\overline{T}\to \infty\), which completes the proof.

1 shows that any follower that is active (and thus is part of a strongly \((2F+1)\)-robust subgraph) infinitely often achieves partial leader-follower consensus. Intuitively, convergence requires continual state updates while being sufficiently connected to filter out adversarial values —– a condition ensured by the BP-MSR algorithm only for followers who are active infinitely often. This allows us to characterize the convergent set without assuming robustness of the entire network. Note, however, that belonging to a strongly \((2F+1)\)-robust subgraph infinitely often is necessary but not sufficient for convergence, since adversaries can indirectly manipulate normal followers’ activation states by misreporting their own states (as discussed in 1).

Finally, the BP-MSR algorithm also guarantees safety for all non-convergent followers by ensuring that their states remain within the convex hull of normal agents whenever \(f_r[t]\) is constant. This is because followers transmit and update their states only when they are active. Therefore, in the worst case, all followers may be non-convergent (i.e., \(\mathcal{F}_{\mathcal{C}}=\emptyset\)), but their states remain bounded.

Now we show that the BP-MSR algorithm also ensures full resilient leader-follower consensus under certain conditions:

4.2 Convergent Set Analysis↩︎

While 1 gives conditions for convergence, determining the exact convergent set \(\mathcal{F}_{\mathcal{C}}\) as defined in 1 a priori is challenging, as it may depend on adversaries’ activation states. We therefore provide a more concrete characterization of \(\mathcal{F}_{\mathcal{C}}\) by identifying its subset and superset.

Let \(\mathcal{F}_{\mathcal{R}}[t] = \{i \in \mathcal{F}_{\mathcal{M}} \mid q_i[t]=1\}\). Note that \(i \in \mathcal{M}\) strictly follows 1 to update its activation state \(q_i[t,k]\) for all iterations. By 1, we know \(q_a^{u}[t,k]\in\{0,1\}\) for any \(a \in \mathcal{A}\). Then, for a given \(\mathbb{G}\), \(|\mathcal{F}_{\mathcal{R}}[t]|\) is determined by whether \(a \in \mathcal{A}\) shares \(q_a^{u}[t,k]=1\) or \(q_a^{u}[t,k]=0\) in each \(k\in[0,f-1]\). By the protocol 1 , for any \(i \in \mathcal{F}_{\mathcal{M}}\), \(q_i[t]=1\) if and only if \(\sum_{j \in \mathcal{N}_i[t]} q_j^i[t,f-1]\geq 2F+1\). Therefore, \(|\mathcal{F}_{\mathcal{R}}[t]|\) at time \(t\) is minimized when all adversaries share \(q_a^{u}[t,k]=0\) for every \(k \in [0,f-1]\) and maximized when they share \(q_a^{u}[t,k]=1\) for every \(k\). Hence, all \(a\in \mathcal{A}\) sharing \(q_a^{u}[t,k]=0\) and \(q_a^{u}[t,k]=1\) \(\forall k\in[0,f-1]\) and \(\forall t \in \mathbb{Z}_{\geq 0}\) will minimize and maximize \(|\mathcal{F}_{\mathcal{C}}|\), respectively.

3 characterizes the two extreme scenarios in which the convergent set is minimized or maximized, based on how adversaries behave. Using this lemma, we provide a constructive method to identify its subset and superset:

We know that \(\mathcal{G}^1[t]\) is strongly \((2F+1)\)-robust with respect to \(\mathcal{L}_{\mathcal{M}}\) and \(\mathcal{V}^1[t] \subseteq \mathcal{M}\). Hence, by 1, every \(i \in \mathcal{V}^1[t] \cap \mathcal{F}_{\mathcal{M}}\) satisfies \(\sum_{j \in \mathcal{N}_i[t] \cap \mathcal{M}} q_j^i[t,f-1] \geq 2F+1\). Therefore, if all adversaries share \(q_a^{u}[t,k] = 0\) for all \(k\in[0,f-1]\), only the followers in \(\mathcal{V}^1[t] \cap \mathcal{F}_{\mathcal{M}}\) are guaranteed to have \(q_i[t]=1\) at time \(t\). It follows that any \(i\) with \(|\mathcal{T}_i^1| = \infty\) has \(\lim\sup_{t\to \infty} q_i[t]=1\), and thus convergent by 1. By 3, this defines the smallest possible convergent set, yielding \(\mathcal{F}_{\mathcal{C}}^1 \subseteq \mathcal{F}_{\mathcal{C}}\).

An analogous argument applies to \(\mathcal{G}^2[t]\), which is strongly \((2F+1)\)-robust with respect to \(\mathcal{L}\cup \mathcal{A}\). If all adversaries share \(q_a^{u}[t,k] = 1\), we can consider all adversaries as leaders. Then by 1, \(q_i[t]=1\) for all \(i \in \mathcal{V}^2[t] \cap \mathcal{F}_{\mathcal{M}}\) at time \(t\). Thus, any \(i\) with \(|\mathcal{T}_i^2| = \infty\) has \(\lim\sup_{t\to \infty} q_i[t]=1\) and convergent by 1. By 3, this defines the largest possible convergent set, yielding \(\mathcal{F}_{\mathcal{C}} \subseteq \mathcal{F}_{\mathcal{C}}^2\). Through 1, we can explicitly determine the subset and superset of convergent set \(\mathcal{F}_{\mathcal{C}}\). The subset \(\mathcal{F}_{\mathcal{C}}^1\) is a set of followers that belong infinitely often to a subgraph that is induced only by normal agents and strongly \((2F+1)\)-robust with respect to \(\mathcal{L}_{\mathcal{M}}\). Conversely, the superset \(\mathcal{F}_{\mathcal{C}}^2\) consists of followers that belong infinitely often to a subgraph that is strongly \((2F+1)\)-robust with respect to \(\mathcal{L}\cup \mathcal{A}\). Examples of such subgraphs are shown in 2.

5 Simulation Results↩︎

We evaluate the effectiveness of our method through two sets of simulations. First, we illustrate 1 by comparing the performance of the BP-MSR algorithm against those of other existing resilient consensus algorithms. Second, we empirically validate the set bounds in 1. For all simulations, we use the graphs in 2, each with leaders \(\mathcal{L}=\mathcal{L}_{\mathcal{M}}= \{1,2,3\}\) and a \(1\)-local \(\mathcal{A}= \{0\}\). The adversary shares \(x_0^j[t] = 1000 \cdot \sin\big((t+j)/5\big)\) with the normal followers \(j \in \{4,5,6,7,8,9\}\). The initial states of followers are generated randomly in the interval \([-1000, 1000]\). Leaders update their states using \(f_r\), drawing the same random value in \([-1000, 1000]\) every \(50\) time step. Code is available here.³

5.0.1 Comparison↩︎

For comparison, we include the W-MSR algorithm with parameter \(F\), which guarantees resilient leader-follower consensus with \(F\)-local adversary set \(\mathcal{A}\) when the network is always either strongly \((2F+1)\)-robust or jointly \((F+1)\)-robust with \(1\) hop [1], [20], [30]. We also consider the SW-MSR algorithm with parameters \(T\) and \(F\), which ensures consensus when the network satisfies strong \((T, t_0, 2F+1)\)-robustness [4]. To evaluate the applicability of these guarantees, we analyze the robustness of \(\mathcal{G}_1\), \(\mathcal{G}_2\), and \(\mathcal{G}_3\) from 2. Each graph is at most strongly \(1\)-robust with respect to \(\mathcal{L}\) and jointly \(1\)-robust with one hop, implying that resilient consensus cannot be guaranteed by W-MSR [4], [20]. Similarly, any periodic repetition of the graphs in 2 fails to satisfy strong \((3,0,3)\)-robustness, so consensus is not guaranteed under SW-MSR either [4].

3 shows results consistent with the analysis above and 1. We consider three cases where each normal agent runs the W-MSR, SW-MSR (with \(T=2\)), and BP-MSR algorithms, all with \(F=1\), under the sequence \(\mathbb{G}=(\mathcal{G}[t])_{t\in \mathbb{Z}_{\geq 0}}\), where \(\mathcal{G}[2\tau]=\mathcal{G}_1\) and \(\mathcal{G}[2\tau+1]=\mathcal{G}_2\) for all \(\tau \in \mathbb{Z}_{\geq 0}\). Neither the W-MSR nor the SW-MSR algorithm enables the followers to track the leader’s reference state (blue). In contrast, followers in \(\mathcal{F}_{\mathcal{C}}=\{6,7,8\}\) reach partial leader-follower consensus under the BP-MSR algorithm, as each satisfies \(\limsup_{t \to \infty} q_i[t] = 1\) and thus belongs to strongly \(3\)-robust subgraphs infinitely often (see yellow-shaded regions in 2 (a)-(b)). Meanwhile, followers \(\{4,5,9\}\) are non-convergent under BP-MSR algorithm but remain within the convex hull of the normal agents’ states.

5.0.2 Convergent Set Analysis↩︎

Now we analyze the convergent set \(\mathcal{F}_{\mathcal{C}}\) under the BP-MSR algorithm with the graph sequence \(\mathbb{G}\) where \(\mathcal{G}_1\), \(\mathcal{G}_2\), and \(\mathcal{G}_3\) repeat periodically. Although the exact \(\mathcal{F}_{\mathcal{C}}\) might be difficult, we can identify its subset and superset using 1. In \(\mathcal{G}_1\), \(\mathcal{G}_2\), and \(\mathcal{G}_3\), the followers \(\{6,7\}\), \(\{8\}\), and \(\{6\}\) respectively belong to strongly \(3\)-robust subgraphs with respect to \(\mathcal{L}_{\mathcal{M}}\) (highlighted in yellow in 2). Similarly, in \(\mathcal{G}_1\), \(\mathcal{G}_2\), and \(\mathcal{G}_3\), the followers \(\{6,7\}\), \(\{8\}\), and \(\{4,5,6\}\) respectively belong to strongly \(3\)-robust subgraphs with respect to \(\mathcal{L}\cup \mathcal{A}\) (as highlighted in gray in 2). Since the graphs are repeating periodically, we can deduce \(\{6,7,8\} \subseteq \mathcal{F}_{\mathcal{C}} \subseteq \{4,5,6,7,8\}\) using 1. This aligns with 4 (a) and (b), which illustrate the smallest and largest convergent sets (by 3), obtained when Byzantine agent \(0\) always shares \(q_0^u[t,k]=0\) and \(q_0^u[t,k]=1\) with its out-neighbors, respectively. In case (a), only followers \(\{6,7,8\}\) converge, whereas in case (b), \(\{4,5,6,7,8\}\) converge.

6 Conclusions↩︎

This paper studies resilient leader-follower consensus for a subset of followers in an arbitrary sequence of time-varying graphs. We propose a novel distributed algorithm that allows each follower to locally decide when to share and update its state based on its connectivity at each time step. We provide a theoretical characterization of the followers guaranteed to achieve leader-follower consensus. Finally, we support our results with simulations showing that our method allows a subset of followers to achieve consensus even when robustness conditions of the entire network are not satisfied.

References↩︎