Secure Distributed State Estimation of an LTI System over Time-Varying Networks and Analog Erasure Channels
Aritra Mitra Shreyas Sundaram
cs.SY

Algebraic Hybridization and Static Condensation with Application to
Scalable H(÷) Preconditioning

  This work was performed under the auspices of the U.S. Department of Energy by
  Lawrence Livermore National Laboratory under Contract DE-AC52-07NA27344, and
  sponsored by the U.S. Department of Energy, Office of Science, Office of
  Advanced Scientific Computing Research, Applied Mathematics
  program. LLNL-JRNL-732140.

    
V. Dobrev
Center for Applied Scientific Computing,
  Lawrence Livermore National Laboratory,
  P.O. Box 808, L-561,
  Livermore, CA 94551, U.S.A (dobrev1@llnl.gov,
  tzanio@llnl.gov, cslee@llnl.gov, tomov2@llnl.gov, panayot@llnl.gov).
T. Kolev
[2]
C. S. Lee
[2]
V. Tomov
[2]
P. S. Vassilevski
[2]

    December 30, 2023
=========================================================================================================================================================================================================================================================================================================================================================================================================================================

empty
empty




 We study the problem of collaboratively estimating the state of an LTI system monitored by a network of sensors, subject to the following important practical considerations: (i) certain sensors might be arbitrarily compromised by an adversary and (ii) the underlying communication graph governing the flow of information across sensors might be time-varying. We first analyze a scenario involving intermittent communication losses that preserve certain information flow patterns over bounded intervals of time. By equipping the sensors with adequate memory, we show that one can obtain a fully distributed, provably correct state estimation algorithm that accounts for arbitrary adversarial behavior, provided certain conditions are met by the network topology. We then argue that our approach can handle bounded communication delays as well. Next, we explore a case where each communication link stochastically drops packets based on an analog erasure channel model. For this setup, we propose state estimate update and information exchange rules, along with conditions on the network topology and packet drop probabilities, that guarantee mean-square stability despite arbitrary adversarial attacks.




§ INTRODUCTION

Consider a scenario where a group of  sensors deployed over a geographical network seek to cooperatively estimate the state of a dynamical process. This general setup constitutes the standard distributed state estimation problem and finds applications in various domains such as power systems, transportation networks, automated factories, and distributed robotics. As envisioned in <cit.>, to fully leverage the benefits of a distributed sensor network as described above, one must design algorithms and networks that can respond to dynamic environments involving unreliable components. In particular, the growing need for designing secure networked control systems necessitates the design of localized algorithms that operate reliably in the face of adversarial sensor attacks. In this context, unavoidable network-induced issues such as communication losses and delays offer additional degrees of freedom for adversaries to devise carefully crafted attacks, thereby significantly compounding the estimation problem.[We discuss how adversaries can use communication losses and delays to their advantage later in the paper.] In light of the above discussion, the design of attack-resilient, provably correct distributed state estimation algorithms that account for various types of communication losses and delays will be the subject of our present investigation. 

Related Work: The classical distributed state estimation problem as described above, has been studied extensively over the past decade; however, single-time-scale algorithms that solve such problems under the most general conditions on the system and network have been proposed only recently in <cit.>. While the problem of detecting and mitigating various forms of data-injection attacks in deterministic <cit.> and stochastic <cit.> centralized[Here, by a centralized system, we refer to a system where the measurements of all the sensors are available at a single location.] systems is now well understood, tackling adversarial behavior in the context of distributed state estimation remains largely unexplored. The limited literature that seeks to address this problem either provides no theoretical guarantees <cit.> or limits the class of admissible attacks <cit.>. In an initial effort to bridge the gap between centralized and distributed secure state estimation, we recently developed a distributed observer that allows each non-compromised sensor to asymptotically recover the entire state dynamics despite arbitrary adversarial sensor attacks, under appropriate conditions on the network topology <cit.>. However, our proposed technique did not account for the challenges introduced by communication drop-outs or delays.  This leads us to the contributions of the present paper.

Contributions: Our contributions are twofold. First, in Section <ref>, we consider a communication loss model where certain information flow patterns are preserved deterministically over bounded intervals of time. For this communication loss model, we show how sensors equipped with memory can process delayed state estimates received from neighbors (some of whom can be potentially adversarial) to asymptotically estimate the state of the system. Our algorithm is inspired by recent work that addresses the resilient consensus problem in asynchronous settings <cit.>, <cit.>. As a byproduct of our analysis, we argue that the proposed  strategy accounts for bounded communication delays as well. We also characterize the convergence rate of our algorithm in terms of the system instability, the upper bound on the delay, and certain properties of the underlying communication graph. The second main result of the paper, presented in Section <ref>, pertains to a network whose communication links are modeled as analog erasure channels that may or may not introduce random delays. We show how a graph metric known as `strong-robustness' (introduced in our prior work <cit.>) can help tolerate higher erasure probabilities, while guaranteeing mean-square stability of the estimation error dynamics. Finally, we emphasize that all our results apply to a sophisticated and worst-case adversarial model (termed Byzantine adversaries) which is typically considered in the literature on resilient distributed algorithms <cit.> .


§ SYSTEM AND ATTACK MODEL

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) ∈ℰ}. The notation |𝒱| is used to denote the cardinality of a set 𝒱. Throughout the rest of this paper, we use the terms `edges' and `communication links/channels' interchangeably. The set of all eigenvalues (modes) of a matrix 𝐀 is denoted by sp(𝐀) = {λ∈ℂ | det(𝐀-λ𝐈) = 0} and the set of all marginally stable and unstable eigenvalues of 𝐀 is denoted by Λ_U(𝐀) = {λ∈ sp(𝐀) |  |λ| ≥ 1 }. We use diag(𝐀_1,⋯,𝐀_2) to refer to a block-diagonal matrix with the matrix 𝐀_i as the i-th block entry. The notation ℤ_≥ 0 is used to denote the set of all non-negative integers, and for a random variable 𝕏, its expected value is denoted by E[𝕏].

