Resilient Leader-Follower Consensus to Arbitrary Reference Values
James Usevitch Dimitra Panagou






Resilient Leader-Follower Consensus to Arbitrary Reference Values
    James Usevitch and Dimitra Panagou
James Usevitch is with the Department of Aerospace Engineering, University of Michigan, Ann Arbor; .
Dimitra Panagou is with the Department of Aerospace Engineering, University of Michigan, Ann Arbor; .
The authors would like to acknowledge the support of the Automotive Research Center (ARC) in accordance with Cooperative Agreement W56HZV-14-2-0001 U.S. Army TARDEC in Warren, MI. This work has been funded by the Center for Unmanned Aircraft Systems (C-UAS), a National Science Foundation Industry/University Cooperative Research Center (I/UCRC) under NSF Award No. 1738714 along with significant contributions from C-UAS industry members. 

    ^⋆ E-mail: mailto:Jordan.Collier@csiro.auJordan.Collier@csiro.au

Accepted 2018 February 23. Received 2018 February 23; in original form 2017 June 16
===========================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================

empty
empty

wrt[w.r.t.]with respect to
apf[APF]Artificial Potential Fields

The problem of consensus in the presence of misbehaving agents has increasingly attracted attention in the literature. Prior results have established algorithms and graph structures for multi-agent networks which guarantee the consensus of normally behaving agents in the presence of a bounded number of misbehaving agents. The final consensus value is guaranteed to fall within the convex hull of initial agent states. However, the problem of consensus tracking considers consensus to arbitrary reference values which may not lie within such bounds. Conditions for consensus tracking in the presence of misbehaving agents has not been fully studied. This paper presents conditions for a network of agents using the W-MSR algorithm to achieve this objective.






§ INTRODUCTION


There has been an increasing amount of recent work on resilient consensus-based algorithms. Several authors have proposed algorithms that employ local filtering mechanisms to guarantee that normal agents are able to come to agreement in the presence of a bounded number of malicious or misbehaving agents. These algorithms include the ARC-P, W-MSR, SW-MSR, and DP-MSR algorithms (<cit.>). These algorithms are able to mitigate the effects of malicious and misbehaving agents without the need for normal agents to explicitly identify the sources of misbehavior. They guarantee that the consensus value of normally behaving agents is within the convex hull of the initial agent state values under the assumption of r-robustness or (r,s)-robustness of the network. On the other hand, consensus-based algorithms without resilience to malicious agents have been employed in the literature to solve the problem of coming to consensus to reference values, where agents seek to come to agreement with a reference state which may or may not lie within the convex hull of initial state values (see <cit.> and references). Solutions to this problem have been studied in the literature under the assumption that agents are behaving nominally (e.g. <cit.>). 

The problem of consensus to reference values in r-robust networks has not been as thoroughly treated. The most relevant work is that in <cit.>. In <cit.> and <cit.>, a resilient protocol and dynamic feedback laws are given to synchronize trajectories of continuous-time agents to the same stable zero-input solution of a time-invariant system in the presence of adversaries. This work only considers continuous-time LTI systems however, with the assumption that the time-varying reference state satisfies the dynamics ẋ_r = Ax_r for some A. In <cit.>, the problem of resilient distributed estimation is considered where agents employ a discrete-time resilient consensus algorithm similar to the W-MSR algorithm to reduce the estimation error of individual parameters of interest. The authors assume that certain nodes have a precise knowledge of their own parameters. These "reliable nodes" drive the errors of the rest of the normal nodes to the reference value of zero in the presence of misbehaving agents. The main result of this paper is that consensus of the normal agents' error values to zero occurs if for each normal node i there exists an infinite sequence of time periods (with bounded, finite time between each time period) where i interacts with at least F+1 reliable nodes. A limitation of these results is the interaction requirement between each normal node and the minimum required number of reliable nodes, which becomes increasingly difficult to satisfy as the network size increases. The problem of consensus with a static reference state also somewhat resembles the resilient broadcast problem (<cit.>) in which a source node seeks to transmit a message to all other nodes in the presence of malicious or misbehaving nodes. However, the state update algorithms differ from those commonly applied in r-robust networks. Finally, in <cit.> the authors consider resilient distributed estimation of a system of the form x[t+1] = Ax[t] where each individual agent may only be able to observe part of the system modes. A Mode Estimation Directed Acyclic Graph (MEDAG) is constructed for each mode λ_j of A. Each MEDAG consists of a set of at least (2F+1) source nodes which can observe λ_j, and successive subsets (called levels) of the remaining nodes with sufficient in-neighbors to guarantee information flow from the source nodes. If there exists a MEDAG for each unobservable mode and if agents can explicitly identify in-neighbors from preceding levels, a resilient consensus algorithm can be used to bring agents' estimates of the system state into agreement with the actual state. A graph condition called strong r-robustness (<cit.>) is a sufficient condition for a graph to contain a MEDAG; specifically, the network must be strongly (2F+1)-robust with respect to a set of source nodes. However, the algorithm given in <cit.> for agents to identify in-neighbors from preceding levels requires the graph to initially be strongly (3F+1)-robust. 




