Byzantine-Resilient Distributed Observers for LTI Systems
Aritra Mitra Shreyas Sundaram

theoremTheorem
problemProblem
conditionCondition
definitionDefinition
lemmaLemma
propositionProposition
corollaryCorollary
remarkRemark
assumptionAssumption
exampleExample



                                              
                                              
                                              

 
                                                

[footnoteinfo]This paper was not presented at any IFAC 
meeting. This research was supported in part by NSF CAREER award 1653648. Corresponding author: Aritra Mitra. Telephone of the corresponding author: 1-(765)-496-0406.

auth]Aritra Mitra and Shreyas Sundaram mitra14@purdue.edu sundara2@purdue.edu  
[auth]School of Electrical and Computer Engineering at Purdue University, West Lafayette, IN 47907, USA
         
                           Resilient state estimation; distributed estimation; Byzantine attacks.               
                             
                                          
                                          

                         
Consider a linear time-invariant (LTI) dynamical system monitored by a network of sensors, modeled as nodes of an underlying directed communication graph. We study the problem of collaboratively estimating the state of the system when certain nodes are compromised by adversaries. Specifically, we consider a Byzantine adversary model, where a
compromised node possesses complete knowledge of the system dynamics and the network, and can deviate arbitrarily
from the rules of any prescribed algorithm. We first characterize certain fundamental limitations of any distributed state estimation algorithm in terms of the measurement and communication structure of the nodes. We then develop an attack-resilient, provably correct state estimation algorithm that admits a fully distributed implementation. To characterize feasible network topologies that guarantee success of our proposed technique, we introduce a notion of `strong-robustness' that captures both measurement and communication redundancy. Finally, by drawing connections to bootstrap percolation theory, we argue that given an LTI system and an associated sensor network, the `strong-robustness' property can be checked in polynomial time.





 

§ INTRODUCTION

The control of large-scale complex networked systems such as power grids, transportation networks, and multi-agent robotic systems requires precise estimation of the state of the underlying dynamical process. Typically, in these applications, sensors (nodes) collecting information about the process are scattered over a geographical region. As the diameters of such networks increase, routing  information from all the sensors to a central computational resource induces large delays and creates communication bottlenecks. To bypass these difficulties, it thus becomes important to consider distributed algorithms where individual sensors communicate only with sensors within a given distance. However, the potential merits <cit.> of such a distributed approach are matched by various challenges. In particular, a key challenge is to design networks and distributed algorithms that guarantee reliable operation of the system in the face of faults or sophisticated adversarial attacks on certain sensors. This leads to the motivation behind our present work. 

In a classical distributed state estimation setup, each node receives partial measurements of the state of an LTI process, and seeks to asymptotically estimate the entire state by exchanging information with its neighbors in the network. Given that our primary focus will be on security related issues associated with this problem, we direct the interested reader to recent work on single-time-scale distributed observers in <cit.>. For literature on distributed Kalman filtering, see <cit.>. However, none of these papers address the challenges associated with tolerating unreliable components in the network. Accordingly, we now provide a survey of the cyber-security literature that is most relevant to our present cause.

Related Work: Over the last decade, a significant amount of research has focused on security in networked control systems. In particular, for noiseless dynamical systems, it has been established that zero-dynamics play a key role in characterizing the stealth of an attack <cit.>. For networked control systems affected by noise, the authors in <cit.> recently introduced an information-theoretic metric that quantifies the detectability of an attack. A unifying feature of <cit.>, and the ones in <cit.>, is that they involve systems where all the sensor measurements are available at a single location. In the sequel, we shall refer to such systems as centralized control systems. Our problem formulation and subsequent analysis differs from the above literature by constraining each sensor to exchange information with only its neighbors in the communication graph. Some recent related work on resilient distributed parameter estimation and resilient decentralized hypothesis testing are reported in <cit.> and <cit.>, respectively. The authors in <cit.> consider the problem of joint attack detection and state estimation. However, the attack model, the system model, and the assumptions on the communication graph in <cit.> differ considerably from the ones considered in this paper.

While the study of security in centralized control systems is now mature, there lacks a comprehensive theoretical understanding of analogous questions in a distributed setting. Preliminary attempts to counter adversarial behavior in a distributed state estimation context are reported in <cit.>,<cit.>. However, unlike our results, these papers neither provide any theoretical guarantees of success, nor allude to graph-theoretic conditions that are necessary for their respective algorithms to work. Recently, in <cit.>, the authors employ an H_∞ based approach for detecting biasing attacks in distributed estimation networks. Our present work deviates from <cit.> in several aspects, namely (i) while the analysis in <cit.> is limited to a certain class of attack inputs, our attack model allows compromised nodes to behave arbitrarily, i.e., no restrictions are placed on the inputs that can be injected by an adversary, (ii) unlike <cit.>, we develop a filtering algorithm that allows each uncompromised node to asymptotically recover the state of the plant without explicitly detecting the nodes under attack, and (iii) the existence of the attack detection filter proposed in <cit.> relies on solving an LMI; however, the authors neither provide graph-theoretic insights regarding the solvability of such an LMI nor discuss whether the LMI can be solved in a distributed manner.  In contrast, we detail graph-theoretic conditions that allow each step of our approach to have a resilient, distributed implementation. Summing up, this paper attempts to bridge the gap between centralized and distributed resilient state estimation. Our main contributions are discussed below.

Contributions: Our contributions are threefold. First, in Section <ref>, we characterize certain necessary conditions that need to be  satisfied by the sensor measurements and the communication graph for the distributed state estimation problem to be solvable in the presence of arbitrary adversarial behavior. Our results hold for any algorithm and hence identify fundamental limitations that are of both theoretical and practical importance in the design of attack-resilient robust networks. We also argue that our impossibility results in the distributed setting generalize those existing for centralized control systems subject to sensor attacks <cit.>. 

For the problem under consideration, it is imperative to understand which (potentially adversarial) neighbors a given node should listen to, and subsequently, how it should process the information received from neighbors it chooses to listen to. Consequently, our second contribution is to develop a distributed filtering algorithm in Section <ref> that enables each uncompromised node to recover the entire state dynamics, provided certain graph conditions are met. A thorough analysis of the proposed filtering scheme is then presented in Section <ref>. 

As our third contribution, in Section <ref>, we introduce a topological property called `strong-robustness' to characterize feasible systems and networks that guarantee applicability of our approach. By drawing connections to bootstrap percolation theory, we show that the `strong-robustness' property can be checked in polynomial time (in the size of the system and the network). 