System Model: Consider the linear 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 has partial measurement of the state 𝐱[k]:

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

where 𝐲_i[k] ∈ℝ^r_i and 𝐂_i ∈ℝ^r_i × n. We denote 𝐲[k]=[ 𝐲^T_1[k]        ⋯ 𝐲^T_N[k] ]^T, and 𝐂=[ 𝐂^T_1     ⋯ 𝐂^T_N ]^T. 

In the standard distributed state estimation problem, each node is required to  estimate the state 𝐱[k] using its own measurements and the information received from its neighbors, where such information flow is restricted by the underlying communication graph 𝒢. A challenging scenario emerges when one seeks to solve the same problem in the presence of malicious nodes in the network. We now formally describe the adversary model considered throughout the 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 (and any variations to such topology due to communication drop-outs), the system dynamics and the algorithm employed by the non-adversarial nodes. 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. This assumption of omniscient adversarial behavior is standard in the literature on resilient and secure distributed algorithms <cit.>, and allows us to provide guarantees against “worst-case" adversarial behavior. In terms of their density in the network, we assume that there are at most f adversarial nodes in the neighborhood of any non-adversarial node; this property will be referred to as the `f-local' property of the adversarial set. Summarily, the adversary model described thus far will be called an f-local Byzantine adversary model.  The non-adversarial nodes will be referred to as regular nodes and be represented by the set ℛ=𝒱∖𝒜. Finally, note that the number and identities of the adversarial nodes are not known to the regular nodes.

Objective: Given the LTI system (<ref>), the measurement model (<ref>), a communication graph 𝒢, and the f-local Byzantine adversary model described above, our  objective in this paper is to design state estimate update and information exchange rules that guarantee asymptotic convergence (in a deterministic or stochastic sense) of the estimates of the regular nodes to the true state of the plant, under different types of communication loss models. 




§ PRELIMINARIES

Before developing our estimation strategy, we first establish certain terminology, notation, and key ideas in this section. To begin with, the underlying communication graph 𝒢 that dictates the flow of information among nodes in the absence of any communication losses will be referred to as the baseline communication graph. The loss of communication between nodes is modeled by a time-varying graph 𝒢[k]=(𝒱,ℰ[k]), where ℰ[k] ⊆ℰ. Regarding system (<ref>), we make the following assumption for clarity of exposition.[The results presented in this paper can however be extended to system matrices with arbitrary spectrum via a more detailed technical analysis.]

 The system matrix 𝐀 has real, distinct eigenvalues.


Based on the above assumption, one can perform a coordinate transformation 𝐳[k]≜𝐕𝐱[k] on (<ref>), with an appropriate non-singular matrix 𝐕, to obtain[As this only relies on the 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.]

    𝐳[k+1]    = 𝐌𝐳[k] = diag(λ_1, ⋯, λ_n)𝐳[k],
    𝐲_i[k]    = 𝐂̅_i𝐳[k],   ∀ i ∈{1, ⋯, N}

where sp(𝐀)=diag(λ_1, ⋯, λ_n), 𝐌=𝐕𝐀𝐕^-1 and 𝐂̅_i=𝐂_i𝐕^-1. Commensurate with this decomposition, the j-th component  of the state vector 𝐳[k] will be denoted by z^(j)[k], and will be referred to as the component corresponding to the eigenvalue λ_j. Since recovering 𝐳[k] is equivalent to recovering 𝐱[k], we focus on estimating 𝐳[k]. To this end, we will use the following definition 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. 