The contributions of this paper differ from prior literature in the following ways: first, we consider consensus tracking with a reference signal which is a piecewise continuous step function. We show that under the W-MSR algorithm, consensus tracking is guaranteed if the graph is strongly (2F+1)-robust without the need for agents to identify in-neighbors from preceding levels in a MEDAG. Since this identification is not required, the graph does not need to initially be (3F+1)-robust. Second, we incorporate the notion of trusted nodes (or trusted agents) into resilient consensus tracking <cit.>. Trusted agents are agents which have been sufficiently secured such that it can be safely assumed that they will always behave. Having trusted agents as leaders allows the condition of strong r-robustness to be slightly relaxed while still guaranteeing consensus to the reference value. Finally, there is very little prior work on proving that any class of graph is strongly r-robust. We demonstrate that certain graphs called k-circulant graphs are strongly r-robust when a proper subset of agents are chosen to behave as leaders.



Our paper is organized as follows: Section 2 contains our notation and problem formulation. In Section 3 we present necessary conditions for consensus tracking in robust networks and the insufficiency of r-robustness and (r,s)-robustness to guarantee consensus tracking to arbitrary values. Section 4 contains our main results on consensus to a reference state in the presence of adversaries. In Section 5 we demonstrate the strong r-robustness of k-circulant graphs.  Section 6 contains simulations demonstrating our work, and in section 7 we give a brief conclusion.






§ NOTATION AND PROBLEM FORMULATION


We denote a graph as 𝒢 = (𝒱,) and a digraph as 𝒟 = (𝒱,), with = {1,...,n} denoting the vertex set, or agent set, of the graph and  denoting the edge set of the graph. A directed edge (i,j) ∈: i,j ∈ denotes that there exists a connection from agent i to agent j. Agent j is able to receive information from agent i if (i,j) is in  (note that (i,j) ≠ (j,i)). This implies that agent i is an in-neighbor of j and agent j is an out-neighbor of i. We denote the set of in-neighbors of agent i as _i = {j: (j,i) ∈)} and the set of inclusive neighbors  of i as _i = (_i ∪{i}) <cit.>. We denote the cardinality of a set S as |S|, the set of integers as ℤ, the set of integers greater than or equal to 0 as ℤ_≥ 0. and the natural numbers as ℕ.

An undirected graph of n agents is called circulant if there exists a set {a_1, a_2, …, a_l ∈ℤ_≥ 0: a_1 < a_2 < … < a_l < n} such that (i, [i ± a_1 ] mod  n) ∈, …, (i,[i ± a_l ] mod  n) ∈ <cit.>. We call such a graph an undirected circulant graph and denote it as C_n(± a_1, ± a_2, …, ± a_m) = (, ). These graphs are constructed over the additive group of integers modulo n (the agents n+a and a are congruent modulo n). Similarly, we call a digraph of n agents circulant if there exists a set {a_1, a_2, …, a_m: 0 < a_1 < a_2 < … < a_m < n}, m ∈ℤ_≥ 0 such that (i, [i+a_1 ] mod  n) ∈ℰ, …, (i,[i+a_m ] mod  n) ∈ℰ. We denote such a graph as C_n(a_1, a_2, …, a_m) = (, ) and call it a directed circulant graph or circulant digraph.

In this paper, we will consider a specific class of circulant digraphs called k-circulant digraphs:


Let n ∈ℤ, n ≥ 2 and let k ∈ℤ: 1 ≤ k ≤ n-1. A k-circulant digraph  is any circulant digraph of the form C_n(1,2,3,…,k) = (, ).