Comparison with prior work by the authors: We reported certain preliminary results in <cit.>. In this paper, we significantly expand upon our prior work in the following ways. (i) While the analysis in <cit.> was limited to system matrices with real, distinct eigenvalues, our present framework allows the system matrix to have arbitrary spectrum. This generalization (accounting for complex, possibly repeated eigenvalues) requires various appropriate modifications to the algorithm developed in <cit.>, along with a more detailed technical analysis. (ii) Section <ref> is a new addition entirely, and discusses fundamental limitations of any distributed state estimation algorithm in the face of arbitrary adversarial attacks. (iii) Section <ref> contains additional details about properties of feasible network topologies, and establishes the key result that the topological condition (namely `strong-robustness') needed for implementing our proposed algorithm can be checked in polynomial time. The latter result (missing in <cit.>) is particularly important since it highlights the applicability of our overall approach.

 Notation: A directed graph is denoted by 𝒢 =(𝒱,ℰ), where 𝒱 ={1, ⋯, N} is the set of nodes and ℰ⊆𝒱×𝒱 represents the edges. An edge from node j to node i, denoted by (j,i), implies that node j can transmit information to node i. The neighborhood of the i-th node is defined as 𝒩_i ≜{j | (j,i) ∈ℰ}. A node j is said to be an out-neighbor of node i if (i,j)∈ℰ. By an induced subgraph of 𝒢 obtained by removing certain nodes 𝒞⊂𝒱, we refer to the subgraph that has 𝒱∖𝒞 as its node set and contains only those edges of ℰ with both end points in 𝒱∖𝒞. The notation |𝒱| is used to denote the cardinality of a set 𝒱. The set of all eigenvalues (or modes) of a matrix 𝐀 is denoted by sp(𝐀) = {λ∈ℂ | det(𝐀-λ𝐈) = 0}, and the set of all unstable eigenvalues by Λ_U(𝐀) = {λ∈ sp(𝐀) |  |λ| ≥ 1 }. We use a_𝐀(λ) and g_𝐀(λ) to denote the algebraic and geometric multiplicities, respectively, of an eigenvalue λ∈ sp(𝐀). An eigenvalue λ is said to be simple if a_𝐀(λ)=g_𝐀(λ)=1. Given a set of matrices {𝐀_1, ⋯, 𝐀_n}, we use diag(𝐀_1, ⋯, 𝐀_n) to refer to a block diagonal matrix with 𝐀_i as its i-th block entry. For a set 𝒥={m_1, ⋯, m_|𝒥|}⊆{1, ⋯, N}, and a matrix 𝐂=[ 𝐂^T_1     ⋯ 𝐂^T_N ]^T, we define 𝐂_𝒥≜[   𝐂^T_m_1         ⋯ 𝐂^T_m_|𝒥| ]^T. The identity matrix of dimension r is denoted 𝐈_r, and ℕ_+ is used to refer to the set of all positive integers. The terms `communication graph' and `network' are used interchangeably, and the  term `resilient' is used in the same context as that used traditionally in the computer science literature to deal with worst-case adversarial attack models <cit.>.
 


§ SYSTEM AND ATTACK MODEL

System Model: Consider the LTI dynamical system

    𝐱[k+1] = 𝐀𝐱[k],

where k ∈ℕ is the discrete-time index, 𝐱[k] ∈ℝ^n is the state vector and  𝐀∈ℝ^ n × n is the system matrix. The system is monitored by a network 𝒢=(𝒱,ℰ) consisting of N nodes. The i-th node receives a measurement of the state, given by

    𝐲_i[k]=𝐂_i𝐱[k],

where 𝐲_i[k] ∈ℝ^r_i and 𝐂_i ∈ℝ^r_i × n. We use 𝐂=[ 𝐂^T_1     ⋯ 𝐂^T_N ]^T to represent the collection of the individual node observation matrices; accordingly, 𝐲[k]=[ 𝐲^T_1[k]        ⋯ 𝐲^T_N[k] ]^T represents the collective measurement vector, i.e., 𝐲[k]=𝐂𝐱[k].

Each node is tasked with estimating the entire system state 𝐱[k] based on information received from its neighbors and its local measurements (if any). As such, we assume that the pair (𝐀,𝐂) is detectable (this is a necessary condition for solving the distributed state estimation problem even in the absence of adversaries); however, we do not assume that the pair (𝐀,𝐂_i) is detectable for any i ∈𝒱. Two immediate challenges are as follows: (i) As the pair (𝐀,𝐂_i) may not be detectable for some (or all) i∈{1, ⋯, N}, information exchange is necessary; and (ii) information exchange is restricted by the underlying communication graph 𝒢. 
In addition to the above challenges, in this paper, we allow for the possibility that certain nodes in the network are compromised by an adversary, and do not follow their prescribed state estimate update rule. We will use the following adversary model in this paper.

Adversary Model: We consider a subset 𝒜⊂𝒱 of the nodes in the network to be adversarial. We assume that the adversarial nodes are completely aware of the network topology, the system dynamics and the algorithm employed by the non-adversarial nodes. Such an assumption of omniscient adversarial behavior is standard in the literature on resilient distributed algorithms <cit.>, and allows us to provide guarantees against “worst-case" adversarial behavior. In terms of capabilities, an adversarial node can leverage the aforementioned information to arbitrarily deviate from the rules of any prescribed algorithm, while colluding with other adversaries in the process. Furthermore, following the Byzantine fault model<cit.>, adversaries are allowed to send differing state estimates to different neighbors at the same instant of time. To characterize the threat model in terms of the number of adversaries in the network, we will use the following definitions from <cit.>,<cit.>.

 (f-total set)
A set 𝒞⊂𝒱 is f-total if it contains at most f nodes in the network, i.e., | 𝒞| ≤ f.

 (f-local set)
A set 𝒞⊂𝒱 is f-local if it contains at most f nodes in the neighborhood of the other nodes, i.e., |𝒩_i ∩𝒞| ≤ f, ∀ i ∈𝒱∖𝒞.

 (f-local and f-total adversarial models) A set 𝒜 of adversarial nodes is f-locally bounded (resp., f-totally bounded) if 𝒜 is an f-local (resp., f-total) set.

In the literature dealing with distributed fault-tolerant algorithms, it is a common assumption to consider an f-total adversarial model. However, to allow for a large number of adversaries in large scale networks, we will allow the adversarial set to be f-local. Summarily, the adversary model considered throughout this paper will be referred to as an f-locally bounded Byzantine adversary model. The non-adversarial nodes will be referred to as regular nodes and be represented by the set ℛ=𝒱∖𝒜. Note that the actual number and identities of the adversarial nodes are not known to the regular nodes.  As is standard, any reliable system is designed to provide a desired level of resilience against a maximum number of component failures or attacks. We share the same philosophy. Specifically, we assume that each node in the network is programmed to tolerate upto a maximum of f adversaries in the entire network (in an f-total model) or in its own neighborhood (in an f-local model). Such an assumption is typical in the design of distributed protocols (for varied applications, such as consensus <cit.>, optimization <cit.>, and broadcasting <cit.>) that are resilient to worst-case Byzantine attack models like the one considered in this paper.

Throughout this paper, we shall only consider causal (i.e., nodes act only on past and present information), synchronous (i.e., all nodes share a common clock w.r.t. their iterates), and deterministic algorithms (i.e., given the same input, such algorithms generate the same output); note however that the notions of causal and deterministic behavior apply only to the regular nodes.  We shall also assume that all quantities being updated iteratively by the regular nodes are initialized identically in each execution. With 𝐱̂_i[k] representing the estimate of 𝐱[k] maintained by node i, the problem studied in this paper can be formally stated as follows.
 
(Resilient Distributed State Estimation) Given an LTI system (<ref>), a linear measurement model (<ref>), and a time-invariant directed communication graph 𝒢, design a set of state estimate update and information exchange rules such that lim_k→∞ ||𝐱̂_i[k]-𝐱[k]||=0, ∀ i ∈ℛ, regardless of the actions of any f-locally bounded set of Byzantine adversaries.


The interplay between the measurement structure of the nodes and the underlying communication graph results in certain conditions being necessary for solving Problem 1, irrespective of the choice of algorithms. We provide such conditions in the following section.



§ FUNDAMENTAL LIMITATIONS OF ANY DISTRIBUTED STATE ESTIMATION ALGORITHM


Intuitively, the network must possess a certain degree of measurement redundancy as well as redundancy in its communication structure so as to counteract the effects of adversarial behavior. More specifically, the measurements of the regular nodes must ensure collective detectability of the state, and the network structure should prevent the malicious nodes from acting as bottlenecks between correctly functioning nodes. To identify necessary conditions for resilient distributed state estimation that capture the above notions of redundancy, we first introduce some terminology. 



 (Critical Set) A set of nodes ℱ⊂𝒱 is said to be a critical set if the pair (𝐀,𝐂_𝒱∖ℱ) is not detectable.


Note that detectability of (𝐀,𝐂) implies that a critical set must necessarily be non-empty.

 (Minimal Critical Set) A set ℱ⊂𝒱 is said to be a minimal critical set if ℱ is a critical set and no subset of ℱ is a critical set.


Let ℳ={ℱ_1, ⋯, ℱ_|ℳ|} denote the set of all minimal critical sets. With each set ℱ_i ∈ℳ, we associate a virtual node s_i as follows. Directed edges are added from s_i to each node in ℱ_i and the resulting network is denoted by 𝒢^'_i=(𝒱∪ s_i, ℰ∪ℰ_i), where ℰ_i represents the set of edges from s_i to ℱ_i. 

(f-local pair and f-total pair cuts w.r.t. s_i) Consider a minimal critical set ℱ_i ∈ℳ. A set ℋ⊂𝒱 is called a cut w.r.t. s_i if removal of ℋ from 𝒢^'_i results in an induced subgraph of 𝒢^'_i whose node set can be partitioned into two non-empty sets 𝒳 and 𝒴 with s_i ∈𝒳, and no directed paths from 𝒳 to 𝒴 in the induced subgraph. A cut ℋ w.r.t. s_i is called an f-local pair cut (resp., f-total pair cut) w.r.t. s_i if it can be partitioned as ℋ= ℋ_1 ∪ℋ_2 such that both ℋ_1 and ℋ_2 are f-local (resp., f-total) in 𝒢.



For an illustration of the above definitions, see Figure <ref>. The following result identifies a fundamental limitation for f-local adversarial models.

 Suppose there exists an f-local pair cut w.r.t. s_i in 𝒢^'_i for some minimal critical set ℱ_i∈ℳ. Then, it is impossible for any causal, synchronous and deterministic algorithm to solve Problem 1.




 Suppose there exists an f-local pair cut ℋ=ℋ_1∪ℋ_2 w.r.t. s_i for some minimal critical set ℱ_i ∈ℳ. For the sake of contradiction, suppose there exists a causal, synchronous and deterministic algorithm 𝒯 that solves Problem 1 for the given network 𝒢. From the definition of ℋ, we see that 𝒴 contains no elements of ℱ_i. Since ℱ_i is a critical set, it then follows that the pair (𝐀,𝐂_𝒴) is not detectable. Thus, there exists an initial condition 𝐱[0]=η that causes the measurement set 𝐲_𝒴[k] corresponding to 𝒴 to be identically zero for all time, while the state 𝐱[k] remains bounded away from zero. The idea of the proof will be to demonstrate that the nodes in 𝒴 cannot distinguish between the zero initial condition and the initial condition η under an appropriately constructed attack. To this end, noting that each of the sets ℋ_1 and ℋ_2 are f-local and can hence act as valid adversarial sets, we consider the following executions σ and σ' of 𝒯. 

Execution σ: The initial condition is 𝐱[0]=0. The nodes in ℋ_1 are regular while the nodes in ℋ_2 are adversarial. The nodes in ℋ_2 pretend that their state estimates are 𝐱̂_ℋ_2[k] and that their measurements are 𝐂_ℋ_2𝐀^kη, where 𝐱̂_ℋ_2[k] represents the collection of the state estimates maintained by the nodes in ℋ_2 during the execution σ' of 𝒯. Additionally, at each time-step, the nodes in ℋ_2 perform the exact same actions that they perform during the execution σ'.
 
Execution σ': The initial condition is 𝐱[0]=η. The nodes in ℋ_2 are regular while the nodes in ℋ_1 are adversarial. The nodes in ℋ_1 pretend that their state estimates are 𝐱̂_ℋ_1[k] and that their measurements are zero, where 𝐱̂_ℋ_1[k] represents the collection of the state estimates maintained by the nodes in ℋ_1 during the execution σ of 𝒯. Additionally, at each time-step, the nodes in ℋ_1 perform the exact same actions that they perform during the execution σ.

Since the actions of the adversaries in the two executions described above are coupled, it becomes important to establish that such actions are in fact well-defined. To do so, we argue as follows. Consider the actions of the adversarial set ℋ_2 at time k=0 of execution σ. Due to their omniscient nature, these adversaries can anticipate the information that a regular set ℋ_2 is supposed to transmit at time k=0 of execution σ' based on algorithm 𝒯.  Thus, their actions are well-defined at time k=0. Note that the last two statements rely on the deterministic nature of 𝒯. Specifically, under a deterministic algorithm 𝒯, the actions of the regular nodes are also deterministic, and hence, can be predicted in advance by an omniscient adversary who is aware of the information set available to such regular nodes. An identical argument defines the actions of the adversarial set ℋ_1 at time k=0 of execution σ'. Since the actions of both the sets ℋ_1 and ℋ_2 at time k=0 are well-defined in each of the executions σ and σ', the response of the regular nodes to such actions (in the respective executions) at time k=1 can be anticipated by any adversarial set. Specifically, to generate their actions at time k=1 of execution σ (resp., execution σ'), the adversarial set ℋ_2 (resp., ℋ_1) simply simulates execution σ' (resp., execution σ) for time k=0 to figure out how a regular set ℋ_2 (resp., ℋ_1) would act at time k=1 of execution σ' (resp., execution σ). Repeating the above argument reveals that the actions of the respective adversarial sets in each of the executions σ and σ' are well-defined at every time step.

Based on the attack described above, it is clear that the nodes in 𝒴 receive the same state estimate and measurement information from the nodes in ℋ in each of the two executions. Further, their own measurements are identically zero for all time in each of the two executions. Hence, based on such identical information, it is impossible for the nodes in 𝒴 to resolve the difference in the underlying initial conditions via algorithm 𝒯. This leads to the desired contradiction and completes the proof.


 Interestingly, the necessary condition presented in the above theorem bears close resemblance to the necessary condition in <cit.> for resilient broadcasting subject to the same f-local Byzantine adversary model that we consider here. This similarity can be attributed to the following analogy: viewing the virtual nodes as originators of messages in a broadcasting context, Problem 1 can be interpreted as a version of the resilient broadcasting problem where the regular nodes are required to agree (asymptotically) on a time-varying message that captures the state evolution of the system. 

 
Our next result provides a necessary condition for an f-total (and hence, also an f-local) adversarial model.

 Suppose there exists a causal, synchronous and deterministic algorithm that solves the variant of Problem 1 corresponding to an f-total Byzantine adversary model. Then, the following equivalent statements are true.



  (i) Consider any minimal critical set ℱ_i ∈ℳ. There exists no f-total pair cut w.r.t. s_i.

  (ii) Consider a node i ∈𝒱 such that (𝐀,𝐂_i) is not detectable. Let 𝒳_i denote the set of all nodes in 𝒢 that have directed paths to node i, and consider a set 𝒟_i ⊆𝒳_i such that |𝒟_i| ≤ 2f. Let 𝒫_i ⊆𝒳_i represent the set of nodes that have directed paths to node i in the induced subgraph obtained by removing 𝒟_i from 𝒢. Then, (𝐀,𝐂_i ∪𝒫_i) is detectable.




The proof of necessity mimics the proof of Theorem <ref>, while the equivalence between the two conditions stated in Theorem <ref> is established in Appendix <ref>.

 
In <cit.>, the authors showed that for centralized systems subject to f sensor attacks, a necessary condition for estimating the state asymptotically is that the system should remain detectable after the removal of any 2f sensors. In our present distributed setting, the maximum information about the state that any given node i can hope to obtain is from the set {i∪𝒳_i}, where 𝒳_i is defined as in Theorem <ref>. Thus, the second part of Theorem <ref> generalizes the necessary conditions in <cit.>. In <cit.>, the authors established that the graph-connectivity metric plays a pivotal role in the analysis of fault-tolerant and resilient distributed consensus algorithms for settings where there are no underlying state dynamics that need to be estimated. The results stated in Theorems <ref> and <ref> differ from those in <cit.> since they blend both graph-theoretic and system-theoretic requirements. Finally, it can be easily shown that when there are no adversaries, i.e., when f=0, the conditions identified in Theorem <ref> reduce to the necessary and sufficient condition for distributed state estimation, namely every source component (strong components with no incoming edges) of the graph should be detectable <cit.>.
 

We now discuss certain implications of Theorem <ref>.
Given an LTI system (<ref>), a measurement model specified by (<ref>), and a communication graph 𝒢, it is of both theoretical and practical interest to know the maximum number of adversaries that can be tolerated when one seeks to solve Problem 1. Leveraging Theorem <ref>, we can provide an upper bound on this number, as follows.


Let k denote the smallest positive integer such that there exists a k-total pair cut w.r.t. s_i for some ℱ_i∈ℳ. Then, the total number of adversaries f must satisfy the inequality f < k for Problem 1 to have a solution.[Similar bounds for static power system models subject to attacks were obtained in <cit.>.]



 
The condition |ℱ_i| ≥ (2f+1) ∀ℱ_i ∈ℳ is necessary for resilient distributed state estimation subject to the f-local or f-total adversarial model.


The proof of the above result is straightforward and is hence omitted here.
With the above corollary in hand, one can gain insights regarding the distribution of certain specific critical sets in the network. To do so, given an eigenvalue λ_j ∈Λ_U(𝐀), let {ρ^(j)_1, ⋯, ρ^(j)_g_𝐀(λ_j)} represent a basis for the null space of (𝐀-λ_j𝐈_n), and let ϕ^(j)_i=span{ρ^(j)_i}, i∈{1,⋯,g_𝐀(λ_j)}. We say that node i can detect the subspace ϕ^(j)_i  if 𝐂_iρ^(j)_i ≠0.[Throughout the paper, for the sake of conciseness, we use the terminology “node i can detect eigenvalue λ_j" to imply that rank[[ 𝐀-λ_j𝐈_n;      𝐂_i ]] = n. Each stable eigenvalue is considered detectable w.r.t. the measurements of every node.] Let 𝒲^(j)_i ⊆𝒱 denote the set of all nodes that can detect ϕ^(j)_i. The next result then readily follows from Corollary <ref> and the classical PBH test <cit.>.


For each λ_j ∈Λ_U(𝐀), if 𝒲^(j)_i ⊂𝒱, where 1≤ i ≤ g_𝐀(λ_j), then  |𝒲^(j)_i| ≥ (2f+1) is a necessary condition for resilient distributed state estimation subject to the f-local or f-total adversarial model.


For systems with distinct eigenvalues, a direct consequence of the above result is the requirement of at least (2f+1) nodes that can detect each unstable eigenvalue of the system. The preceding analysis builds up to the distributed estimation strategy adopted in  this paper. In particular, our approach involves identifying the locally detectable and undetectable eigenvalues associated with a given node, and subsequently devising separate estimation strategies for the subspaces associated with such eigenvalues. We formalize this idea in the next section.

 Two important directions of future investigation are (i) finding an efficient algorithm (if one exists) for computing k in Corollary <ref> either exactly or approximately, and (ii) determining whether the conditions stated in Theorem 1 (resp., Theorem 2) are sufficient for achieving resilient distributed state estimation subject to an f-local (resp., f-total) Byzantine adversary model. Note that the main source of computational complexity associated with the first point lies in finding all the minimal critical sets associated with the given system.




§ RESILIENT DISTRIBUTED STATE ESTIMATION




 §.§ Preliminaries


For each eigenvalue λ∈ sp(𝐀), let 𝐕(λ) represent a block diagonal matrix with the Jordan blocks corresponding to λ (in the standard Jordan canonical representation of 𝐀) along the main block diagonal. We begin by recalling certain properties of the real Jordan canonical form of a square matrix that will be useful for our subsequent development <cit.>. We first note that if λ represents a non-real eigenvalue of 𝐀 and λ̅ represents its complex-conjugate, then <cit.> ensures that λ and λ̅ have the same Jordan structure. Next, let λ=a+ib where a,b ∈ℝ, and i=√(-1). Let 𝐃(a,b) be defined as 𝐃(a,b)≜[  a  b; -b  a ]. Then, the matrix diag(𝐕(λ),𝐕(λ̅)) is similar to a real block upper triangular matrix 𝐖(λ)∈ℝ^2a_𝐀(λ)× 2a_𝐀(λ) which has a_𝐀(λ) 2-by-2 blocks 𝐃(a,b) on the main block diagonal and (a_𝐀(λ)-1) blocks 𝐈_2 on the block superdiagonal.  Henceforth, for a non-real eigenvalue λ∈ sp(𝐀), 𝐖(λ) will have the meaning  discussed above. Let sp(𝐀)={{λ_1,λ̅_1}, ⋯, {λ_p,λ̅_p}, λ_p+1, ⋯, λ_γ} with the first p pairs representing the non-real eigenvalues, and λ_p+1 to λ_γ representing the real eigenvalues of 𝐀. Then, the real Jordan canonical form theorem <cit.> can be stated as follows.
 There exists a real similarity transformation matrix 𝐓 that transforms the state transition matrix 𝐀 in (<ref>) to a real block diagonal matrix 𝐌 given by 𝐌=diag(𝐖(λ_1), ⋯, 𝐖(λ_p), 𝐕(λ_p+1), ⋯, 𝐕(λ_γ)).



With 𝐓 as in the above theorem, and 𝐳[k]=𝐓^-1𝐱[k], the dynamics (<ref>) are  transformed into the form

    𝐳[k+1]    = 𝐌𝐳[k] 
    𝐲_i[k]    = 𝐂̅_i𝐳[k],   ∀ i ∈{1, ⋯, N}

where 𝐌=𝐓^-1𝐀𝐓 and 𝐂̅_i=𝐂_i𝐓.









For a non-real eigenvalue pair {λ_j,λ̅_j}∈ sp(𝐀), let 𝐳^(j)[k] ∈ℝ^2a_𝐀(λ_j) represent the portion of the state 𝐳[k] associated with the matrix 𝐖(λ_j). Similarly, for a real eigenvalue λ_j∈ sp(𝐀), 𝐳^(j)[k] ∈ℝ^a_𝐀(λ_j) is the portion of the state 𝐳[k] associated with the matrix 𝐕(λ_j). For each node i, we denote the detectable and undetectable eigenvalues by the sets 𝒪_i and 𝒪_i, respectively. Next, we introduce the notion of source nodes.


(Source nodes)
For each λ_j ∈Λ_U(𝐀), the set of nodes that can detect λ_j is denoted by 𝒮_j, and called the set of source nodes for λ_j.


We now proceed to develop an estimation scheme that enables each regular node to estimate 𝐳[k] (from which they can obtain 𝐱[k]=𝐓𝐳[k]). Accordingly, let 𝐳̂^(j)_i[k] denote the estimate of 𝐳^(j)[k] (the portion of 𝐳[k] corresponding to the eigenvalue λ_j[Throughout the rest of the paper, the terminology “𝐳^(j)[k] corresponds to the eigenvalue λ_j" should be interpreted as 𝐳^(j)[k] corresponds to the eigenvalue pair {λ_j,λ̅_j} for a non-real eigenvalue λ_j∈ sp(𝐀).]) maintained by node i∈ℛ. For each λ_j∈Λ_U(𝐀), our estimation scheme relies on separate strategies for nodes in 𝒮_j and 𝒱∖𝒮_j. In particular, each node in 𝒮_j employs a Luenberger observer for estimating 𝐳^(j)[k]. The nodes in 𝒱∖𝒮_j, on the other hand, cannot detect the eigenvalue λ_j, and thus rely on a resilient consensus algorithm to estimate 𝐳^(j)[k]. In what follows, we discuss these ideas in detail.

The first step in the estimation process involves the above common coordinate transformation given by 𝐳[k]=𝐓^-1𝐱[k], to be performed by each regular node of the graph. As this only requires knowledge of the system matrix 𝐀 (which is assumed to be known by all the nodes), all of the nodes can do this in a distributed manner (e.g., by using an agreed-upon convention for ordering the eigenvalues and corresponding eigenvectors). Building on the general theme in <cit.>, we first present a method that allows a regular node i∈ℛ to estimate the locally detectable portion of the state 𝐳[k] without communicating with neighbors. To this end, consider the following result. 


Let λ_j ∈𝒪_i be a non-real eigenvalue. Let 𝐂̅^(j)_i denote the columns of 𝐂̅_i corresponding to 𝐖(λ_j) in (<ref>). Then, the pair (𝐖(λ_j),𝐂̅^(j)_i) is detectable.


 We claim that λ_j ∈𝒪_i if and only if λ̅_j ∈𝒪_i. It suffices to prove necessity since the proof for sufficiency will follow an identical argument. We prove necessity by contradiction. Suppose node i can detect λ_j (i.e., λ_j ∈𝒪_i), but cannot detect λ̅_j. Then, there exists 𝐯≠0 such that 𝐀𝐯=λ̅_j𝐯 and 𝐂_i𝐯=0. Taking complex conjugates on both sides of these equations reveals that node i cannot detect λ_j, leading to the desired contradiction. Given that a similarity transformation maps (𝐀,𝐂_i) to (𝐌,𝐂̅_i), it then follows that {λ_j,λ̅_j} are detectable eigenvalues w.r.t. (𝐌,𝐂̅_i). Detectability of the pair (𝐖(λ_j),𝐂̅^(j)_i) then follows readily from the PBH test by noting the structure of the matrix 𝐌.


Let 𝒪_i={{λ_n_1,λ̅_n_1}, ⋯, {λ_n_p_i,λ̅_n_p_i}, λ_n_p_i+1, ⋯, λ_n_γ_i}, where the first p_i pairs represent the non-real eigenvalues, and λ_n_p_i+1 to λ_n_γ_i represent the real eigenvalues of 𝐀 that are detectable w.r.t. the measurements of node i. Let 𝐌_𝒪_i = diag(𝐖(λ_n_1), ⋯, 𝐖(λ_n_p_i), 𝐕(λ_n_p_i+1), ⋯,
 𝐕(λ_n_γ_i)). Let 𝐂_𝒪_i represent the columns of 𝐂̅_i corresponding to the matrix 𝐌_𝒪_i, and 𝐳_𝒪_i[k] denote the portion of the state 𝐳[k] corresponding to the detectable eigenvalues of node i, i.e., corresponding to 𝒪_i. Based on Lemma <ref>, it is easy to see that the pair (𝐌_𝒪_i, 𝐂_𝒪_i) is detectable. Thus, a standard Luenberger observer can be locally constructed by node i for estimating 𝐳_𝒪_i[k]. The details of such a construction are straightforward, and are similar to those in Section VI-A of <cit.>. We thus skip minor details and state the following result which will be useful later on.
 

For each regular node i ∈ℛ and each λ_j ∈𝒪_i, a Luenberger observer can be locally constructed by node i such that lim_k→∞||𝐳̂^(j)_i[k]-𝐳^(j)[k]||=0.



Based on the previous result, we see that a regular node i can estimate certain portions of the state space without having to exchange information with neighbors. The challenge, however, lies in estimating the locally undetectable portion of the state in the presence of adversaries. The following section presents a resilient consensus based strategy to address this issue.



 §.§ Local-Filtering Based Resilient Estimation


 For any λ_j ∈ sp(𝐀), let z^(jm)[k] denote the m-th component of the vector 𝐳^(j)[k], and let ẑ^(jm)_i[k] denote the estimate of that component maintained by node i∈𝒱. Consider an unstable eigenvalue λ_j ∈ 𝒪_i. For such an eigenvalue, node i has to rely on the information received from its neighbors, some of which might be adversarial, in order to estimate 𝐳^(j)[k]. To this end, we propose a  resilient consensus algorithm that requires each regular node i ∈𝒱∖𝒮_j to update its estimate of 𝐳^(j)[k] using the following two stage filtering strategy:


  1) At each time-step k, each regular node i collects the state estimates of 𝐳^(j)[k] received from only those neighbors that belong to a certain subset 𝒩^(j)_i ⊆𝒩_i (to be defined later). For every component m of 𝐳^(j)[k], the estimates of z^(jm)[k] received from nodes in 𝒩^(j)_i are sorted from largest to smallest.

  2) For each component m of 𝐳^(j)[k], node i removes the largest and smallest f estimates (i.e., removes 2f estimates in all) of z^(jm)[k] received from nodes in 𝒩^(j)_i, and computes the quantity:

    z̅^(jm)_i[k]=∑_l ∈ℳ^(jm)_i[k]w^(jm)_il[k]ẑ^(jm)_l[k],

where ℳ^(jm)_i[k] ⊂𝒩^(j)_i (⊆𝒩_i) is the set of nodes from which node i chooses to accept estimates of z^(jm)[k] at time-step k, after removing the f largest and f smallest estimates of z^(jm)[k] from 𝒩^(j)_i. Node i assigns the weight w^(jm)_il[k] to the l-th node at the k-th time-step for estimating the m-th component of 𝐳^(j)[k]. The weights are nonnegative and chosen to satisfy ∑_l ∈ℳ^(jm)_i[k]w^(jm)_il[k]=1, ∀λ_j ∈ 𝒪_i and for each component m of 𝐳^(j)[k]. With the quantities z̅^(jm)_i[k] in hand, node i updates 𝐳̂^(j)_i[k] as follows:

    𝐳̂^(j)_i[k+1]=
        𝐕(λ_j)𝐳̅^(j)_i[k],    if λ_j ∈𝒪_i is real
    𝐖(λ_j)𝐳̅^(j)_i[k],    if λ_j ∈𝒪_i is not real,

where 𝐳̅^(j)_i[k]=[ z̅^(j1)_i[k], ⋯, z̅^(jσ_j)_i[k] ]^T, σ_j=a_𝐀(λ_j) if λ_j∈𝒪_i is real, and σ_j=2a_𝐀(λ_j) if λ_j∈𝒪_i is not real.

We refer to the above algorithm as the Local-Filtering based Resilient Estimation (LFRE) algorithm. For implementing this algorithm, a regular node i needs to construct the set 𝒩^(j)_i, ∀λ_j ∈ 𝒪_i, based on the relative positions of its neighbors (with respect to its own position) in  𝒢. We will provide the exact definition of 𝒩^(j)_i, and a distributed algorithm for constructing such a set in the following sections where we analyze the convergence of the LFRE algorithm. We conclude this section by commenting on certain features of the LFRE algorithm.


The rationale behind performing a real Jordan canonical decomposition at every node (as opposed to a standard Jordan transformation) is to ensure that the state estimates featuring in equations (<ref>) and (<ref>) are real at every time-step, thereby making the sorting operation performed in Step 1 of the algorithm meaningful. At any time-step, if a regular node i either receives a non-real estimate of z^(jm)[k] from some node l ∈𝒩^(j)_i or does not receive an estimate at all, it would immediately identify node l as an adversarial node, and simply assign a 0 value to node l's estimate of z^(jm)[k]. Note that every regular node in 𝒩^(j)_i will always transmit a real estimate to node i at every time-step.



The strategy of disregarding the most extreme values in one's neighborhood, and using a convex combination of the rest for performing linear scalar updates, has been used for designing resilient distributed algorithms for consensus <cit.> and optimization <cit.> problems. In this paper, we show that such algorithms can also be used for resilient distributed state estimation, with certain substantial differences arising from the fact that the nodes are trying to track the state of an external dynamical system.


 The consensus weights w^(jm)_il appearing in equation (<ref>) can be chosen arbitrarily to achieve an exponential rate of convergence, as long as the weights meet the rules specified by the LFRE algorithm. Since our primary focus is on resilience against worst-case adversarial behavior, the problem of optimizing such weights (or exploiting sensor memory) for achieving improved performance against noise is not considered in this paper. In a non-adversarial setting (i.e., when f=0), the proposed LFRE algorithm will continue to guarantee exponential convergence in the absence of noise, and bounded mean square error in the presence of i.i.d. noise with bounded second moments (provided the topological conditions outlined in Section <ref> are met). However, disregarding the estimates of certain neighbors in the absence of attacks may potentially degrade performance against noise; we do not delve deeper into this topic here.


It should be noted that the algorithmic development in this section can be considerably simplified if more structure is imposed on the system matrix 𝐀 (for instance, the assumption made in <cit.> that 𝐀 has only real, distinct eigenvalues).


§ ANALYSIS OF THE RESILIENT DISTRIBUTED ESTIMATION STRATEGY


In this section, we provide our main result concerning the convergence of the LFRE algorithm. Let Ω_U(𝐀) ≜{λ_j ∈Λ_U(𝐀)| 𝒱∖𝒮_j  is non-empty}. By this definition, all nodes are source nodes for each eigenvalue in Λ_U(𝐀) ∖Ω_U(𝐀), and are hence capable of recovering the corresponding portions of the state based on locally constructed Luenberger observers (as discussed in Section <ref>). Consequently, the LFRE algorithm specifically applies to only those eigenvalues that belong to Ω_U(𝐀). Consider the following definition.




(Mode Estimation Directed Acyclic Graph (MEDAG)) Consider an eigenvalue λ_j ∈Ω_U(𝐀). Suppose there exists a spanning subgraph 𝒢_j = (𝒱,ℰ_j) of 𝒢  with the following properties for all f-local sets 𝒜 and ℛ=𝒱∖𝒜.


  (i) If i ∈{𝒱∖𝒮_j}∩ℛ, then |𝒩^(j)_i| ≥ 2f+1, where 𝒩^(j)_i={l|(l,i) ∈ℰ_j} represents the neighborhood of node i in 𝒢_j.

  (ii) There exists a partition of ℛ into the sets {ℒ^(j)_0, ⋯ , ℒ^(j)_T_j}, where T_j ∈ℕ_+, ℒ^(j)_0 = 𝒮_j ∩ℛ, and if i ∈ℒ^(j)_q (where 1 ≤ q ≤ T_j), then 𝒩^(j)_i ∩ℛ⊆⋃^q-1_r=0ℒ^(j)_r. Furthermore, 𝒩^(j)_i=∅, ∀ i ∈ℒ^(j)_0.

Then, we call 𝒢_j a Mode Estimation Directed Acyclic Graph (MEDAG) for λ_j ∈Ω_U(𝐀).

An example of a MEDAG is shown in Figure <ref>.
The “for all 𝒜" in the definition accounts for the fact that the set of adversarial nodes during the process of state estimation is unknown, and hence can be any f-local set of 𝒱. Note that T_j and the levels ℒ^(j)_0 to ℒ^(j)_T_j can vary across different f-local sets. For a given f-local set 𝒜, we say a regular node i∈ℒ^(j)_m “belongs to level m", where the levels are indicative of the distances of the regular nodes from the source set 𝒮_j. The first property indicates that every regular node i ∈𝒱∖𝒮_j has at least (2f+1) neighbors in the subgraph 𝒢_j, while the second property indicates that all its regular neighbors in such a subgraph belong to levels strictly preceding its own level. In essence, the edges of the MEDAG 𝒢_j represent a medium for transmitting information securely from the source nodes 𝒮_j to the non-source nodes, by preventing the adversaries from forming a bottleneck between such nodes. Intuitively, this requires redundant nodes and edges, and such a requirement is met by the first property of the MEDAG. In particular, as regards measurement redundancy, it follows from the definition that for each λ_j ∈Ω_U(𝐀), a MEDAG 𝒢_j contains at least (2f+1) source nodes that can detect λ_j.[Recall from the discussion immediately following Proposition <ref> that such a condition is in fact necessary for systems with distinct eigenvalues.] The LFRE algorithm described in the previous section relies on a special uni-directional information flow pattern that requires a node i to listen to only its neighbors in 𝒩^(j)_i for estimating 𝐳^(j)[k]. The second property of a MEDAG then indicates that nodes in level m only use the estimates of regular nodes in levels 0 to m-1 for recovering 𝐳^(j)[k]. The implications of the above properties will become apparent in the proof of the following result which provides a sufficient condition for solving Problem 1 based on our approach.

 Suppose that 𝒢 contains a MEDAG 𝒢_j for each λ_j ∈Ω_U(𝐀). Then, based on the LFRE dynamics described by equations (<ref>) and (<ref>), each regular node i∈ℛ can asymptotically estimate the state of the plant, despite the actions of any f-locally bounded set of Byzantine adversaries.


The proof of the above theorem is given in Appendix <ref>. Notice that Theorem <ref> hinges on the existence of a MEDAG 𝒢_j, for each λ_j ∈Ω_U(𝐀); in the following section we describe an approach for checking whether a given graph 𝒢 contains such MEDAGs.


§ CHECKING THE EXISTENCE OF A MEDAG

 
From the foregoing discussion, it is apparent that the MEDAGs described in Definition <ref> play a key role in solving Problem 1 based on our proposed technique. In particular, recall that for each λ_j∈Ω_U(𝐀), the LFRE algorithm described in Section <ref> requires a regular node i ∈𝒱∖𝒮_j to accept estimates from only its neighbor set 𝒩^(j)_i in the MEDAG 𝒢_j for estimating 𝐳^(j)[k]. With these points in mind, our immediate goal in this section will be to develop a distributed algorithm, namely Algorithm 1, that constructs a MEDAG 𝒢_j for each λ_j ∈Ω_U(𝐀), and in the process enables each regular node i to determine the set 𝒩^(j)_i for each λ_j ∈𝒪_i. The construction of these MEDAGs constitutes the initialization phase of our design, which can then be followed up by the LFRE algorithm described earlier. We briefly describe the implementation of Algorithm 1 as follows.

Algorithm 1 requires each node i to maintain a counter c_i(j) and a list of indices 𝒩^(j)_i for each λ_j ∈Ω_U(𝐀). The nodes in 𝒩^(j)_i ⊆𝒩_i will be the parents of node i in the DAG constructed for the estimation of 𝐳^(j)[k]. Algorithm 1 is initialized with c_i(j)=0 and 𝒩^(j)_i = ∅, for each i∈𝒱. Subsequently, the algorithm proceeds in rounds where in the first round each node in 𝒮_j broadcasts the message “1" to its out-neighbors, sets c_i(j)=1, maintains 𝒩^(j)_i = ∅ for all future rounds, and goes to sleep. Each node i ∈𝒱∖𝒮_j waits until it has received “1" from at least (2f+1) distinct neighbors, at which point it sets c_i(j)=1, appends the labels of each of the neighbors from which it received “1" to 𝒩^(j)_i, broadcasts the message “1" to its out-neighbors, and goes to sleep. Let ℛ'⊆𝒱 denote the set of nodes that behave regularly during the execution of Algorithm 1. We say that the MEDAG construction algorithm “terminates for λ_j" if there exists T_j ∈ℕ_+ such that c_i(j) =1 ∀ i ∈ℛ',  for all rounds following round T_j. The objective of the algorithm is to return a set of sets {𝒩^(j)_i}, where λ_j ∈Ω_U(𝐀), and i ∈𝒱.


 
We emphasize that in addition to misbehavior during the state estimation phase (run-time), an adversarial node is allowed to misbehave during the implementation of Algorithm 1 (design-time) as well. For example, it can transmit the message out of turn, i.e., before receiving “1" from at least (2f+1) neighbors. It can also choose not to transmit the message at all. Note however that we must have 𝒱∖ℛ' ⊆𝒜, i.e., the f-local set of adversaries during the estimation phase must contain the set of adversaries during the design phase. In the next section, we shall detail graph conditions that guarantee the termination of the MEDAG construction algorithm under arbitrary adversarial behavior. For the following discussion, we characterize the properties of the output of Algorithm 1 if it terminates. To this end, consider the spanning subgraph 𝒢_j=(𝒱,ℰ_j)  induced by the sets {𝒩^(j)_i} returned by Algorithm 1. Keeping in mind that ℛ'⊇ℛ represents the set of nodes that behave regularly during the execution of Algorithm 1, we have the following results; proofs of these results can be found in <cit.>.

Suppose Algorithm 1 terminates for some λ_j ∈Ω_U(𝐀), and returns the sets {𝒩^(j)_i}. Then, the spanning subgraph 𝒢_j induced by these sets contains no directed cycles where every node belongs to ℛ'.



Let ℒ^(j)_m-1 denote the set of all nodes in ℛ' that update their counter value from 0 to 1 in round m of Algorithm 1, i.e., ℒ^(j)_0 = 𝒮_j ∩ℛ', and so on.[Note that the method developed in this paper allows even some of the source nodes in 𝒮_j to be adversarial.]

Suppose Algorithm 1 terminates for some λ_j ∈Ω_U(𝐀). Let T_j denote the smallest integer such that in round T_j, c_i(j)=1 ∀ i ∈ℛ'. Then, the sets {ℒ^(j)_0, ⋯, ℒ^(j)_T_j} form a partition of the set ℛ' in 𝒢_j. 



Suppose the MEDAG construction algorithm terminates for λ_j ∈Ω_U(𝐀). Then, there exists a subgraph 𝒢_j satisfying the properties of a MEDAG for all f-local sets 𝒜 that contain 𝒱∖ℛ' as a subset.





The result follows immediately from Propositions <ref> and <ref>. 

Based on the above theorem, we make the following observations. If Algorithm 1 terminates for each λ_j ∈Ω_U(𝐀), and 𝒱∖ℛ'=∅, then the 𝒢_j subgraphs satisfy all the properties of a MEDAG and we can directly invoke Theorem <ref>. If Algorithm 1 terminates for each λ_j ∈Ω_U(𝐀) and 𝒱∖ℛ'≠∅, (i.e., there is some adversarial activity during the MEDAG construction phase), then we do not need to provide any guarantees of state estimation for the set of misbehaving nodes 𝒱∖ℛ', since 𝒱∖ℛ' ⊆𝒜. In this case too, the subgraphs returned by Algorithm 1 have enough redundancy to ensure that Problem 1 can be solved based on our proposed approach; this fact can be established using arguments identical to those used for proving Theorem <ref>. In what follows, we summarize our overall approach.




 §.§ Summary of the Resilient Distributed State Estimation Scheme




  1) Each regular node i∈ℛ performs the coordinate transformation 𝐳[k]= 𝐓^-1𝐱[k] described in Section <ref>; accordingly, it identifies its detectable and undetectable eigenvalues (𝒪_i and 𝒪_i respectively). 

  2) The MEDAG construction algorithm described by Algorithm 1 is implemented for each λ_j∈Ω_U(𝐀); graph conditions for termination of this algorithm are provided in the next section. At the end of this algorithm, each regular node i knows the subset 𝒩^(j)_i of neighbors it should use in the LFRE algorithm.

  3) Each regular node i employs a locally constructed Luenberger observer (refer to Lemma <ref> and the discussion preceding it) for estimating 𝐳_𝒪_i[k], namely the portion of the state 𝐳[k] corresponding to its detectable eigenvalues.

  4) Each regular node i employs the LFRE algorithm governed by equations (<ref>) and (<ref>) for estimating 𝐳_𝒪_i[k], namely the portion of the state 𝐳[k] corresponding to its undetectable eigenvalues.



Whereas steps 1 and 2 correspond to the initial design phase of our scheme, steps 3 and 4 constitute the estimation phase. A key benefit of the proposed method is that if certain graph-theoretic conditions (to be discussed in the following section) are met, then our overall scheme provably admits a fully distributed implementation even under worst-case adversarial behavior.




§ FEASIBLE GRAPH TOPOLOGIES


In this section, we characterize  feasible graph topologies that guarantee the termination of the MEDAG construction algorithm described in the previous section. In other words, based on Remark <ref>, feasible graph topologies guarantee that Problem 1 can be solved based on our proposed approach (summarized in Section <ref>). We first recall the following definition from <cit.>.
(r-reachable set) For a graph 𝒢=(𝒱,ℰ), a set 𝒮⊂𝒱, and an integer r ∈ℕ_+, 𝒮 is an r-reachable set if there exists an i ∈𝒮 such that |𝒩_i ∖𝒮| ≥ r, 


Thus, if a set 𝒮 is r-reachable, then it contains a node which has at least r neighbors outside 𝒮. We modify the notion of a strongly-r robust graph from <cit.> as follows.

(strongly r-robust graph w.r.t. 𝒮_j) For r ∈ℕ_+ and λ_j ∈Ω_U(𝐀), a graph 𝒢=(𝒱,ℰ) is strongly r-robust w.r.t. to the set of source nodes 𝒮_j, if for any non-empty subset 𝒞⊆𝒱∖𝒮_j, 𝒞 is r-reachable.



For an illustration of the above definitions, the reader is referred back to Figure  <ref>. Figure <ref>(a) is an example of a network that is strongly 3-robust w.r.t. the set of source nodes, namely nodes {1,2,3}. Specifically, all subsets of {4,5,6,7} are 3-reachable (i.e., each such subset has a node that has at least 3 neighbors outside that subset).

 

The MEDAG construction algorithm terminates for λ_j ∈Ω_U(𝐀) if 𝒢 is strongly (3f+1)-robust w.r.t. 𝒮_j.




We prove by contradiction. Consider any λ_j ∈Ω_U(𝐀) and let 𝒢 be strongly (3f+1)-robust w.r.t. the set of source nodes 𝒮_j. Suppose that the MEDAG construction algorithm for λ_j does not terminate. Since the possibility of the counter c_i(j) oscillating between 0 and 1 (where i ∈ℛ) is ruled out based on our MEDAG construction algorithm, there must then exist a non-empty set 𝒞⊆𝒱∖𝒮_j of regular nodes that never update their counter c_i(j) from 0 to 1, where i∈𝒞. As 𝒢 is strongly (3f+1)-robust w.r.t. 𝒮_j, it follows that 𝒞 is (3f+1)-reachable, i.e., there exists a node i ∈𝒞 which has at least (3f+1)  neighbors outside 𝒞. Under the f-local adversarial model, at least (2f+1) of them are regular nodes with c_i(j) = 1. Thus, at least (2f+1) regular nodes must have transmitted the message “1" to node i. Thus, based on the rules of Algorithm 1, node i must have updated c_i(j) from 0 to 1 at some point of time, leading to a contradiction.



Whereas the (2f+1) term appears in various contexts when dealing with security problems on networks (such as distributed consensus <cit.>, broadcasting <cit.> and optimization <cit.>), the (3f+1) term featuring in our analysis accounts for misbehavior that involves transmission of no messages by the adversarial nodes during execution of the MEDAG construction algorithm described in Section <ref>.
We now present the main result of this paper which ties together the previous results presented in this paper, and in turn provides a connection between feasible graph topologies and the solution to Problem 1 based on our proposed approach.


 Consider an LTI system (<ref>) and a measurement model (<ref>). Let the communication graph 𝒢 be strongly (3f+1)-robust w.r.t. 𝒮_j, ∀λ_j∈Ω_U(𝐀). Then, the proposed algorithm summarized in Section <ref> provides a solution to Problem 1.




From Lemma <ref>, it follows that if 𝒢 is strongly (3f+1)-robust w.r.t. 𝒮_j for every λ_j ∈Ω_U(𝐀), then the MEDAG construction algorithm terminates for each such eigenvalue. Combining Theorem <ref>, Remark <ref> and Theorem <ref> then leads to the desired result.

If the adversarial attacks are restricted to the estimation phase only, i.e., if there are no attacks during the initial MEDAG construction phase, then the following result provides a tight graph condition for our algorithm.

 Consider an LTI system (<ref>) and a measurement model (<ref>). Suppose adversarial behavior is restricted to the estimation phase (steps 3 and 4) of the proposed algorithm summarized in Section <ref>. Then, this algorithm solves Problem 1  if and only if 𝒢 is strongly (2f+1)-robust w.r.t. 𝒮_j, ∀λ_j ∈Ω_U(𝐀).



The proof of the above result is given in Appendix <ref>. Essentially, Theorem <ref> alludes to the fact that 𝒢 contains a MEDAG 𝒢_j for each λ_j ∈Ω_U(𝐀) if and only if 𝒢 is strongly (2f+1)-robust w.r.t. 𝒮_j, ∀λ_j ∈Ω_U(𝐀). Note that although Theorem <ref> provides a graph condition that is necessary and sufficient for the algorithm developed in this paper, such a condition may not be necessary for solving Problem 1 in general.

Theorems <ref> and <ref> reveal that `strong r-robustness w.r.t. 𝒮_j, ∀λ_j∈Ω_U(𝐀)' is the key topological property required for guaranteeing success of our proposed algorithm. Accordingly, given a system model (<ref>) and measurement model (<ref>), a network that is strongly r-robust w.r.t. 𝒮_j,  ∀λ_j∈Ω_U(𝐀), will be called an `r-feasible network' for simplicity. We summarize certain features of an r-feasible network in the following result.

 An r-feasible network 𝒢 has the following properties.


  (i) The graph 𝒢^'=(𝒱∪v_new,ℰ∪ℰ_new), where v_new is a new vertex added to 𝒢 and ℰ_new is the edge set associated with v_new, is an r-feasible network if |𝒩_v_new| ≥ r.

  (ii) r ≤min_λ_j ∈Ω_U(𝐀)|𝒮_j|.

  (iii) Let 𝒮=⋂_λ_j ∈Ω_U(𝐀)𝒮_j. Then |𝒩_i| ≥ r,  ∀ i ∈𝒱∖𝒮.

  (iv) Removal of a k-local set from 𝒢, where 0 < k < r, results in a network 𝒢^' that is (r-k)-feasible.



 (i) Consider any λ_j ∈Ω_U(𝐀). If v_new is a source node for λ_j, then it is easily seen that 𝒢^' is strongly r-robust w.r.t. 𝒮_j. For the case when v_new is not a source node for λ_j, consider any non-empty set 𝒞⊆{𝒱∪v_new}∖𝒮_j. If 𝒞={v_new}, then r-reachability of 𝒞 follows from the fact that |𝒩_v_new| ≥ r. In every other case, 𝒞 contains some nodes of the original graph 𝒢 and is hence r-reachable as 𝒢 is r-feasible. Thus 𝒢^' is strongly r-robust w.r.t. 𝒮_j. A similar analysis holds for each λ_j ∈Ω_U(𝐀), leading to the desired result.

(ii) Suppose r > |𝒮_ρ|  where ρ=min_λ_j ∈Ω_U(𝐀)|𝒮_j|. Since the set 𝒞=𝒱∖𝒮_ρ can be at most |𝒮_ρ|-reachable and |𝒮_ρ| < r, it follows that 𝒢 is not r-feasible.

(iii) Suppose i ∈𝒱∖𝒮 with |𝒩_i| < r. As i ∈𝒱∖𝒮, there exists some λ_j ∈Ω_U(𝐀) such that i∈𝒱∖𝒮_j. Consider the set 𝒞={i}. As |𝒩_i| < r, the set 𝒞 is not r-reachable. Thus, 𝒢 is not strongly r-robust w.r.t. 𝒮_j, implying that 𝒢 is not r-feasible.

(iv) First, observe that as 𝒢 is r-feasible and k < r, removal of a k-local set from 𝒢 cannot cause the removal of an entire source node net 𝒮_j for any λ_j∈Ω_U(𝐀). This follows from noting that any source set 𝒮_j where λ_j ∈Ω_U(𝐀) (or any set containing 𝒮_j) will have an overlap of at least r nodes with the neighborhood of some non-source node owing to the r-feasibility of the original network. As r>k, such sets are not k-local. Next, pick any λ_j∈Ω_U(𝐀) and let 𝒞 be a non-empty subset of 𝒱^'∖𝒮_j^', where 𝒱^' and 𝒮_j^' represent the vertex set and source node set for λ_j, respectively, in 𝒢^'. Since 𝒞 was r-reachable in 𝒢, it contained some node v with r neighbors outside 𝒞. While constructing 𝒢^', node v can lose at most k of such neighbors, and hence 𝒞 is (r-k)-reachable in 𝒢^'. The rest of the proof follows trivially.

We remark on certain implications of the above result. The first property provides a procedure for constructing r-feasible networks with N nodes (where N > r) starting from r-feasible networks with fewer than N nodes. The second property shows that the measurement structure of the nodes provides an upper bound on the robustness of the overall network. The third property places a lower bound on the minimum in-degree of any node that cannot estimate the entire state on its own in an r-feasible network. Finally, a direct implication of the fourth property is that a loss of k source nodes (where k < r) for any unstable eigenvalue of the system (possibly due to sensor failures) leaves the resulting network at least (r-k)-feasible if the original network is r-feasible to begin with.
Applicability of the Proposed Approach:
Building on the insights developed in this section, we make a case for the applicability of the approach developed in this paper by addressing the following question: How efficiently can one verify whether a given system and  network is r-feasible? To answer the above question we will exploit a connection between the `strong r-robustness property w.r.t. a certain set of nodes' and the dynamic process of `bootstrap percolation' on networks <cit.>. Given a graph 𝒢 and a threshold r ≥ 2, bootstrap percolation can be viewed as a process of spread of activation where one starts off with a set ℐ⊆𝒱 of initially active nodes. Subsequently, the process evolves over the network based on the rule that an inactive node becomes active if and only if it has at least r active neighbors, with active nodes remaining active forever. The process terminates when no more nodes become active; an initial set ℐ is said to percolate if upon termination the final active set equals the entire node set 𝒱. Consider the following simple, yet key observation.

 Given a graph 𝒢 and a threshold r ≥ 2, an initial set ℐ percolates via the process of bootstrap percolation if and only if 𝒢 is strongly r-robust w.r.t. ℐ.

 
The proof of the above result follows similar arguments as Lemma <ref>, and is hence omitted. Leveraging Lemma <ref>, we obtain the following result.

Given a system matrix 𝐀∈ℝ^n × n (<ref>), a measurement model (<ref>), a communication graph 𝒢=(𝒱,ℰ) with |𝒱|=N, the source set 𝒮_j for each λ_j∈ sp(𝐀), and an integer r≥ 2, one can verify whether the network is r-feasible in O(nN|ℰ|) time.




Notice that |Ω_U(𝐀)| ≤ n, i.e., there are at most n source sets 𝒮_j for which we need to verify the strong r-robustness property in Definition <ref>. Based on Lemma <ref>, for each 𝒮_j corresponding to some λ_j ∈Ω_U(𝐀), verifying whether 𝒢 is strongly r-robust w.r.t. 𝒮_j is equivalent to verifying whether 𝒮_j percolates via the process of bootstrap percolation with threshold r. Thus, we analyze the complexity of simulating a bootstrap percolation process on a given network.[ Algorithm 1 essentially simulates the evolution of a bootstrap percolation process with threshold r=(2f+1), provided there is no adversarial activity during the distributed implementation of such an algorithm.] First, notice that it takes at most N iterations/rounds for a bootstrap percolation process to terminate on a network of N nodes. In each round, every inactive node checks whether it has at least r active neighbors; the entire process of checking is thus completed in O(∑^N_i=1d_i) = O(|ℰ|) time, where d_i represents the in-degree of node i. Thus, for a given initial set, it takes O(N|ℰ|) time to simulate the bootstrap percolation process. The result then follows readily.
 Based on the above result, one can check whether the approach developed in this paper is applicable for a given system and network in polynomial time.[This result is in stark contrast with analogous results existing in the resilient distributed consensus <cit.> and optimization <cit.> literature, since checking the `robustness' condition needed for solving such problems is coNP-complete.]Interestingly, leveraging the equivalence described in Lemma <ref>, it is possible to show that the strong r-robustness property described in Definition <ref> is exhibited by various large-scale complex network models such as 
 the Barabási-Albert (BA) preferential attachment model, the Erdős-Rényi random graph model, and the 2-dimensional random geometric graph model. A detailed discussion on this topic can be found in Appendix <ref>.



§ SIMULATIONS





Consider the system and network given by Figure <ref>. The state evolves as x[k+1]=ax[k], with a=2. Nodes 1, 2 and 3 are the source nodes and directly estimate the state, i.e., y_i[k]=x[k], ∀ i∈{1,2,3}. The rest of the nodes have zero measurements. Node 1 is the only adversarial node in the network, and it simply transmits a constant signal of magnitude ϵ=0.001 to each of its neighbors at every time-step. Each regular source node updates its state estimate based on a standard Luenberger observer as follows:

    x̂_i[k+1]=ax̂_i[k]+l_i(y_i[k]-x̂_i[k]), i∈{2,3},

with the observer gain l_i set to 1.5 (this gain is simply chosen to ensure stability). We first consider a scenario where each non-source node updates its estimate as follows: x̂_i[k+1]=a∑_l∈𝒩^(j)_iw^(j)_ilx̂_l[k], where the weights form a convex combination, and 𝒩^(j)_i represents the neighbors of node i in the MEDAG shown in Figure <ref>(b).[For this scalar system, there is only one mode, i.e., j=1.] If node 1 were to update its estimate as per (<ref>), then it can be easily verified analytically that all nodes would be able to track the state asymptotically (see <cit.> for details). However, as seen from Figure <ref>(a), a single adversarial node (node 1 in this case) transmitting a small constant signal can cause the estimates of all the non-source nodes to diverge. This example demonstrates that although the underlying network is strongly 3-robust (i.e., has enough built-in redundancy to deal with a single adversarial node[For this example, we assume that node 1 misbehaves only during the estimation phase. Hence, Theorem <ref> is applicable.]), the non-resilient distributed observer employed above proves to be inadequate in the face of attacks. However, as seen from Figure <ref>(b), the LFRE algorithm  complements the robust network structure and succeeds in counteracting the adversarial attack. For all simulations, x[0]=0.5, and x̂_i[0], i∈𝒱 is a random number between 0 and 1.


§ CONCLUSIONS



We studied the problem of collaboratively estimating the state of an LTI system subject to worst-case adversarial behavior. For the attack models under consideration, we identified certain necessary conditions that need to be satisfied by any system and network for the problem posed in this paper to have a feasible solution. We then developed a local-filtering algorithm to enable each non-compromised node to recover the entire state. Finally, using a topological property called strong r-robustness, we characterized networks that guarantee success of our proposed strategy. Two notable features of our approach are as follows: (i) each step of our approach admits an attack-resilient, completely distributed implementation provided certain graph-theoretic conditions are met; and (ii) these graph-theoretic conditions can be checked in polynomial time as discussed in the previous section.

There are various interesting directions for future research, some of which were pointed out in Remark <ref>. Finding an algorithm-independent necessary and sufficient condition for the problem posed in this paper will likely be a challenging proposition. Whereas the focus of this paper has been on obtaining sufficient graph-theoretic conditions that account for worst-case adversarial behavior, it might be of interest to see if such conditions can be relaxed when confronted with less sophisticated adversarial attacks. Extensions of our framework to account for network-induced issues such as packet-drops, delays and asynchronicity also merit attention; see <cit.> for preliminary results on this topic.
unsrt
 


§ PROOF OF THEOREM <REF>



“(i)⟹(ii)" We prove by contraposition. Suppose statement (ii) is violated for some node i ∈𝒱, i.e., there exists a set 𝒟_i such that its removal from 𝒢 causes the pair (𝐀,𝐂_i∪𝒫_i) to become undetectable (where 𝒟_i and 𝒫_i have the same meaning as in the statement of Theorem <ref>). It then follows that ℱ=𝒱∖{i∪𝒫_i} is a critical set. Suppose it is also a minimal critical set. We construct 𝒢^' by adding directed edges from a virtual node s to each node in ℱ.[Throughout this proof, we drop the subscript on 𝒢^', ℱ and s, unlike the notation in Section <ref>. This is done since the subscript i is used to denote sets defined w.r.t. a node i in this proof.] Observe that ℋ=𝒟_i  satisfies all the properties of an f-total pair cut w.r.t. s. In particular, 𝒴={i∪𝒫_i} and 𝒳={𝒱∖{𝒟_i∪𝒴}}∪{s}. Thus, statement (i) is violated. A similar argument holds when ℱ contains a minimal critical set.

“(i)⟸(ii)" We again prove by contraposition. Suppose statement (i) is violated, i.e., there exists an f-total pair cut ℋ w.r.t. a virtual node s corresponding to some minimal critical set ℱ. Consider a node i in 𝒴 (recall that 𝒴 is non-empty based on Definition <ref>). First consider the case when node i is not reachable from any node in ℋ in the graph 𝒢. It then follows that in the graph 𝒢, directed paths to node i can only exist from the set 𝒴. But since i∈𝒴 and (𝐀,𝐂_𝒴) is not detectable, it is trivially impossible for node i to estimate the state. We thus focus on the case where node i is reachable from a certain set of nodes, say 𝒟_i, within the set ℋ. Since |ℋ|≤ 2f and 𝒟_i⊆ℋ, we have that |𝒟_i|≤ 2f. It can be easily argued that the removal of 𝒟_i from 𝒢 results in an induced subgraph where node i can only be reached from the set 𝒴. In other words, the set 𝒫_i, as defined in the statement of Theorem <ref>, is a subset of 𝒴. As (𝐀,𝐂_𝒴) is not detectable, it follows that (𝐀,𝐂_i∪𝒫_i) is not detectable either, and thus statement (ii) is violated. 




§ PROOF OF THEOREM <REF>


 Let 𝒜 be the (unknown) set of f-local adversaries, and consider ℛ=𝒱∖𝒜. Given a node i∈ℛ, the state vector 𝐳[k] can be partitioned into the components 𝐳_𝒪_i[k] and 𝐳_𝒪_i[k] that correspond to the detectable and undetectable eigenvalues, respectively, of node i. Based on Lemma <ref>, we know that node i can estimate 𝐳_𝒪_i[k] asymptotically via a locally constructed Luenberger observer. It remains to show that node i can recover 𝐳_𝒪_i[k], or in other words, for each λ_j ∈𝒪_i, we need to prove that lim_k→∞||𝐳̂^(j)_i[k]-𝐳^(j)[k]||=0. To this end, consider a non-real eigenvalue λ_j ∈Ω_U(𝐀). As 𝒢 contains a MEDAG for each λ_j ∈Ω_U(𝐀), the sets {ℒ^(j)_0, ℒ^(j)_1, ⋯, ℒ^(j)_q, ⋯ℒ^(j)_T_j} form a partition of the set ℛ. We prove that each node in ℛ can asymptotically estimate 𝐳^(j)[k] by inducting on the level number q.

For q=0, by definition of the set ℒ^(j)_0, all nodes in ℒ^(j)_0 are regular and belong to the set 𝒮_j, i.e., λ_j ∈𝒪_i for each node i in ℒ^(j)_0. Thus, by  Lemma <ref>, each node in level 0 can estimate 𝐳^(j)[k] asymptotically. Notice that for any node i belonging to a level q, where 1 ≤  q ≤ T_j, we have λ_j ∈𝒪_i. Consider a node i in ℒ^(j)_1 and let its error in estimation of the component z^(jm)[k] be denoted by e^(jm)_i[k] ≜ẑ^(jm)_i[k]-z^(jm)[k]. The estimation errors of the individual components are aggregated in the vector 𝐞^(j)_i[k]= ẑ^(j)_i[k]-𝐳^(j)[k]. Subtracting 𝐳^(j)[k+1] from both sides of equation (<ref>), noting that 𝐳^(j)[k+1]=𝐖(λ_j)𝐳^(j)[k] (based on the dynamics given by (<ref>)), and using (<ref>), we obtain

    0.8!𝐞^(j)_i[k+1]=𝐖(λ_j)[       ∑_l ∈ℳ^(j1)_i[k]w^(j1)_il[k]e^(j1)_l[k];                                             ⋮; ∑_l ∈ℳ^(jσ_j)_i[k]w^(jσ_j)_il[k]e^(jσ_j)_l[k] ]_𝐞̅^(j)_i[k],

where σ_j=2a_𝐀(λ_j) (since λ_j is non-real). For arriving at (<ref>), we used the fact that ∑_l ∈ℳ^(jm)_i[k]w^(jm)_il[k]=1 for every component m of 𝐳^(j)[k]. We now analyze the error dynamics (<ref>). To this end, for each component m of the vector 𝐳^(j)[k], we partition the set 𝒩^(j)_i into the sets 𝒰^(jm)_i[k], 𝒥^(jm)_i[k], and ℳ^(jm)_i[k], such that the sets 𝒰^(jm)_i[k] and 𝒥^(jm)_i[k] contain f nodes each, with the highest and lowest estimate values for z^(jm)[k] respectively, transmitted to node i at time-step k, and ℳ^(jm)_i[k] contains the rest of the nodes in 𝒩^(j)_i. According to the update rule (<ref>), node i only uses estimates from the set ℳ^(jm)_i[k] (which is non-empty at all time-steps based on the properties of a MEDAG) to compute the quantity z̅^(jm)_i[k]. Now, for any component m of 𝐳^(j)[k], consider the following two cases.
(i) ℳ^(jm)_i[k] ∩𝒜 = ∅, i.e., there are no adversarial nodes in the set ℳ^(jm)_i[k]: in this case, all the nodes in the set ℳ^(jm)_i[k] are regular and belong to ℒ^(j)_0 (as 𝒩^(j)_i ∩ℛ⊆ℒ^(j)_0). (ii) ℳ^(jm)_i[k] ∩𝒜 is non-empty, i.e., there are some adversarial nodes in the set ℳ^(jm)_i[k]: based on the f-local adversarial model, it is apparent that each of the sets 𝒰^(jm)_i[k] and 𝒥^(jm)_i[k] contain at least one regular node belonging to ℒ^(j)_0. Let u and v be two such regular nodes belonging to 𝒰^(jm)_i[k] and 𝒥^(jm)_i[k], respectively. Based on the definitions of the sets 𝒰^(jm)_i[k], 𝒥^(jm)_i[k], and ℳ^(jm)_i[k], we have ẑ^(jm)_v[k] ≤ẑ^(jm)_l[k] ≤ẑ^(jm)_u[k], and hence e^(jm)_v[k] ≤ e^(jm)_l[k] ≤ e^(jm)_u[k],  for every node l ∈ℳ^(jm)_i[k]. In particular, since u,v ∈ℒ^(j)_0, it follows that for any node l ∈ℳ^(jm)_i[k], e^(jm)_min[k] ≤ e^(jm)_l[k] ≤ e^(jm)_max[k], where e^(jm)_min[k]= min_u∈ℒ^(j)_0 e^(jm)_u[k] and   e^(jm)_max[k]= max_u∈ℒ^(j)_0 e^(jm)_u[k]. This property holds for every component m of 𝐳^(j)[k]. Analyzing each of the two cases, we infer that at every time-step k, each component of the vector 𝐞̅^(j)_i[k] in (<ref>) lies in the convex hull of the corresponding components of the error vectors 𝐞^(j)_u[k], u ∈ℒ^(j)_0 = 𝒮_j ∩ℛ. Based on Lemma <ref>, we have that lim_k→∞𝐞^(j)_u[k] = 0, ∀ u ∈𝒮_j ∩ℛ, and hence it follows that 𝐳̂^(j)_i[k] converges asymptotically to 𝐳^(j)[k] for every regular node i in  ℒ^(j)_1. 

Suppose the result holds for all levels from 0 to q (where 1 ≤ q ≤ T_j-1). It is easy to see that the result holds for all regular nodes in ℒ^(j)_q+1 as well, by noting the following. (i) A regular node i ∈ℒ^(j)_q+1 has 𝒩^(j)_i ∩ℛ⊆⋃^q_r=0ℒ^(j)_r. (ii) For each i∈ℒ^(j)_q+1, a similar analysis reveals that at every every time-step k, each component of the vector 𝐞̅^(j)_i[k] lies in the convex hull of the corresponding components of the error vectors 𝐞^(j)_u[k], u ∈⋃^q_r=0ℒ^(j)_r. The desired result then follows from the induction hypothesis. An identical argument can be sketched for a real eigenvalue λ_j ∈Ω_U(𝐀), and thus the result holds for any λ_j ∈Ω_U(𝐀). We arrive at the conclusion that every node i ∈ℛ can asymptotically estimate 𝐳^(j)[k] for every eigenvalue λ_j ∈𝒪_i. Thus, each node i ∈ℛ can asymptotically estimate 𝐳[k], and hence 𝐱[k]=𝐓𝐳[k]. 



§ PROOF OF THEOREM <REF>



For sufficiency, it is easily noted that the conditions stated in the theorem guarantee termination of the MEDAG construction algorithm for every λ_j∈Ω_U(𝐀). The rest of the proof for sufficiency follows identical arguments as the proof of Theorem <ref>.

For proving necessity, we first note that the proposed algorithm summarized in Section <ref> is applicable only if the MEDAG construction algorithm (Algorithm 1) terminates for each λ_j∈Ω_U(𝐀) and returns a subgraph 𝒢_j satisfying the properties of a MEDAG for all f-local sets containing 𝒱∖ℛ'. Here ℛ' denotes the set of nodes that behave regularly during the execution of Algorithm 1. Based on the hypothesis of the theorem, since ℛ'=𝒱, the existence of a MEDAG 𝒢_j ∀λ_j∈Ω_U(𝐀) is necessary in this case for running the LFRE algorithm. The rest of the proof proceeds via contradiction. Suppose 𝒢 is not strongly (2f+1)-robust w.r.t. 𝒮_j for some λ_j ∈Ω_U(𝐀) and yet there exists a MEDAG 𝒢_j for λ_j. Since 𝒢 is not strongly (2f+1)-robust w.r.t. λ_j, there exists a non-empty set 𝒞⊆𝒱∖𝒮_j that is not (2f+1)-reachable. Consider the trivial f-local set 𝒜=∅. The subgraph 𝒢_j must contain a partition of ℛ=𝒱∖𝒜=𝒱 into levels that satisfy the second property of a MEDAG in Definition <ref>. With this point in mind, let 𝒞 be partitioned as 𝒞=⋃_r=1^qℱ_r, where ℱ_r=𝒞∩ℒ^(j)_n_r for some set of integers {n_1, ⋯, n_q| 1 ≤ n_i ≤ T_j  ∀ i∈{1,⋯,q}}. Here, {ℒ^(j)_n_r}^q_r=1 represents a subset of the levels that partition ℛ in the MEDAG 𝒢_j (that exists based on the hypothesis). Without loss of generality, let n_1 < n_2 < ⋯ < n_q. Then, from the definition of a MEDAG, it follows that for any i ∈ℱ_n_1, N^(j)_i contains elements from only 𝒱∖𝒞. As 𝒞 is not (2f+1)-reachable, |𝒩^(j)_i| < (2f+1), thereby violating the first property of a MEDAG in Definition <ref>. We thus arrive at a contradiction, and the proof is complete.



§ THE STRONG R-ROBUSTNESS PROPERTY OF RANDOM GRAPHS


The focus of this section is to address the following question. Given a dynamical system and an associated large-scale complex sensor network monitoring the system, under what conditions is the system and network pair r-feasible?  To provide an answer to this question, we study the `strong r-robustness' property in three relatively common random graph models for large-scale complex networks, namely the Barabási-Albert (BA) preferential attachment model, the Erdős-Rényi random graph model, and the 2-dimensional random geometric graph model.

Consider a scenario where we are given a dynamical system and an associated wireless sensor network such that the system and network pair is r-feasible, and hence, resilient to adversarial attacks. We wish to expand the network via addition of more sensors without disrupting the r-feasibility property, i.e., we intend to tolerate the same number of adversaries as earlier. As the first property in Proposition <ref> suggests, this can be achieved by continually adding new nodes with incoming edges from at least r nodes in the existing network. The specific construction where the neighbors of a new node are selected with a probability proportional to the number of edges they already have leads to the BA preferential attachment model. Such a model is thought of as a plausible mechanism for the formation of many real-world complex networks <cit.>. Based on our foregoing discussion, it then follows that such real-world networks would facilitate the LFRE dynamics introduced in Section <ref>, and would hence be resilient to the worst-case attack model considered in this paper.

Next, we turn our attention to one of the most common mathematical models for large-scale networks, namely Erdős-Rényi random graphs<cit.>. We denote an Erdős-Rényi random graph on N nodes by 𝒢_N,p, where all possible edges between pairs of different nodes are present independently and with the same probability p. We further note that p is in general a function of the network size N. From the perspective of a network designer, we will be interested in answering the following questions. (i) How should the size of the source sets 𝒮_j (for each λ_j ∈Ω_U(𝐀)) scale with the size of the network to maintain r-feasibility in an Erdős-Rényi random graph?  (ii) Which nodes should be chosen as the source nodes? Prior to answering these questions, we briefly remark on the notation to be used for the remainder of this section. The term w.h.p. (with high probability) will be used for events with probability tending to 1 as N →∞. Given two non-negative sequences a_N and b_N, the notation a_N≪ b_N will convey the same meaning as a_N=o(b_N). To make use of Lemma <ref>, we first recall a few definitions from <cit.>. Given an integer r ≥ 2, define

    T_c(N,p) ≜((r-1)!/Np^r)^1/(r-1),   A_c(N) ≜(1-1/r)T_c(N,p).


We have the following result for an Erdős-Rényi random graph model. 

 

Given an LTI system (<ref>), a measurement model (<ref>), and a network modeled by an Erdős-Rényi random graph 𝒢_N,p, suppose that for each λ_j ∈Ω_U(𝐀), the source set 𝒮_j(N) is chosen randomly.[By choosing 𝒮_j(N) randomly, we imply that the measurement set needed to detect λ_j is allocated to |𝒮_j(N)| nodes picked uniformly at random. The notation 𝒮_j(N) is used to explicitly point out that the size of the source sets scales with the size of the network.] Then, the following are true.


  (i) Let p=p(N) be such that N^-1≪ p ≪ N^-1/r. If for each λ_j ∈Ω_U(𝐀), |𝒮_j(N)|/A_c(N)≥ 1+δ, for some δ >0, and |𝒮_j(N)| ≤N/2, then 𝒢_N,p is r-feasible w.h.p. if and only if Np-(ln N+(r-1)ln  lnN) →∞ as N →∞.

  (ii) Let p=p(N) be such that p ≫ N^-1/r. If for each λ_j ∈Ω_U(𝐀), |𝒮_j(N)| ≥ r, then 𝒢_N,p is r-feasible w.h.p. 


 (i) If the conditions in part (i) are met, then for each λ_j ∈Ω_U(𝐀), 𝒮_j percolates via bootstrap percolation with threshold r on 𝒢_N,p w.h.p. based on <cit.>. Lemma <ref> then implies that 𝒢_N,p is strongly r-robust w.r.t. each such source set 𝒮_j w.h.p., i.e., 𝒢_N,p is r-feasible w.h.p. . The proof for part (ii) follows similarly by leveraging <cit.> and Lemma <ref>. 



We glean the following insights from the above result. First, we observe that if either condition (i) or condition (ii) is met, then our proposed algorithm will enable each regular node to asymptotically estimate the state of the system w.h.p. in the presence of any ⌊r-1/3⌋ locally-bounded set of Byzantine adversaries. This is a direct consequence of Theorem <ref>. The first part of Proposition <ref> indicates that although the source sets can be chosen randomly, their size needs to scale appropriately with the size of the network to maintain r-feasibility. The second part states that if the probability of edge formation is large enough, then it suffices to pick source sets of constant size equal to the bare minimum required for achieving r-feasibility (which equals r based on part (ii) of Proposition <ref>).


Among the three random graph models mentioned earlier, the one most relevant to our cause is the two-dimensional random geometric graph (RGG) model <cit.>. RGGs are typically used to model networks where a notion of spatial proximity governs the interaction between the nodes. A wireless sensor network where randomly deployed nodes communicate with nodes only in a geographical vicinity, constitutes an ideal setup for an RGG model <cit.>. We will consider a two-dimensional RGG model generated by first placing N nodes randomly within the unit square [0,1]^2. Undirected edges are placed between two nodes if and only if the Euclidean distance between such nodes is at most d(N), where d(N) is a positive number that may depend on the network size N. We will denote such a RGG by 𝒢_N,d(N).

Like the Erdős-Rényi case, our focus will be on understanding how the source sets should be chosen to ensure r-feasibility of 𝒢_N,d(N) with high probability. To provide such a characterization, we first recall a few functions from <cit.>. Let H(x) ≜ x   lnx-x+1 be defined on [0,∞) and J(x) ≜ lnx-1+x^-1 be defined on (0,∞). Furthermore, let J^-1_R: [0,∞) → [1,∞) denote the inverse of J(x) when the domain of J(x) is [1,∞). We then have the following result. 

 

Given an LTI system (<ref>) and a measurement model (<ref>), let the communication graph be modeled by the RGG 𝒢_N,d(N), where d(N)=√(a  ln N/π N) and a > 1. For each λ_j ∈Ω_U(𝐀), let a  node be chosen as a source node for λ_j with a probability p independently of the other nodes in the network. Let r=γ a   ln N, where γ∈ (0, 1/5π). Suppose a ≥5π/H(5πγ) and 

    p ≥min{γ, 5πγ/J^-1_R(1/aγ)}.

Then, 𝒢_N,d(N) is r-feasible.[A RGG 𝒢_N,d(N) is connected w.h.p. for d(N) > √(ln N/π N). The choice of a > 1 thus allows one to deal with an asymptotically connected 𝒢_N,d(N).]


 For each λ_j ∈Ω_U(𝐀), if the source set 𝒮_j is chosen as described above, then it percolates 𝒢_N,d(N) w.h.p. if the conditions of the proposition are met <cit.>. The result then follows from Lemma <ref>.



In an attack-prone wireless sensor network, one might be interested in tolerating f-local adversarial sets where the paramater f scales with the size of the network. Such a possibility is captured by  Proposition <ref>, based on which, ⌊γ a   ln N-1/3⌋-local Byzantine adversarial sets can be accounted for by our proposed algorithm.