Let Ω_U(𝐀) ⊆Λ_U(𝐀) contain the set of eigenvalues of 𝐀 for which 𝒱∖𝒮_j is non-empty. Then, for each λ_j ∈Ω_U(𝐀), our strategy requires the source nodes 𝒮_j to maintain local[Here, by `local' we imply that such observers can be constructed and run without any information from neighbors.] Luenberger observers for estimating z^(j)[k], while the non-source nodes rely on a secure consensus protocol for the same. For any node i, let the set of eigenvalues it can detect be denoted by 𝒪_i, and let 𝒰𝒪_i=sp(𝐀)∖𝒪_i. Then, the following result from <cit.> states that node i can estimate the locally detectable portion of 𝐳[k], referred to as 𝐳_𝒪_i[k], without interacting with its neighbors.


Suppose Assumption 1 holds. Then, for each regular node i∈ℛ and each λ_j ∈𝒪_i, a local Luenberger observer can be constructed that ensures that lim_k→∞|ẑ^(j)_i[k]-z^(j)[k]|=0, where ẑ^(j)_i[k] denotes the estimate of z^(j)[k] maintained by node i.



The real challenge is posed by the task of estimating the locally undetectable dynamics, since it necessitates communicating with neighbors, some of whom might be adversarial. In fact, the traditional metric of graph connectivity which plays a pivotal role in the analysis of fault-tolerant and secure distributed algorithms <cit.>, cannot capture the requirements to be met by a sensor network for addressing adversarial behavior in the context of distributed state estimation. A simple illustration of this fact is as follows.

 Consider a scalar unstable plant monitored by a clique of N+2 nodes, as depicted in Figure <ref>. Nodes s_1 and s_2 are the only nodes with non-zero measurements, i.e., they are the source nodes for this system. Although this network is fully connected, the presence of a single adversarial node makes it impossible for any algorithm to guarantee estimation of x[k] at every regular node. This remains true even if every regular node possesses knowledge of the network topology. Specifically, if the adversary compromises one of the two source nodes, then it can behave in a way that makes it impossible for the non-source nodes to distinguish between two different state trajectories of the system, due to the conflicting information from the two source nodes.[We omit details of such an attack strategy due to space constraints. For centralized systems where f sensors are compromised, <cit.> have shown that for recovering the state of the system asymptotically, the system must remain detectable after the removal of any 2f sensors.]


The above example alludes to the need for a certain amount of redundancy in the measurement structure and the network topology. To this end, in <cit.>, we proposed an algorithm that made use of certain directed acyclic subgraphs in addressing the secure distributed estimation problem; properties of such subgraphs are described below.



(Mode Estimation Directed Acyclic Graph (MEDAG)) For each eigenvalue λ_j ∈Ω_U(𝐀), suppose there exists a spanning subgraph 𝒢_j = (𝒱,ℰ_j) of 𝒢 with the following properties. 


  (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)_1, ⋯ , ℒ^(j)_T_j}, where ℒ^(j)_0 = 𝒮_j ∩ℛ, and if i ∈ℒ^(j)_m (where 1 ≤ m ≤ T_j), then 𝒩^(j)_i ∩ℛ⊆⋃^m-1_r=0ℒ^(j)_r.


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



We say a regular node i∈ℒ^(j)_m “belongs to level m", where the levels are indicative of the relative 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, note that for each λ_j ∈Ω_U(𝐀), a MEDAG 𝒢_j contains atleast (2f+1) source nodes that can detect λ_j.] Our estimation scheme (described later) relies on a special information flow pattern that requires a node i to listen to only its neighbors in 𝒩^(j)_i for estimating z^(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 z^(j)[k]. The implications of such properties will become apparent during the analysis of our proposed algorithms.

Before proceeding further, we need to understand the properties of the baseline communication graph 𝒢 that guarantee the existence of a MEDAG 𝒢_j, ∀λ_j ∈Ω_U(𝐀). To this end, we require the following definitions and result from <cit.>.

(r-reachable set) For a graph 𝒢=(𝒱,ℰ), a set 𝒮⊂𝒱,  and an integer r ∈ℤ_>0, 𝒮 is an r-reachable set if there exists an i ∈𝒮 such that |𝒩_i ∖𝒮| ≥ r. 


(strongly r-robust graph w.r.t. 𝒮_j) For r ∈ℤ_>0 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.



 If 𝒢 is strongly (2f+1)-robust w.r.t. 𝒮_j, for some λ_j ∈Ω_U(𝐀), then 𝒢 contains a MEDAG 𝒢_j for λ_j.



Given a λ_j ∈Ω_U(𝐀), there might be more than one subgraph that satisfies the definition of a MEDAG 𝒢_j. In <cit.>, we proposed a distributed algorithm that allowed each node i to identify the sets 𝒩^(j)_i, ∀λ_j ∈𝒰𝒪_i, by explicitly constructing a specific MEDAG 𝒢_j for each λ_j ∈𝒰𝒪_i. In this paper, we assume that these MEDAGs have already been constructed during a distributed design phase using such an algorithm, to inform each node i of the set 𝒩^(j)_i, ∀λ_j ∈𝒰𝒪_i. It will be important to keep in mind that the sets 𝒩^(j)_i are time-invariant as they correspond to specific MEDAGs.



§ SECURE STATE ESTIMATION OVER TIME-VARYING NETWORKS


In this section, we develop an algorithm that enables each regular node to estimate its locally undetectable portion subject to arbitrary adversarial attacks and intermittent communication losses that satisfy the following criterion.

 There exists T ∈ℤ_>0 such that ∀ k ≥ T, ⋃^T_τ=0𝒢[k-τ] contains the MEDAG 𝒢_j for each λ_j ∈Ω_U(𝐀).


Note that under the above communication failure model, 𝒢[k] may not contain the specific MEDAGs constructed during the design phase for some (or all) k, thereby precluding direct use of the technique developed in <cit.>. However, such MEDAGs will be preserved in the union graph over the interval [k-T,k], ∀ k≥ T. For this model, we assume that all estimates being transmitted by regular nodes are properly time-stamped, and propose the following algorithm. 

For each λ_j ∈𝒰𝒪_i, a regular node i updates its estimate of z^(j)[k] in the following manner. 



  * At every time-step k, node i collects the most recent estimate of z^(j)[k] received from each node l ∈𝒩^(j)_i, along with the corresponding time-stamp ϕ_il[k] ∈ℤ_≥ 0. It then evaluates the delay τ_il[k] =k-ϕ_il[k] and computes the quantity z̅^(j)_il[k]  ≜λ_j^τ_il[k]ẑ^(j)_l[k-τ_il[k]].[For notational simplicity, while considering the eigenvalue λ_j, we drop the superscript `j' on the time-stamp ϕ_il[k] and the delay τ_il[k].] Prior to receiving the first estimate from a node l ∈𝒩^(j)_i, the value z̅^(j)_il[k] is maintained at 0 by node i.[If node i receives an estimate without a time-stamp from some node in 𝒩^(j)_i ∩𝒜, it simply assigns a value of 0 to such an estimate (without loss of generality). Note that based on Assumption 2, node i is guaranteed to receive a time-stamped estimate from every regular node l in 𝒩^(j)_i at least once over every interval of the form [k-T,k],  ∀ k ≥ T, i.e., for each l ∈𝒩^(j)_i ∩ℛ, z̅^(j)_il[k] will necessarily be of the form λ_j^τ_il[k]ẑ^(j)_l[k-τ_il[k]], ∀ k≥ T.]


  * The values z̅^(j)_il[k] are sorted from largest to smallest; subsequently, the largest f and the smallest f of such values are discarded (i.e., 2f values are discarded in all) and ẑ^(j)_i[k] is updated as

    0.8!ẑ^(j)_i[k+1]=λ_j(∑_l∈ℳ^(j)_i[k]w^(j)_il[k]z̅^(j)_il[k]),

where ℳ^(j)_i[k] ⊂𝒩^(j)_i represents the set of nodes whose (potentially) delayed estimates are used by node i at time-step k after the removal of the 2f aforementioned values. Node i assigns the consensus weight w^(j)_il[k] to node l at time-step k for estimating the component of the state corresponding to the eigenvalue λ_j. The weights w^(j)_il[k] are non-negative and satisfy ∑_l∈ℳ^(j)_i[k]w^(j)_il[k]=1, ∀λ_j ∈𝒰𝒪_i.


We refer to the above algorithm as the Sliding Window Local-Filtering based Secure Estimation (SW-LFSE) algorithm. We comment on certain features of this algorithm and then proceed to analyze its convergence properties.

 Like the LFSE algorithm in <cit.>, the SW-LFSE algorithm also relies on a two-stage filtering strategy. Specifically, the first stage of filtering corresponds to a regular node i ∈𝒱∖𝒮_j listening to only its neighbors 𝒩^(j)_i ⊆𝒩_i in the MEDAG 𝒢_j.[This operation ensures a uni-directional flow of information from the source nodes 𝒮_j (some of whom might also be adversarial) to the rest of the network.] The second stage of filtering requires node i to discard certain extreme values received from nodes in 𝒩^(j)_i.[Whereas the first stage of filtering is specific to our distributed state estimation approach, the second stage of filtering is similar to the W-MSR algorithm employed in the secure consensus literature <cit.>,<cit.>.] A key point of difference between the algorithms is that in the SW-LFSE approach, at each time-step k, node i needs to store the most recent (potentially) delayed  estimate received from each neighbor in 𝒩^(j)_i. Consequently, we require the regular nodes to possess adequate memory.



Our approach does not require the nodes to have a priori knowledge of the value of T in Assumption 2.


 Our results will continue to hold if in step 2 of the SW-LFSE algorithm, node i simply uses the median value of z̅^(j)_il[k], l ∈𝒩^(j)_i, in the update rule (<ref>). Although this can reduce computation, the present approach offers a degree of freedom in choosing the weights w^(j)_il[k], that can be potentially leveraged to account for issues like noise.


 As alluded to earlier in the introduction, this communication-loss model offers the adversaries the additional opportunity of sending false information regarding the time-stamps of their estimates.[In other words, due to false time-stamp information, the quantity ẑ^(j)_l[k-τ_il[k]] may not represent the true estimate of an adversarial node l at time (k-τ_il[k]). Thus, we resort to a slight abuse of notation here.] Nevertheless, as we establish in the next section, our proposed algorithm is immune to such misbehavior.





§ ANALYSIS OF THE SW-LFSE ALGORITHM

The following is the main result of this section.

 Given an LTI system (<ref>) and a measurement model (<ref>), let the baseline communication graph 𝒢 be strongly (2f+1)-robust w.r.t. 𝒮_j, ∀λ_j∈Ω_U(𝐀). Furthermore, let Assumptions 1 and 2 be met. Then, the proposed SW-LFSE algorithm guarantees the following despite the actions of any set of f-local Byzantine adversaries.

 

  * (Asymptotic Stability) Each regular node i∈ℛ can asymptotically estimate the state of the plant, i.e., lim_k→∞ ||𝐱̂_i[k]-𝐱[k]||=0, ∀ i ∈ℛ, where 𝐱̂_i[k] is the estimate of the state 𝐱[k] maintained by node i.

  * (Rate of Convergence) Let e^(j)_i[k]=ẑ^(j)_i[k]-z^(j)[k] denote the error in estimation of the component z^(j)[k] by a regular node i ∈𝒱∖𝒮_j. Then, if node i belongs to level q of the MEDAG 𝒢_j, its estimation error e^(j)_i[k] satisfies the following inequality ∀ k ≥ (T+1)q:


    0.8!|e^(j)_i[k]| ≤β^(j)[(N-(2f+1))(|λ_j|/γ^(j))^(T+1)]^q(γ^(j))^k,

where β^(j) > 0 and γ^(j)∈ (0,1) are certain constants. 




Note that for each regular 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]-z^(j)[k]|=0. Equivalently, we show that for each λ_j ∈Ω_U(𝐀), every regular node i ∈𝒱∖𝒮_j can asymptotically recover z^(j)[k].