This type of graph is fully determined by the number of agents n and by the parameter k, which determines the in- and out-neighbors of each agent.

Finally, the notions of reachability, r-robustness, and (r,s)-robustness were defined by the authors of <cit.>. We do not repeat the definitions here due to lack of space. Although the definitions refer specifically to digraphs, they also apply to undirected graphs.[Undirected graphs can be modeled as digraphs in which (i,j) ∈ (j,i) ∈]






































 §.§ Problem Definition


The prior literature has mainly dealt with resilient asymptotic consensus (<cit.>), where agents remain within the convex hull of their initial values and come to consensus on a common value. However, there may exist cases where it is desired for agents' states to reach consensus on some reference value that may be outside the convex set of initial states. To address this problem, we assume there exists a potentially time-varying reference state x_r[t] that satisfies x_r[t+1] = f_r(t,x_r[t]). We assume that f_r(t,x_r[t]) is a piecewise-continuous step function where for each point of discontinuity t_d, f_r(t_d,x_r[t_d]) = lim_t  t_d^+ f_r(t,x_r[t]). The objective of consensus tracking is

    lim_t →∞x_i[t] - x_r[t] = 0, ∀ i ∈


We consider the case where the reference state is constant after some finite time T, i.e. for some C_L ∈,

    f_r(t,x_r[t]) = C_L ∀ t ≥ T


In this paper, we consider the problem of sufficient graph theoretical conditions for consensus tracking among normally behaving agents to occur when these agents apply the W-MSR algorithm in the presence of misbehaving agents, which will be defined later in this section. As we will show in section <ref>, the graph theoretic concepts of r- and (r,s)-robustness are insufficient to guarantee consensus tracking under these conditions.

Three types of agents are considered: normal agents, agents behaving as leaders, and misbehaving or adversarial agents. Normal agents update their state by applying the W-MSR algorithm, which was defined in <cit.> and is summarized below:



  * Each agent i receives state values from its inclusive set of in-neighbors _i and forms a sorted list.

  * Each agent i's own state value is used as a reference to filter out outliers in the sorted list. If there are F or less values greater than (or less than) its state value, each agent removes all states greater than (less than) its own from the list. If there are F or more states greater than (or less than) its own state, it removes the highest (lowest) F states.

  * Using the remaining values, denoted as ℛ_i[t], each agent i updates its state according to a function of the remaining states:

    x_i[t+1] = ∑_j ∈ℛ_i[t] w_ij[t]x_j[t], ∀ i ∈



The set of normal agents is denoted . It is assumed that the following conditions hold for the weights w_ij[t] for all i ∈ and for all t ∈ℤ_≥ 0:



  * w_ij[t] = 0 when j ∉𝒥_i

  * w_ij[t] ≥α, 0 < α < 1, ∀ j ∈𝒥_i

  * ∑_j=1^n w_ij[t] = 1

Next, we define a agent behaving as a leader as follows:

An agent behaves as a leader if it updates its state value according to 

    x[t+1] = x_r[t+1] = f_r(t,x_r[t]) ∀ t ≥ t_0



We denote the set of such agents as ⊂. By a slight abuse of language, we will sometimes refer to agents behaving as leaders simply as “leaders" in this paper. Such agents are not explicitly recognized by other agents in the network; their communicated state values are filtered and weighted in the same way as other agents' states in state update equations.

Finally, we define misbehaving agents as follows:

An agent j ∈ is misbehaving if both of the following conditions are satisfied:


  * There exists a time t where agent j does not update its state according to equation (<ref>) 

  * There exists a time t where agent j does not update its state according to (<ref>) and/or sends different state values to different out-neighbors at any time t.


Misbehaving agents therefore include agents that are Byzantine and malicious, as defined in <cit.>. Briefly, the key difference between the two is that malicious agents send the same state value to all out-neighbors while Byzantine agents may send different values to different out-neighbors. We denote the set of misbehaving agents as . We assume that ∪∪ =. The threat model assumed in this paper is that  is an F-local set, meaning that for any i ∈, |_i ∩| ≤ F <cit.>.

The following Lemmas will be needed in our analysis of conditions guaranteeing resilient consensus tracking:






Consider the reference tracking consensus problem. A necessary condition for the normal agents reaching consensus to the group reference at any arbitrary value under the W-MSR protocol is the presence of at least F+1 agents behaving as leaders.
 


Suppose || ≤ F, and all other normal and misbehaving agent states are at a common value a ∈. Suppose x_r[t_1] = a_1, a_1 ≠ a for some a_1 ∈ and t_1. If the malicious agents keep their state values at a, then ∀ i ∈, |ℛ_i[t] ∩| = 0 ∀ t ≥ t_1 by definition of the W-MSR algorithm. Thus all normal agents will remain at a.




Under the W-MSR protocol, any agent i connected to at least F+1 agents behaving as leaders with state values equal to a value C_L will receive input from those leaders at all times. 



Suppose an agent i is connected to all agents in a set of leaders S_L, |S_L| ≥ F+1 whose state value is C_L. If C_L is greater or less than x_i[t], agent i will filter out at most F values from S_L. If C_L = x_i[t], none of the states from S_L will be filtered out.




 §.§ Insufficiency of r- and (r,s)-Robustness for Consensus to Reference Values
 

In <cit.> it was shown that under an F-total  malicious adversary model, a necessary and sufficient condition for resilient asymptotic consensus in a network applying the W-MSR protocol is (F+1,F+1)-robustness of the network. Similarly, under an F-local malicious or F-total Byzantine adversary model, a sufficient condition for resilient asymptotic consensus is (2F+1)-robustness of the network. In order to achieve resilient consensus tracking, one might be tempted to take a (2F+1)- or (F+1,F+1)-robust network and designate any F+1 arbitrary agents to behave as leaders. We demonstrate that this is not sufficient to guarantee that the normal agents will achieve consensus to the leader agents.

Consider an (F+1,F+1)-robust network partitioned into two disjoint sets S_1 and S_2, S_1 ∪ S_2 =. Let a_1,a_2 ∈, a_1 ≠ a_2 be two arbitrary values. Define 𝒳_S_m^r = {i ∈ S_m: | _i ∖ S_m| ≥ r} for m ∈{1,2}. Suppose the set S_1 consists of F+1 agents with initial value of a_1, all of which have F+1 in-neighbors outside of S_1 (|F+11| = |S_1|). Suppose the set S_2 consists of all other agents in the network, all with initial value a_2 and none of which have more than F connections outside of S_2 (|F+12| = 0). Let all agents in S_1 behave as leaders with x_r[t] = a_1. This graph meets the criteria for being (F+1,F+1)-robust, but the normal agents will not achieve consensus to the leaders since none have at least F+1 in-neighbors outside of S_2. 



Next, consider a (2F+1)-robust network with a set S_1 of F+1 agents with state values at a_1. Let S_2 contain all other agents in the graph with initial state values of a_2. Since the graph is (2F+1)-robust, there necessarily exists at least one agent in S_1 that has (2F+1) connections in S_2. Suppose that F or less agents in S_2 are connected to all agents in S_1. This graph satisfies the conditions for (2F+1)-robustness. But, if all agents in S_1 behave as leaders with x_r = a_1, and if all F or less agents in S_2 connected to all the leaders in S_1 become malicious and hold their state values at a_2, the normal agents will never achieve consensus to the leaders. This demonstrates that simply designating F+1 arbitrary agents in a (2F+1)- or (F+1,F+1)-robust network to act as the group reference will not guarantee that all normal agents will converge to x_r[t]. 



§ CONSENSUS TO A REFERENCE VALUE IN ROBUST NETWORKS




 §.§ Consensus Tracking Without Trusted Agents


It is clear that different graph conditions are needed to guarantee consensus to the group reference under the W-MSR algorithm. We will demonstrate that the property of strong r-robustness is sufficient for this to be achieved.


	<cit.> Let r ∈_≥ 0 and S ⊂. A graph is strongly r-robust with respect to S if for all nonempty subsets C ⊆\ S, C is r-reachable.















Consider a graph G = (,) which satisfies an F-local adversary model with |∩| ≥ 0. Suppose G is strongly (2F+1) robust with respect to  and the normal agents apply the W-MSR algorithm. Define m[t] = min_i ∈ (x_i[t],x_r[t]) and M[t] = max_i ∈ (x_i[t],x_r[t]). Then on any time interval [t_1,t_2) where x_r[t] is constant, the following hold ∀ t ∈ [t_1,t_2):


  * x_i[t] ∈ [[t_1],[t_1]] ∀ i ∈\

  * [t] and [t] are nondecreasing and nonincreasing, respectively