Consider an eigenvalue λ_j ∈Ω_U(𝐀). Since  ℰ[k]⊆ℰ for all k, Assumption 2 can hold only if the baseline graph 𝒢 contains 𝒢_j. The latter follows from the conditions of the Theorem and Lemma <ref>. Next, based on Assumption 2, notice that for all k ≥ T,  the union of the graphs over the interval [k-T,k] contains the MEDAG 𝒢_j. Recall that the sets {ℒ^(j)_0, ℒ^(j)_1, ⋯, ℒ^(j)_q, ⋯ℒ^(j)_T_j} form a partition of the set of regular nodes ℛ in such a MEDAG. We prove the desired result by inducting on the level number q. For q=0, ℒ^(j)_0=𝒮_j ∩ℛ from definition, and hence all nodes in level 0 can estimate z^(j)[k] asymptotically by virtue of Lemma <ref>. Next, consider a regular node i in ℒ^(j)_1 and let e^(j)_i[k] ≜ẑ^(j)_i[k]-z^(j)[k]. We first analyze the SW-LFSE update rule (<ref>). To this end, at each time-step k, let the neighbor set 𝒩^(j)_i of node i be partitioned into the sets 𝒰^(j)_i[k], ℳ^(j)_i[k] and 𝒥^(j)_i[k], where 𝒰^(j)_i[k] and 𝒥^(j)_i[k] contain f nodes each, with the highest and the lowest values of z̅^(j)_il[k] respectively, and ℳ^(j)_i[k] contains the remaining nodes in 𝒩^(j)_i. At any instant k, we can either have ℳ^(j)_i[k] ∩𝒜=0 or ℳ^(j)_i[k] ∩𝒜≠ 0. In the former case, all nodes in ℳ^(j)_i[k] belong to ℒ^(j)_0=𝒮_j∩ℛ. In the latter case, when node i uses values transmitted by adversarial nodes in its update rule, it follows from the SW-LFSE algorithm, the f-locality of the adversary model, and the fact that |𝒩^(j)_i| ≥ (2f+1), that for each l∈ℳ^(j)_i[k]∩𝒜, there exists a node u∈𝒰^(j)_i[k] and a node v∈𝒥^(j)_i[k] such that both u,v ∈ℒ^(j)_0, and z̅^(j)_iv[k]≤z̅^(j)_il[k] ≤z̅^(j)_iu[k], i.e., z̅^(j)_il[k] can be expressed as a convex combination of z̅^(j)_iu[k] and z̅^(j)_iv[k].[Explicit dependence of u,v on the parameters represented by i,j,l and k is not shown to avoid cluttering of the exposition.] Based on the above discussion and (<ref>), it follows that for all k, ẑ^(j)_i[k+1] belongs to the convex hull formed by λ_j z̅^(j)_il[k], l∈ℒ^(j)_0. Specifically, there exist weights w̅^(j)_il[k] such that ∑_l∈𝒩^(j)_i ∩ℒ^(j)_0w̅^(j)_il[k]=1, and 

    0.75!ẑ^(j)_i[k+1]= λ_j(∑_l∈𝒩^(j)_i ∩ℒ^(j)_0 w̅^(j)_il[k]z̅^(j)_il[k]).