Consider an agent i ∈. At any time t ∈ [t_1,t_2), agent i will receive at most F values from _i ∩, denoted {x_a_1[t],…,x_a_j[t]}, j ≤ F, by definition of an F-local adversary model. For any such j, observe that x_a_j[t] > [t] implies x_a_j[t] > x_k[t], ∀ k ∈_i \. This implies that x_a_j[t] will be one of the highest values in i's sorted list of state values, and therefore will not be in ℛ_i[t]. A similar method can be used to show x_a_j < [t] implies x_a_j[t] ∉ℛ_i[t]. Therefore by definition of the W-MSR algorithm, x_i[t] will update its state with a convex combination of values in [[t],[t]], implying [t+1] ≥[t], [t+1] ≤[t] ∀ t ∈ [t_1,t_2) (since x_r[t] is constant on [t_1,t_2)). Therefore x_i[t] ∈ [[t_1],[t_1]] and [t] and [t] are nondecreasing and nonincreasing, respectively, for t ∈ [t_1,t_2).





 Lemma <ref> gives a safety condition in the sense that when x_r[t] is constant ∀ t ∈ [t_1,t_2), [[t_1],[t_1]] is an invariant set on the same time interval.













Consider a graph of n agents operating under the W-MSR algorithm that satisfies an F-local adversary model with |∩| ≥ 0. Suppose further that there exists a time t_C and a constant C_L ∈ such that x_r[t]=C_L ∀ t ≥ t_C. Then lim_t →∞x_i[t] - x_r[t] = 0 ∀ i ∈ if the network is strongly (2F+1)-robust with respect to .



We prove by contradiction. By Lemma <ref>, we know that m[t] and M[t] are monotonic functions for all t ≥ t_C and therefore have limits A_ and A_, respectively. The agents reach consensus to x_r[t] if A_ = A_ = C_L. 

We first consider the case when [t_C] > C_L and [t_C] < C_L. Let _m0 = C_L - A_ and _M0 = A_ - C_L. Let _0 = min(_m0,_M0). This implies that A_ + _0 ≤ C_L ≤ A_ - _0. Define the functions X_m(t,ϵ_i) = {i ∈: x_i[t] < A_ + ϵ_i} and X_M(t,ϵ_i) = {i ∈: x_i[t] > A_ - ϵ_i}. Next, define the set S_X(t,_i) = X_m(t,_i) ∪ X_M(t,_i). Also define ϵ < α^N/1-α^Nϵ_0 where N = ||. Note that ϵ_0 > ϵ > 0. By the definition of convergence, there exists a time t_ϵ such that [t_] > A_ - and [t_] < A_ +. Consider the set S_N_0 =.  By definition of strong (2F+1)-robustness, there exists at least one agent i ∈ S_N_0 that is connected to at least F+1 leader agents. This is because at least one agent in S_N_0 must have 2F+1 in-neighbors outside of S_N_0. Since an F-local adversary model implies |_i ∩| ≤ F, i must be connected to at least F+1 leaders. From Lemma <ref> we know that i will use at least one leader's state to update its own state for all time. 

By Lemma <ref>, agent i will update its state with values on the interval [[t_,[t_]]. To demonstrate the smallest and largest values that i's state can possibly have at time t_ + 1, we assume that the minimum possible weight α is placed on the leader's state value, and the maximum possible weight is placed on [t_] or [t_], the smallest and largest values possible for agent i's in-neighbors. We have

    x_i[t_ +1]    ≥ (1-α)[t_] + α C_L
       ≥ (1-α)(A_ - ) + α(A_ + _0) 
       ≥ A_ + α_0 -  (1-α) 
    
    x_i[t_ +1]    ≤ (1-α)[t_] + α C_L
       ≤ (1-α)(A_ + ) + α(A_ - _0) 
       ≤ A_ - α_0 +  (1-α)

Define _1 = α_0 - (1-α). It can be shown that _0 > _1 >  >0. The above bounds also apply to any other normal agents connected to at least F+1 leader agents, and therefore each normal agent i connected to at least F+1 leaders satisfies A_ + _1 ≤ x_i[t_+1] ≤ A_ - _1. Since these agents use their own state when performing state updates, and by monotonicity of [t] and [t], these bounds also apply ∀ t ≥ t_ +1. Now, observe that |S_X(t_+1,_1)| ≤ |S_X(t_,)|. Consider the new set S_N_1 = S_X(t_+1,_1). Observe that all normal agents connected to at least F+1 leaders are not in S_N_1. By the conditions of (2F+1)-robustness, there exists at least one agent i_1 that will not filter out at least one in-neighbor with state value within the bounds [A_ + _1, A_ - _1]. Therefore the lowest and highest bounds for x_i_1[t_ + 2] are

    x_i_1[t_+2]    ≥ (1-α)[t_]+α(A_+_1) 
       ≥ A_ + α_1 -  (1-α) 
    
    x_i_1[t_ +2]    ≤ (1-α)[t_] + α (A_ - _1)
       ≤ A_ - α_1 +  (1-α)

These bounds also apply for all normal agents not in S_N_0 since each normal agent uses its own state value when performing its state update. Defining the new value _2 = α_1 -  (1-α), we then have i_1 ∉ S_X(t_ + 2,_2). This implies  |S_X(t_+2,_2)| < |S_X(t_+1,_1)|. We now define _j recursively for j ≥ 1, j ∈ as _j = α_j-1 - (1-α). It can be shown that _j < _j-1 ∀ j ≥ 1. If at each timestep t_ + j we define S_N_j = S_X(t_+j,_j), there will exist a agent i_j ∈ S_N_j with at least F+1 in-neighbors in the interval [A_+_j, A_-_j]. This implies that i_j has an in-neighbor k ∈ S_L: A_ + _j ≤ x_k[t_ + j] ≤ A_ + _j that will not be filtered out when updating its state for time step t_ + j+1. Therefore agent i_j will not be in S_N_j+1 for time step t_+j+1 (as well as all normal agents which were not in S_N_j.

Continuing the above analysis for each time step t_+j, we see that |S_X(t_+j,_j)| < |S_X(t_+j-1,_j-1)|. Since |S_X(t_,_0)| ≤ ||, there exists a time step t_ + T, T ≤ || where |S_X(t_+T,_T)| = 0. This implies that [t_+T] ≥ A_ + _T and [t_+T] ≤ A_ - _T. We demonstrate that _T > 0, which contradicts A_ and A_ being the lower and upper limits for [t] and [t]. Let N = ||. The value of _T satisfies

    _T    = α_T-1 - (1-α)
       = α^2 _T-2 - α(1-α) - (1-α)
       ⋮
       = α^T _0 - (1-α)(1+α+…+α^T-1)
       = α^T _0 -(1-α^T)
       ≥α^N _0 - (1-α^N)

By definition of , (1-α^N) < α^N _0, which implies that _T > 0. This contradicts our assumptions that A_ < C_L and A_ > C_L, proving that A_ = A_ = C_L and lim_t →∞x_i[t] - x_r[t] = 0 ∀ i ∈.

Finally, we consider the case when either [t] = C_L or [t] = C_L for some t ≥ t_T. Without loss of generality, consider the case where [t] = C_L. By Lemma <ref> we know that all normal agents' state values are bounded by [[t_0],C_L] and that [t] is nondecreasing. Therefore m[t] has an upper limit A_. Suppose A_ < C_L. Let ϵ_0 = C_L - A_. A similar strategy can be used to demonstrate that there exists a time where all agents have a value greater than A_, contradicting that A_ is an upper limit to [t] and proving that lim_t →∞x_i[t] - x_r[t] = 0 ∀ i ∈.





















 §.§ Consensus Tracking With Trusted Agents




We point out that for a graph to be strongly (2F+1)-robust with respect to the set , || ≥ 2F+1. If we incorporate the notion of trusted agents into the network, this lower bound on the number of leaders can be slightly relaxed. Trusted agents as defined in <cit.> are agents who have been made sufficiently secure to safely assume that they cannot be compromised and will not misbehave. We define trusted leader-follower robustness as follows:



A network is trusted leader-follower robust (TLF robust) with parameter F ∈_≥ 0 if for a set S ⊂ and for all nonempty sets C ⊆\ S, at least one of the following holds:


  * There exists i ∈ C with at least F+1 in-neighbors from S; i.e. |_i ∩𝒮| ≥ F+1

  * C is 2F+1-reachable



Under TLF robustness, the minimum number of leaders required is only F+1. The following Lemma and Theorem extend the results obtained for (2F+1)-robust networks to TLF-robust networks:












Consider a graph G = (,) which satisfies an F-local adversary model where |∩| = 0. Suppose G is TLF robust with parameter F, and the normal agents apply the W-MSR algorithm. Define m[t] = min_i ∈(x_i[t],x_r[t]) and M[t] = max_i ∈ (x_i[t],x_r[t]). Then on any time interval [t_1,t_2) where x_r[t] is constant, the following hold ∀ t ∈ [t_1,t_2):


  * x_i[t] ∈ [[t_1],[t_1]] ∀ i ∈\

  * [t] and [t] are nondecreasing and nonincreasing, respectively




The result can be shown by a method similar to the proof of Lemma <ref>. 



Consider a network of n agents with trusted leaders (|∩| = 0) operating under the W-MSR algorithm that satisfies an F-local adversarial condition. Suppose further that there exists a time t_C and a constant C_L ∈ such that x_r[t]=C_L ∀ t ≥ t_C. Then lim_t →∞x_i[t] - x_r[t] = 0 ∀ i ∈ if the network is TLF robust with parameter F.



The result can be shown by using a method similar to Theorem <ref>.













§ APPLICATION TO CIRCULANT GRAPHS


Circulant graphs are useful in the context of robust networks since their r-robustness is easily determined. Since 2k-connected ring graphs are at least k/2-robust (<cit.>), an undirected circulant graph of the form C_n{± 1, ± 2, …, ± k} is 2k connected and therefore k-robust. In addition, our recent work in <cit.> demonstrates that circulant digraphs of the form C_n{1,2,…,k} are at least k/2-robust.

We now show that these graphs can demonstrate strong (2F+1)-robustness and TLF robustness with parameter F by selecting a proper subset of agents to behave as leaders. As per the definition of circulant graphs, we assume all agents are indexed 1,…,n. In our next proof we refer to sets of consecutive agents by index. An example is P_L = {2,3,4,5,…,9} in a network of n=15 agents. Since the index numbers are defined on the set of integers modulo n, the set P_L = {14, 15,1,2} would also be a set of consecutive agents in a network of n=15 agents.



A k-circulant digraph = C_n{1,2,…,k} is strongly (2F+1)-robust with respect to  if  contains a set of consecutive agents by index P_L such that |P_L| ≤ k and |P_L ∩| ≥ 2F+1. Moreover,  satisfies the conditions for TLF robustness with parameter F if |P_L| ≤ k - F and |P_L ∩| ≥ F+1.



Since robustness analysis occurs prior to knowing which agents will become adversarial, all agents will be treated as either normal or leaders. Suppose k ≥ |P_L| and |P_L ∩| ≥ 2F+1. Let the first agent in P_L be labeled as agent (n-|P_L|+1) and the last agent in P_L as agent n. We must show that all nonempty C ⊆\ are (2F+1)-reachable. If agent 1 ∈ C then C is (2F+1)-reachable since {(n-|P_L|+1),…,n }⊆_1 which implies |_1∩ (\ C)| ≥ 2F+1. Next, suppose that agent 1 ∉ C and 2 ∈ C. Since {(n-|P_L|+2),…,1 }⊆_2, this implies that |_2∩ (\ C)| ≥ |_1∩ (\ C)| ≥ 2F+1 and therefore C is 2F+1-reachable. This reasoning can be continued inductively by assuming {1,… p-1}∉ C, p ∈ C, and observing that |_p∩ (\ C)| ≥ |_p-1∩ (\ C)|. Note that if p is ever the number of an agent in , then we need not consider it ever being in C and the analysis can be continued with the next normal agent. This reasoning can be continued through the entire network to show that all nonempty C are (2F+1)-reachable.

To prove the result for TLF robustness with parameter F, assume that agents are labeled in the same way as before. Note that {(n-|P_L|+1),…,n}⊆_j, ∀ j ∈{1,…,F}. Therefore agents 1 through F each have at least F+1 leaders as in-neighbors, i.e. |_j ∩| ≥ F+1 ∀ j ∈{1,…,F}. Therefore, if any of these agents are in C, the network satisfies the first condition of TLF robustness with parameter F. Now, assume that {1,…,F}∉ C and F+1 ∈ C. Note that {(n-|P_L|+1),…,n,1,…,F}⊆_F+1, and therefore |_F+1∩ (\ C)| ≥ 2F+1, satisfying the second condition of TLF robustness. A similar inductive method as the one used to prove (2F+1)-robustness can then be used to show that the network is TLF robust with parameter F.


As an example, suppose a k-circulant digraph has n=10 agents, k = 7, and F = 2 with agents {1,4,5} being leaders. The set of consecutive agents P_L = {1,2,3,4,5} satisfies |P_L| ≤ k - F and |P_L ∩| ≥ F+1. Therefore the digraph is TLF robust with parameter F=2. 



An undirected circulant graph of the form 𝒢 = C_n{± 1,± 2,…,± k} is strongly (2F+1)-robust with respect to  if 𝒢 contains a set of consecutive agents P_L such that |P_L| ≤ k and |P_L ∩| ≥ 2F+1. Moreover, 𝒢 satisfies the conditions for TLF robustness with parameter F if |P_L|≤ k-F and |P_L ∩| ≥ F+1.



The same method in Theorem <ref> can be applied to prove the result.


Because k-circulant graphs demonstrate properties of r-robustness, strong r-robustness, and TLF robustness, they can be used both for situations requiring consensus tracking and for situations requiring only resilient asymptotic consensus under the W-MSR algorithm. We point out that the properties of strong (2F+1)-robustness and TLF robustness are a two-edged sword: if the F-local adversary assumption is violated in a strongly (2F+1) or TLF robust network, a properly chosen set of misbehaving agents could potentially influence the network in a similar manner to a set of leaders.



§ SIMULATION


For our simulations, we consider agents in k-circulant digraphs. We assume the agents are trying to come to agreement on a state variable of interest such as altitude, the radius of a circular patrolling path (<cit.>), minimum inter-agent separation distance, etc. The implementation of the W-MSR algorithm among all agents serves as a distributed consensus manager to allow agents to reach agreement on the variable of interest. Once agreement is reached, agents can apply local control laws based on this variable (<cit.>). We emphasize that in these simulations, agents have no knowledge as to whether their in-neighbors are normal, malicious, or behaving as leaders. In all simulations, for all agents in (\) the agents' initial states are random values on the interval [-25,25].

For comparison, Figure <ref> shows 20 agents running the normal W-MSR protocol in an 15-circulant digraph (which is 8-robust) with F=3. The 3 malicious agents are {1,6,15}, and are indicated by the dotted red lines. The normal agents come to consensus to a value within the convex hull of their initial states.



The next simulation does not assume any trusted leaders (|∩| ≥ 0). In this simulation (Figure <ref>) n=30, k=15, and F=3. The agents initially behaving as leaders are agents {22, 23, 24, 25, 26, 27,28}. If we let P_L = {22,…,28}, we see that this set of consecutive agents satisfies |P_L ∩| ≥ 2F+1 and |P_L| ≤ k, and is therefore strongly 7-robust by Theorem <ref>. Here, leaders {22,26,28} are attacked and begin misbehaving. However, the normal agents are still able to converge to x_r[t], which is outside the interval [-25,25].




The third simulation demonstrates a scenario where the reference value is initially changing but remains constant after a particular time. In this simulation n=30, F=3, k=12. The agents initially designated to behave as leaders are {22, 23, 24, 25, 26 ,27, 28}, which again indicates a strongly 7-robust graph by Theorem <ref>. Again, the leaders are not assumed to be trusted, and it is assumed agents {22,26,28} misbehave. In this simulation, the value x_r[t] switches between the values 30, -20, and 0, finally remaining at 0 for the remainder of the simulation. The normal agents asymptotically approach x_r[t] on every interval where x_r[t] is constant.



The fourth simulation demonstrates the same network and parameters as the third simulation, except the misbehaving agents demonstrate unbounded ramp function behavior. Despite this unbounded behavior, the normal agents still converge to x_r[t].






§ CONCLUSION


In this paper, we outline conditions for networks operating under the W-MSR algorithm to achieve consensus to arbitrary reference values. Our future work will involve extending these results to the case of time-varying graphs, and considering reference signals with different dynamics.



IEEEtran