Since ∑_l∈𝒩^(j)_i ∩ℒ^(j)_0w̅^(j)_il[k]=1, and z^(j)[k+1]=λ_jz^(j)[k] based on (<ref>), we obtain 

    0.95!z^(j)[k+1]=λ_j(∑_l∈𝒩^(j)_i ∩ℒ^(j)_0w̅^(j)_il[k]λ_j^τ_il[k]z^(j)[k-τ_il[k]]).

Based on Assumption 2 and step 1 of the SW-LFSE update rule, we have that for all k ≥ T, z̅^(j)_il[k]=λ_j^τ_il[k]ẑ^(j)_l[k-τ_il[k]], l∈𝒩^(j)_i ∩ℒ^(j)_0. Subtracting (<ref>) from (<ref>), we then obtain the following error dynamics for all k ≥ T:

    0.85!e^(j)_i[k+1]= λ_j(∑_l∈𝒩^(j)_i ∩ℒ^(j)_0w̅^(j)_il[k]λ_j^τ_il[k]e^(j)_l[k-τ_il[k]]).
 
Noting that the weights w̅^(j)_il[k] belong to [0,1], the delay terms τ^_il[k] are upper bounded by T for l∈𝒩^(j)_i∩ℛ, λ_j satisfies |λ_j| ≥ 1, and using the triangle inequality, we obtain the following based on (<ref>) for all k ≥ T:

    0.85!|e^(j)_i[k+1]| ≤ |λ_j|^(T+1)(∑_l∈𝒩^(j)_i ∩ℒ^(j)_0 |e^(j)_l[k-τ_il[k]]|).

For every l ∈ℒ^(j)_0, since e^(j)_l[k] converges asymptotically, and hence exponentially (the local Luenberger observer based dynamics are linear)  based on Lemma <ref>, there exist constants c^(j)_l > 0 and γ^(j)_l ∈ (0,1) such that |e^(j)_l[k]| ≤ c^(j)_l(γ^(j)_l)^k. Let β^(j)≜max_l∈ℒ^(j)_0 c^(j)_l and γ^(j)≜max_l∈ℒ^(j)_0γ^(j)_l. Then, we obtain the following inequality based on (<ref>) for all k≥ T:

    |e^(j)_i[k+1]| ≤ |λ_j|^(T+1)|ℳ^(j)_i[k]|β^(j)(γ^(j))^(k-T).

Finally, note that based on the rules of the SW-LFSE algorithm, at each time-step k ≥ T, node i discards 2f values and does not use its own estimate in the update rule (<ref>). Hence, we have |ℳ^(j)_i[k]| ≤ (N-(2f+1)). Thus, we obtain (<ref>) for q=1, implying exponential stability of the error dynamics (<ref>) for all nodes in level 1, since γ^(j)∈ (0,1). 

Suppose asymptotic stability holds for nodes in all levels from 0 to q (where 1 ≤ q ≤ T_j-1). It is easy to see that the result holds for all nodes in ℒ^(j)_q+1 as well, by noting that (i) a regular node i ∈ℒ^(j)_q+1 has 𝒩^(j)_i ∩ℛ⊆⋃^q_r=0ℒ^(j)_r, and (ii) any value z̅^(j)_il[k] used by node i in the update rule (<ref>) lies in the convex hull formed by z̅^(j)_iu[k], u∈⋃^q_r=0ℒ^(j)_r. Based on the induction hypothesis, asymptotic stability can then be argued using the same reasoning as the q=1 case. Verifying (<ref>) is a matter of straightforward algebra.


The above arguments can be used almost identically to analyze the impact of bounded communication delays (potentially random, time-varying) in the presence of adversaries, for static networks.[Here, by a bounded communication delay we imply that if (i,j)∈ℰ and i,j ∈ℛ, then any estimate transmitted by node i to node j at time-step k, is received by node j no later than time-step k+T, for some T∈ℤ_> 0.] We formalize this observation below.


Given an LTI system (<ref>) satisfying Assumption 1, and a measurement model (<ref>), let 𝒢[k]=𝒢∀ k, where 𝒢 is strongly (2f+1)-robust w.r.t. 𝒮_j, ∀λ_j∈Ω_U(𝐀). Furthermore, let communication delays between any pair of regular nodes in 𝒢 be bounded by some T ∈ℤ_>0. Then, the proposed SW-LFSE algorithm provides identical guarantees as in Theorem <ref>.



We conclude this section with the following remark.
 For each unstable/ marginally stable eigenvalue of the system, Theorem <ref> and Corollary <ref> explicitly relate the rates of convergence of the different non-source nodes to the the instability of the system mode under consideration, the delay upper bound T, and the respective distances of such nodes (captured by the different levels `q' of a MEDAG) from the corresponding sources of information. 




§ SECURE STATE ESTIMATION OVER ANALOG ERASURE CHANNELS


In this section, we explore the problem of secure distributed state estimation over a network where each communication link is modeled by an analog erasure channel as defined in <cit.>. Specifically, the transmission of information across any link (i,j) ∈ℰ is governed by a random process ξ_ij[k] that is memoryless, i.e., ξ_ij[k] is i.i.d. over time. Furthermore, across space, the packet dropping processes over different links are independent. For any k, the random variable ξ_ij[k] follows a Bernoulli fading distribution, i.e., ξ_ij[k]=0 with erasure probability p and ξ_ij[k]=1 with probability (1-p); the implications of ξ_ij[k] assuming the values 0 and 1 will be discussed shortly. 

Our objective in this section will be to design a secure distributed state estimation protocol that guarantees mean-square stability of the estimation error dynamics for each regular node, in the following sense.
(Mean-Square Stability (MSS))
The estimation error dynamics of the regular nodes is said to be mean-square stable if  lim_k→∞ E[||𝐞_i[k]||^2]=0, ∀ i ∈ℛ, where 𝐞_i[k]=𝐱̂_i[k]-𝐱[k], and the expectation is taken with respect to the packet dropping processes ξ_ij[k], (i,j) ∈ℰ.





 §.§ Channels with no delay


We first consider the case where ξ_ij[k]=1 implies that any data packet transmitted by node i at time k is received perfectly by node j at time k, and when ξ_ij[k]=0, such a packet is dropped completely. For this model, we propose a simple algorithm described as follows.

For each λ_j ∈𝒰𝒪_i, a regular node i updates its estimate of z^(j)[k] in the following manner.



  * At each time-step k, if it receives estimates from at least (2f+1) nodes in 𝒩^(j)_i, it runs the LFSE algorithm, i.e., it removes the largest f and the smallest f estimates ẑ^(j)_l[k], l∈𝒩^(j)_i and updates ẑ^(j)_i[k] as

    0.8!ẑ^(j)_i[k+1]=λ_j(∑_l∈ℳ^(j)_i[k]w^(j)_il[k] ẑ^(j)_l[k]),

where the set ℳ^(j)_i[k] and the weights w^(j)_il[k] are defined as in the description of the SW-LFSE algorithm in Section <ref>. Otherwise, it runs open-loop as follows:

    ẑ^(j)_i[k+1]=λ_jẑ^(j)_i[k].


The above algorithm provides the following guarantees. 

Given an LTI system (1) satisfying Assumption 1, and a measurement model (2), let the baseline communication graph 𝒢 be strongly (mf+1)-robust w.r.t. 𝒮_j, ∀λ_j∈Ω_U(𝐀), where m∈ℤ_>0. For each (i,j) ∈ℰ, let ξ_ij[k] be a Bernoulli packet dropping process with erasure probability p, that is i.i.d. over time and independent of packet dropping processes over other links. Suppose m ≥ 3 and that the following is true:[The choice of m ≥ 3 is justified in Remark <ref>.]

    ρ^2p̅ < 1,

where ρ is the spectral radius of 𝐀, and 

    p̅≜ 1-∑_l=(2f+1)^(m-1)f+1(m-1)f+1l(1-p)^lp^(m-1)f+(1-l).

Then, the secure distributed state estimation algorithm described by the update rules (<ref>) and (<ref>) guarantees mean-square stability in the sense of Definition <ref>, despite the actions of any f-local set of Byzantine adversaries



Note that the packet dropping processes do not affect the estimation of the locally detectable portions of the state, i.e., each regular node i can recover 𝐳_𝒪_i[k] asymptotically based on Lemma <ref>. Consider λ_j ∈Ω_U(𝐀). Since 𝒢 is strongly (mf+1)-robust w.r.t. 𝒮_j, a trivial extension of Lemma <ref> implies that in the MEDAG 𝒢_j, |𝒩^(j)_i| ≥ (mf+1), ∀ i ∈{𝒱∖𝒮_j}∩ℛ. We induct on the level numbers q of such a MEDAG 𝒢_j present in the baseline communication graph 𝒢. Let i be a node in level 1. Let ℐ_i[k] be an indicator random variable[To avoid cluttering the exposition, we drop the superscript `j' on ℐ_i[k] and certain other terms throughout the proof, since they can be inferred from context.] such that ℐ_i[k]=1 if node i uses the update rule (<ref>) and ℐ_i[k]=0 if node i uses the update rule (<ref>). To make the presentation clear, we make the following assumption. Suppose node i receives estimates from more than (2f+1) nodes in 𝒩^(j)_i at a certain time-step k. Then, after removing 2f estimates based on the LFSE algorithm, it listens to only a single node picked arbitrarily from ℳ^(j)_i[k], while running (<ref>).[The result continues to hold for the general update rule (<ref>).] Combining  (<ref>) and (<ref>), we obtain

    0.8!ẑ^(j)_i[k+1]=λ_j (ℐ_i[k]ẑ^(j)_i[k]+(1-ℐ_i[k])ẑ^(j)_l[k]),

where l ∈ℳ^(j)_i[k]. It is easy to see that the error e^(j)_i[k]=ẑ^(j)_i[k]-z^(j)[k] follows the dynamics:

    0.8!e^(j)_i[k+1]=λ_j (ℐ_i[k]e^(j)_i[k]+(1-ℐ_i[k])e^(j)_l[k]).

Defining σ^(j)_i[k] ≜ E[(e^(j)_i[k])^2], and using (<ref>), we obtain:

    σ^(j)_i[k+1]=   λ^2_j E[ℐ^2_i[k]]σ^(j)_i[k]+λ^2_jE[(1-ℐ_i[k])^2]σ^(j)_l[k] 
       +2λ^2_jE[ℐ_i[k]-ℐ^2_i[k]]E[(e^(j)_i[k])(e^(j)_l[k])]_g[k], 
    
    =   λ^2_jp^(j)_i[k]σ^(j)_i[k]+λ^2_j(1-p^(j)_i[k])σ^(j)_l[k], 
    ≤    (λ^2_jp̅)  σ^(j)_i[k]+λ^2_jσ^(j)_l[k],

where l∈ℳ^(j)_i[k] and p^(j)_i[k] is the probability that ℐ_i[k]=1. We now justify each of the above steps. For arriving at the first equality, we used the fact that e^(j)_i[k] is independent of ℐ_i[k] for any i∈ℛ, based on the update rules (<ref>) and (<ref>), and the nature of the packet dropping processes. The fact that e^(j)_l[k] (where l ∈ℳ^(j)_i[k]) is independent of ℐ_i[k] requires further arguments. In particular, suppose node l is adversarial and has precise knowledge of the number of packets received by node i at time-step k, i.e., suppose node l knows ℐ_i[k]. The estimate ẑ^(j)_l[k] it transmits to node i might then be influenced by the knowledge of ℐ_i[k]. Irrespective of such knowledge, whenever l∈ℳ^(j)_i[k], based on the LFSE update rule (<ref>) and the f-locality of the adversarial model, it follows from arguments identical to those in Theorem <ref> that e^(j)_l[k] can be expressed as a convex combination of e^(j)_u[k] and  e^(j)_v[k], for some u,v ∈ℒ^(j)_0. Since such nodes are regular, their errors at time k are independent of ℐ_i[k], and converge to 0 since ℒ^(j)_0=𝒮_j∩ℛ. Thus, for any l∈ℳ^(j)_i[k], e^(j)_l[k] and ℐ_i[k] are independent, and lim_k→∞σ^(j)_l[k]=0. Also, since ℐ_i[k] is an indicator random variable, E[ℐ_i[k]]=E[ℐ^2_i[k]]. Hence, g[k]=0 leading to the second equality in (<ref>).

For arriving at the final inequality, we first note that p^(j)_i[k] can potentially vary over time and across different nodes  since the adversarial nodes are allowed to behave arbitrarily. In particular, a compromised node may choose not to transmit estimates even if all out-going communication links from such a node are intact. Thus, since it is impossible to exactly compute p^(j)_i[k], we instead seek to upper-bound it. To this end, note that the probability that ℐ_i[k]=0, i.e., the probability that node i receives estimates from at least (2f+1) nodes in 𝒩^(j)_i at time k, is lower bounded by the probability that it receives estimates from at least (2f+1) nodes in 𝒩^(j)_i∩ℛ at time k. The latter probability can be further lower bounded by (1-p̅) (where p̅ is given by (<ref>)) by noting that |𝒩^(j)_i∩ℛ| ≥ ((m-1)f+1) based on the f-locality of the fault model. In light of the above discussion, we have p^(j)_i[k] ≤p̅, leading to the last inequality in (<ref>).

Finally, equation (<ref>) implies that λ^2_jp̅ < 1, and in turn guarantees that lim_k→∞σ^(j)_i[k]=0, based on Input to State Stability (ISS) and the foregoing discussion. 

Suppose lim_k→∞σ^(j)_i[k]=0 for all nodes in levels 0 to q. Consider a node i ∈ℒ^(j)_q+1[k]. Its error dynamics evolves based on (<ref>), with g[k]=0 for reasons discussed above, and e^(j)_l[k]=α^(j)_il[k]e^(j)_u[k]+(1-α^(j)_il[k])e^(j)_v[k], for some α^(j)_il[k]∈ [0,1], and some u,v ∈⋃_r=0^qℒ^(j)_r. The last argument follows from the LFSE update rule (<ref>). Since σ^(j)_u[k] and σ^(j)_v[k] converge to 0 based on the induction hypothesis, the term E[(e^(j)_u[k])(e^(j)_v[k])] appearing in σ^(j)_l[k] can be upper-bounded by √(σ^(j)_u[k]σ^(j)_v[k]) by virtue of the Cauchy-Schwartz inequality. This implies lim_k→∞σ^(j)_l[k]=0, ∀  l ∈ℳ^(j)_i[k]. The rest of the proof can be completed following similar arguments as the q=1 case.


The term p̅ appearing in (<ref>) and (<ref>) can be interpreted as the effective packet drop/erasure probability for the problem under study. With this in mind, the implications of the above result are described as follows.
(Increasing `network robustness' reduces `effective packet drop probability') Given knowledge of the spectral radius ρ of 𝐀, an upper-bound f on the number of adversaries in the neighborhood of any regular node, and the erasure probability p of the communication network, suppose we are faced with the problem of designing a network topology that guarantees mean-square stability in the sense of Definition <ref>. Theorem <ref> provides an answer to this problem by quantitatively relating our notion of `strong-robustness' in Definition <ref> to the effective packet drop probability p̅. For instance, as shown in Figure <ref>, given the parameters ρ, f and p, one can generate a plot for ρ^2p̅ offline, and choose m to satisfy the MSS criterion ρ^2p̅ < 1. Subsequently, one can proceed to design a network that is strongly (mf+1)-robust w.r.t. 𝒮_j, λ_j ∈Ω_U(𝐀). It is easy to verify that p̅ is monotonically increasing in p, and monotonically decreasing in m. In other words, for a fixed ρ and f, one can tolerate higher erasure probabilities p by increasing the robustness parameter m.


 Note that when f=0, i.e., in the absence of adversaries, equation (<ref>) reduces to ρ^2 p < 1. This condition is reminiscent of the MSS criterion for remote stabilization of an LTI system over a Bernoulli packet dropping channel <cit.>. This observation can be explained by viewing the contribution due to the LFSE update (<ref>) (that helps stabilize the error dynamics (<ref>)) as an analogue of the stabilizing input in the remote stabilization problem.


 We must justify the need for m≥3 in Theorem <ref>. For a network that is strongly (mf+1)-robust with m ≤ 2, each adversarial node may follow the simple strategy of never transmitting its estimate. If the adversaries compromise f nodes in some set 𝒩^(j)_i, where i∈ℛ and λ_j ∈𝒰𝒪_i, then such a strategy might cause the regular node i to run open-loop forever based on the algorithm described by the update rules (<ref>) and (<ref>). Instead of running open-loop, suppose that if a regular node i does not hear from some neighbor in 𝒩^(j)_i at time k, it assigns a value of 0 to the corresponding estimate, and then employs the LFSE update rule (<ref>). Such an approach will in general not work either, due to the following reason. Unlike the communication loss model studied in Section <ref>, where each regular node was guaranteed to receive estimates from `enough' regular neighbors over bounded intervals of time, no such guarantees can be claimed for the analog erasure channel model studied here. Thus, while strongly (2f+1)-robust networks sufficed in Section <ref>, the choice of m≥3 is in fact necessary in the present context for achieving MSS  based on our specific approach. However, m=2 does suffice for certain variants of the analog erasure channel model, as we discuss next.






 §.§ Channels with erasure and delay

In this section, we consider a variant of the analog erasure channel that accounts for the presence of random delays. To this end, let (i,j)∈ℰ, and let 𝐯[k] be a message transmitted by node i to node j at time-step k. Then, a channel with delay and erasure causes node j to receive the following message:

    0.7!𝐫[k]=ξ_ij[k]𝐯[k]+(1-ξ_ij[k])𝐯[k-τ_ij[k]],
  
where ξ_ij[k] is the memory-less packet dropping process described earlier, τ_ij[k] ∈ℤ_> 0 is a random delay satisfying 1≤τ_ij[k]≤ T, and T ∈ℤ_>0. In words, the channel output 𝐫[k] is either equal to the present channel input 𝐯[k] with probability (1-e), or equal to a delayed channel input with probability e, where the delay is upper bounded by some positive constant T. It should be noted that the erasure channel model  considered here is a generalization of the erasure channel with delay in <cit.>, where the delays are constant. For this model, we have the following result.

Given an LTI system (1) satisfying Assumption 1, and a measurement model (2), let the baseline communication graph 𝒢 be strongly (2f+1)-robust w.r.t. 𝒮_j, ∀λ_j∈Ω_U(𝐀). Let each communication link of 𝒢 be modeled as a channel with delay and erasure as described by equation (<ref>). Then, the SW-LFSE algorithm provides identical guarantees as in Theorem <ref>, with probability 1.





 The proof follows from the following simple observation: based on the channel model (<ref>), note that for each λ_j ∈Ω_U(𝐀), every regular node i∈𝒱∖𝒮_j is guaranteed to receive a state estimate that is at most T time-steps delayed, from each of its regular neighbors in 𝒩^(j)_i, at every time-step k, ∀ k ≥ T. This corresponds to a special case of the bounded delay model in Corollary <ref>, and the result thus follows.





§ CONCLUSION



We developed secure distributed state estimation algorithms that account for adversarial nodes in the presence of communication losses, both deterministic and stochastic. For the former case, we characterized the convergence rate of our algorithm in terms of certain system and network properties, and for the latter scenario involving analog erasure channels, we established that our notion of `strong-robustness' plays an important role in tolerating high erasure probabilities while ensuring mean-square stability. As future work, it would be interesting to explore if exploiting sensor memory like the SW-LFSE approach in Section <ref> can help tolerate higher erasure probabilities for the analog erasure channel model considered in Section <ref>.

IEEEtran 



