# On the detection and identification of edge disconnections in a multi-agent
consensus network

Gianfranco Parlangeli and Maria Elena Valcher G. Parlangeli is with the
Dipartimento di Ingegneria dell’Innovazione, Università del Salento, Via per
Monteroni, 73100 Lecce, Italy, e-mail<EMAIL_ADDRESS>M.E. Valcher is with the Dipartimento di Ingegneria dell’Informazione
Università di Padova, via Gradenigo 6B, 35131 Padova, Italy, e-mail:
<EMAIL_ADDRESS>
###### Abstract

In this paper we investigate the problem of the sudden disconnection of an
edge in a discrete-time multi-agent consensus network.  If the graph remains
strongly connected, the multi-agent system still achieves consensus, but in
general, unless the information exchange between each pair of agents is
symmetric, the agents’ states converge to a drifted value of the original
consensus value.  Consequently the edge disconnection can go unnoticed. In
this paper the problems of detecting an edge disconnection and of identifying
in a finite number of steps the exact edge that got disconnected are
investigated. Necessary and sufficient conditions for both problems to be
solvable are presented, both in case all the agents’ states are available and
in case only a subset of the agents’ states is measured. Finally, an example
of a network of 7 agents is provided, to illustrate some of the theoretical
results derived in the paper.

Keywords$-$ Multi-agent system, consensus, strongly connected network,
Laplacian, detection and identification,  edge disconnection.

##  I Introduction

The technology advances of the last decades brought brand new opportunities in
several engineering areas and stimulated a significant thrust of research in
communications, information processing and control theory [1, 17, 45], The
availability of miniaturized low-cost processing and integrated communication
devices allowing peer-to-peer communication pushed a renewed interest in the
analysis and design of distributed heterogeneous sensor networks and in the
cooperative control of networks of autonomous agents [3, 8].

For a network of agents, _consensus_ is a fundamental target, useful for
coordination, and a key tool to achieve decentralized architectures [22, 33,
35]. _Consensus_ refers to the situation when agents achieve a common decision
on a local variable, which is updated performing local computation and
exchanging local information [22]. Under the assumption that each agent
follows a prescribed protocol, the use of such local variable makes the system
behave as if the agents were fully connected (i.e. as if the communication
graph were complete) [23], and this condition enables a variety of
applications in a wide range of fields [6], [19], [34], [36], [42]. However,
the adherence of each agent to the agreed protocol may fail for a number of
reasons, and several research directions have been explored to achieve  robust
consensus in the presence of intermittent transmissions, transmission errors,
faults or noise [20], [21], [30, 44].

Malfunctions in a network, may be temporary or intermittent, casual or
intentional (for instance, they may be the results of a cyber-attack [28]),
and a long stream of research has been devoted to address fault-detection and
identification (FDI) problems or fault-tolerant control strategies for multi-
agent systems, see [30, Section II-B] for an extensive literature review. FDI
algorithms for multi-agent systems split into two classes: centralized and
distributed ones. In the first case [9, 27, 32], a central unit gathers all
the system information to perform the fault diagnosis algorithm. In the
distributed case [11, 27, 38], all agents run some local fault detection
algorithm, based on local information and on the signals received from
neighbouring agents, and they coordinate to decide whether and where the fault
occurred.

Most of the literature on FDI for multi-agent systems, however, assumes that
faults act additively either on the state-update equations or on the signals
exchanged by pairs of agents [11, 26, 27, 38]. Even if an edge disconnection
can be modelled in this way, this set-up is too general and it does not
exploit the correlation between the fault signal and the state evolution that
characterizes faults resulting from edge disconnections. As a result, FDI
conditions deduced in the general set-up do not exploit the special nature of
these faults, thus leading to conservative conditions for a successful and
prompt diagnosis when dealing with edge disconnection.

On the other hand, in general, the problem of detecting an edge disconnection
has been investigated for multi-agent systems that are not necessarily
consensus networks. For instance, in [4] and [29] the possibility of detecting
an edge or a node disconnection in a multi-agent system is investigated, and
the concepts of discernibility from the states or the outputs are
investigated. In [43] the problem of detecting an edge disconnection is
addressed for a diffusive network, by resorting to an impulsive input applied
at one specific node. Simple graph conditions allow to determine whether the
problem is solvable. The residual signal is generated at the specific node by
assuming that the whole network topology is known, and it depends on the whole
state trajectory. The authors of [9] use stochastic techniques and propose an
algorithm based on the full state knowledge to promptly detect abrupt
topological changes of the network such as a link failure, creation, or
degradation. In [12, 13, 39] the detection of a link disconnection in a
network from noisy measurements at a single node is investigated. By making
use of a Maximum A Posteriori Probability technique, conditions for asymptotic
detection, in terms of the network spectrum and graph, are derived. If the
detector does not know the whole state of the system, perfect detection is not
possible. Note, also, that none of the previous references explicitly
addresses the identification problem.

Few contributions have specifically addressed the problem of detecting and/or
identifying a link disconnection in a consensus network, by making use of the
network properties and of the very specific change of the network description
that results from this fault. Specifically, in [31] a multi-agent system
subjected to multiple communication link failures is considered, with the goal
of deriving useful design guidelines for reliable and fault-tolerant multi-
agent networks. The possibility of detecting multiple link failures
corresponding to at least some initial conditions is characterised in terms of
the communication graph properties. In [25] an algorithm for diffusion of
information among nodes reaching a weighted agreement is proposed, which is
informative of the topology of the network and can be applied to the detection
(but in general not the identification) of a link failure. In [32] a method to
detect and identify link failures in a network of continuous-time homogeneous
agents, with a weighted and directed communication graph, is proposed,
assuming that only the output responses of a subset of nodes are available.
Jump discontinuities in the output derivatives are used to detect link
failures. The order of the derivative at which the discontinuity is observed
depends on the relative degree of the agents transfer matrix, and on the
distance of the observation point from the disconnected edge. A graph based
algorithm to identify the link is presented. It is worth remarking that all
the previous references adopt a centralised approach to the problem solution.

This paper focuses on the problem of detecting and identifying an edge removal
within a network of agents reaching consensus. This type of fault may result
in a disconnected network, for which consensus is no longer achievable, and in
this case the fault cannot go unnoticed but it can be detected significantly
later than it occurred. Alternatively, the communication network may remain
connected, but a different algorithm is performed with respect to the original
one and this leads to agree on a final value which is different from the one
the original network would have achieved. For this reason it is fundamental to
detect and possibly identify disconnected edges, so that they can be promptly
restored. We assume, as it was done in the large majority of the
aforementioned references, that the agents represent devices with limited
functionalities. In general they have not the capability of detecting an edge
disconnection, not even when they are directly affected by it (by this meaning
that they are either the transmitter or the receiver at the extremes of the
disconnected edge), and hence they cannot send an alarm signal. This
assumption is extremely realistic when dealing with large networks of cheap
sensors, for instance, whose software is configured to perform very basic
tasks. Accordingly, we assume that the detection and identification of a
broken edge cannot be performed at local level by means of a distributed
algorithm that involves a subset of the agents and we propose centralised
algorithms that are able to identify a link disconnection from the knowledge
of either the entire state evolution or the state evolution of a subset of its
agents. In fact, a distributed FDI is typically possible only under the
condition that a selected group of agents is able to both generate a residual
signal and to communicate with each other to reach a decision about the
occurrence of a fault. This requires additional features with respect to the
basic ones that are imposed by the consensus algorithm. In addition to the
fact that for certain multi-agent systems, the physical nature of the devices
does not offer alternatives, the choice of adopting a centralised approach has
several motivations: first of all, what can be obtained in a centralised way
always represents a benchmark that distributed solutions try to approach as
much as they can, and since a clear analysis of this problem is not available
yet in the literature, we believe that this is the first goal to achieve.
Secondly, a centralised solution requires weaker properties in terms of
observability/reconstructibility than the ones that a distributed solution
would impose on the single agents. It is often the case that a wise choice of
a small set of agents whose states need to be monitored in a centralised way
allows an effective detection and identification, but those same agents would
not be able to independently perform FDI. This aspect will be better clarified
at the end of the paper. Finally, several distributed FDI algorithms rely on
the estimate of the overall state vector, and this is extremely demanding from
a computational point of view, as well as not realistic, since it presumes
that single agents may have a complete knowledge of the overall system
structure. Solutions that require the selected agents to estimate only
portions of the state vector typically impose very strong conditions of the
structural properties of the overall system and they are strongly dependent on
the specific system structure.

The paper structure is the following one. Section II presents the class of
discrete-time multi-agent systems and the general setting of the problem. In
Section III the effects of the disconnection of a single link are explored.
The problem of detecting an edge disconnection is tackled in Section IV, and
it is split into four subsections. The discernibility  of two networks, one of
them obtained from the other as a result of the disconnection of a link, is
studied in Subsection IV.A from a theoretical standpoint, assuming that the
whole state vector is available for measurement. Some special situations that
prevent discernibility are discussed. In Subsection IV.B an algorithm for link
failure detection and isolation is introduced and  it is shown that, if
discernibility conditions are satisfied, the algorithm can detect each fault
and isolate it under an additional condition.  Section V is devoted to the
discernibility problem when only a subset of nodes is available and in
Subsection V.A an algorithm for detecting the edge disconnection under these
conditions is provided. Also in this case, if discernibility conditions are
satisfied, the algorithm is able to detect each fault, while fault isolation
is ensured under an additional condition.  In Section VI the case of a network
of 7 nodes with only three states available for measurement is considered, and
the results derived in the paper are illustrated for different edge
disconnections.

The results provided in this paper have been inspired by [4], where the
concept of discernibility of a multi-agent system from the (faulty) one
resulting from an edge or a node disconnection have been first investigated.
Compared to [4], we tailor our analysis to a consensus network and hence
account for the fact that discernibility in a consensus network does not
reduce to the observability of a special matrix pair associated with the
healthy and the faulty systems. Indeed, the dominant eigenvalue/eigenvector
that ensure consensus do not change after the edge disconnection and need to
be separately accounted for. In addition we have explicitly addressed the
identification problem and proposed an algorithm to identify which specific
link of the system got disconnected. To achieve this goal we have proposed a
residual generator that is based on a (full-order) dead-beat observer. This
solution has the great advantage of zeroing the effects of the initial
conditions in a finite number of steps, thus making it possible to promptly
detect an edge disconnection in the minimal number of steps, even when the
effects of such a disconnection are small and hence may be erroneously
interpreted as the effect of disturbances. This manuscript extends the edge
failure analysis first performed in [40] and then summarized in [41] (this
latter paper presents some preliminary results about node disconnection and
compares such results with those obtained in [40] for the edge disconnection)
in the following way. First of all in this paper we address the case of a
directed communication graph, rather than an undirected one.  While Sections
II and III represent slightly modified versions of the original Sections II
and III in [40], the analysis in the following sections is sigificantly
improved and extended compared to the one presented in [40]. The proof of
Proposition 3 is new. The whole part of subsection IV.A, after Remark 6 (in
particular, Proposition 7), and subsection IV.B (in particular, Proposition 8)
are original. Since this last part deals with the problem of providing a
method to detect and identify the specific edge that got disconnected, we
believe that there is a significant added value with respect to the original
conference paper [40]. Also, the proof of Proposition 9 in Section V is
original, and the whole Subsection V.A, providing conditions for fault
detection and identification of an edge disconnection when only a subset of
the states is available, is original. Finally, Section VI provides a useful
illustrative example and is new. We believe that the current results provide a
first meaningful step toward the final goal of first determining necessary and
sufficient conditions for detecting and identifying all kinds of  edge/mode
faults, for general classes of homogeneous multi-agent systems, and then
designing practical algorithms to perform their detection and identification.

Notation. ${\mathbb{Z}}_{+}$ and $\mathbb{R}_{+}$ denote the set of
nonnegative integer and real numbers, respectively. Given
$k,n\in{\mathbb{Z}}_{+},k<n,$ we denote by $[k,n]$ the set of integers
$\\{k,k+1,\dots,n\\}$. We let $\mathbf{e}_{i}$ denote the $i$-th element of
the canonical basis in ${\mathbb{R}}^{k}$ ($k$ being clear from the context),
with all entries equal to zero except for the $i$-th one which is unitary.
${\bf 1}_{k}$ and ${\bf 0}_{k}$ denote the $k$-dimensional real vector whose
entries are all $1$ or all $0$, respectively. Given a real matrix $A$, the
$(i,j)$-th entry of $A$ is denoted either by $a_{ij}$ or by $[A]_{ij}$, and
its transpose by $A^{\top}$. Given a vector ${\bf v}$, the $i$-th entry of
${\bf v}$ is denoted by $v_{i}$ or by $[{\bf v}]_{i}$. The _spectrum_ of
$A\in{\mathbb{R}}^{n\times n}$, denoted by $\sigma(A)$, is the set of its
eigenvalues and the _spectral radius_ of $A$, denoted by $\rho_{A}$, is the
maximum modulus of the elements of $\sigma(A)$. For a nonnegative matrix
$A\in{\mathbb{R}}_{+}^{n\times n}$, i.e., a matrix whose entries are
nonnegative real numbers, the spectral radius is always an eigenvalue. A
nonnegative and nonzero matrix is called positive, while a matrix whose
entries are all positive is called strictly positive. Nonnegative, positive
and strictly positive vectors are analogously defined. A positive matrix
$A\in\mathbb{R}_{+}^{n\times n},n>1,$ is irreducible if no permutation matrix
$P$ can be found such that

$P^{\top}AP=\begin{bmatrix}A_{11}&A_{12}\cr 0&A_{22}\end{bmatrix},$

where $A_{11}$ and $A_{22}$ are square  (non-vacuous) matrices. By the Perron-
Frobenius theorem [5, 15, 22], for an irreducible positive matrix $A$ the
spectral radius $\rho_{A}$ is a simple real dominant eigenvalue, and the
corresponding left and right eigenvectors are strictly positive. Positive
eigenvectors of a positive irreducible matrix necessarily correspond to the
spectral radius.

A directed weighted graph ${\mathcal{G}}$ is a triple
$({\mathcal{V}},{\mathcal{E}},{\color[rgb]{0,0,0}{\mathcal{W}}})$, where
${\mathcal{V}}=[1,N]$ is the set of vertices,
${\mathcal{E}}\subseteq{\mathcal{V}}\times{\mathcal{V}}$ is the set of arcs,
and ${\color[rgb]{0,0,0}{\mathcal{W}}}$ is the matrix of the weights of
${\mathcal{G}}$. ${\color[rgb]{0,0,0}{\mathcal{W}}}$ is called adjacency
matrix of the graph. The $(i,j)$-th entry of
${\color[rgb]{0,0,0}{\mathcal{W}}}$,
$[{\color[rgb]{0,0,0}{\mathcal{W}}}]_{ij}$, is nonzero if and only if the arc
$(j,i)$ belongs to ${\mathcal{E}}$. We assume that
$[{\color[rgb]{0,0,0}{\mathcal{W}}}]_{ii}=0,$ for all $i\in[1,N]$, namely
there are no self-loops. A weighted graph
${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}},{\color[rgb]{0,0,0}{\mathcal{W}}})$
is undirected  if the arcs are bidirectional, namely $(j,i)\in{\mathcal{E}}$
if and only if $(i,j)\in{\mathcal{E}}$ and
$[{\color[rgb]{0,0,0}{\mathcal{W}}}]_{ij}=[{\color[rgb]{0,0,0}{\mathcal{W}}}]_{ji}.$
Therefore for undirected graphs
${\color[rgb]{0,0,0}{\mathcal{W}}}={\color[rgb]{0,0,0}{\mathcal{W}}}^{T}$.

A path connecting $j$ and $i$ is an ordered sequence of arcs
$(j,i_{1}),(i_{1},i_{2}),\dots,(i_{k-1},i_{k}),(i_{k},i)\in{\mathcal{E}}$. A
directed (resp. undirected) graph ${\mathcal{G}}$ is strongly connected
(connected) if, for every pair of vertices $j$ and $i$, there is a path
connecting them. ${\mathcal{G}}$ is  strongly connected (connected) if and
only if its  (symmetric) adjacency matrix ${\color[rgb]{0,0,0}{\mathcal{W}}}$
is irreducible.
The Laplacian matrix [16] associated with the adjacency matrix
${\color[rgb]{0,0,0}{\mathcal{W}}}$ is defined as
${\mathcal{L}}:={\mathcal{C}}-{\color[rgb]{0,0,0}{\mathcal{W}}},$ where
${\mathcal{C}}$ is the (diagonal) connectivity matrix, whose diagonal entries
are the sums of the corresponding row entries of
${\color[rgb]{0,0,0}{\mathcal{W}}}$, namely
$[{\mathcal{C}}]_{ii}=\sum_{j=1}^{N}[{\mathcal{W}}]_{ij},\forall i\in[1,N]$.
Clearly, by the way the Laplacian has been defined ${\mathcal{L}}{\bf
1}_{N}={\bf 0}_{N}$. Also, ${\mathcal{L}}$ is irreducible if and only if
${\color[rgb]{0,0,0}{\mathcal{W}}}$ is irreducible. If ${\mathcal{G}}$ is
undirected then the associated Laplacian ${\mathcal{L}}$ is symmetric.
A family $\pi=\\{{\mathcal{V}}_{1},..,{\mathcal{V}}_{k}\\}$ of non-empty
subsets of ${\mathcal{V}}$ such that
$\cup_{i=1}^{k}{\mathcal{V}}_{i}={\mathcal{V}}$ and
${\mathcal{V}}_{i}\cap{\mathcal{V}}_{j}=\emptyset$, $\forall i\neq j$, is
called a partition of the vertex set ${\mathcal{V}}$. When so,
${\mathcal{V}}_{i}$ is called the $i$-th _cell_ of the partition $\pi$, and
the vector ${\mathbf{x}}\in\mathbb{R}^{N}$ satisfying $x_{\ell}=1$ if
$\ell\in{\mathcal{V}}_{i}$ and $x_{\ell}=0$ if $\ell\notin{\mathcal{V}}_{i}$,
i.e., ${\bf x}=\sum_{\ell\in{\mathcal{V}}_{i}}{\bf e}_{\ell}$, is called the
_characteristic vector_ of the $i$-th cell ${\mathcal{V}}_{i}$. Finally, the
matrix $P_{\pi}\in\mathbb{R}^{N\times k}$, whose $i$-th column is the
characteristic vector of the subset ${\mathcal{V}}_{i}$ is called the
_characteristic matrix_ of $\pi$.

##  II Problem setup

Consider a multi-agent system consisting of $N>2$ agents, each of them indexed
in the integer set $[1,N]$. The state of the $i$-th agent is described by the
scalar variable $x_{i}$ that updates according to the following discrete-time
linear state-space model [23]:

$x_{i}(t+1)=x_{i}(t)+v_{i}(t),\qquad t\in\mathbb{Z}_{+},$

where $v_{i}$ is the input of the $i$-th agent. The communication among the
$N$ agents is described by a fixed directed graph ${\mathcal{G}}$ with
adjacency matrix ${\color[rgb]{0,0,0}{\mathcal{W}}}\in{\mathbb{R}}^{N\times
N}$. The $(i,j)$-th entry,  $i\neq j$, of ${\color[rgb]{0,0,0}{\mathcal{W}}}$
is positive, i.e., $[{\color[rgb]{0,0,0}{\mathcal{W}}}]_{ij}>0$, if there is
information flowing from agent $j$ to agent $i$, and
$[{\color[rgb]{0,0,0}{\mathcal{W}}}]_{ij}=0$ otherwise. Each agent adopts the
(nearest neighbor linear) consensus protocol [23], which amounts to saying
that the input $v_{i}$ takes the form:

$v_{i}(t)=\kappa\sum_{j=1}^{N}[{\color[rgb]{0,0,0}{\mathcal{W}}}]_{ij}(x_{j}(t)-x_{i}(t)),$
(1)

where $\kappa>0$ is a given real parameter known as coupling strength111 If we
regard the discrete-time system describing the $i$-th agent dynamics as the
discretized version of the continuous-time equation $\dot{x}_{i}(t)=v_{i}(t)$,
$\kappa$ represents the sampling time.. If we stack the states of the agents
in a single state vector ${\bf x}\in\mathbb{R}^{N}$, the overall multi-agent
system becomes

${\bf x}(t+1)=(I_{N}-\kappa{\mathcal{L}}){\bf x}(t)=:A{\bf x}(t),$ (2)

where ${\mathcal{L}}=[\ell_{ij}]\in{\mathbb{R}}^{N\times N}$ is the Laplacian
associated with the adjacency matrix ${\color[rgb]{0,0,0}{\mathcal{W}}}$. It
is easy to deduce the relationship between eigenvalues
$\lambda_{A}\in\sigma(A)$ and $\lambda_{\mathcal{L}}\in\sigma({\mathcal{L}})$,
namely

$\lambda_{A}=1-\kappa\lambda_{\mathcal{L}}.$ (3)

In particular, ${\mathcal{L}}{\bf 1}_{N}={\bf 0}_{N}$ implies that $A{\bf
1}_{N}={\bf 1}_{N}$.

System (2) can be used to describe a wide variety of situations where each
agent/node shares information with its neighbours with the final goal of
converging to a common  decision. If so, we refer to the multi-agent system as
to a consensus network. More formally, system (2) is a consensus network if
for every initial state ${\bf x}(0)$ there exists $\alpha\in\mathbb{R}$ such
that

$\lim_{t\to+\infty}{\bf x}(t)=\alpha\mathbf{1}_{N}.$ (4)

The constant $\alpha$ is called the _consensus value_ [22] for system (2),
corresponding to the given initial state. If the agents’ communication graph
is strongly connected, namely the Laplacian ${\mathcal{L}}$ is irreducible
[22], and the coupling strength $\kappa$ satisfies the following constraint:

$0<\kappa<\frac{1}{\max_{i\in[1,N]}\ell_{ii}},$ (5)

$\ell_{ii}$ being the $i$-th diagonal entry of ${\mathcal{L}}$, system (2) is
a consensus network (see Theorem 2 in [22]). Moreover, the consensus value is

$\alpha={\bf w}_{A}^{\top}{\bf x}(0),$ (6)

where ${\bf w}_{A}$ is the left eigenvector of $A$ corresponding to $1$ and
satisfying ${\bf w}_{A}^{\top}{\bf 1}_{N}=1$. In the special case when the
graph is undirected and hence ${\mathcal{L}}$ and $A$ are symmetric, ${\bf
w}_{A}=\frac{1}{N}{\bf 1}_{N}$ and hence the consensus value is the average
value of the agents’ initial conditions.
Assumption 1. In the following we steadily assume that ${\mathcal{L}}$ is
irreducible and $\kappa$ satisfies the inequalities in (5). Consequently,
$A=I_{N}-\kappa{\mathcal{L}}$ is a positive irreducible matrix. Perron-
Frobenius theorem and condition $A{\bf 1}_{N}={\bf 1}_{N}$ ensure that $1$ is
a simple dominant eigenvalue of $A$. The eigenspace associated with the
unitary eigenvalue is $\langle{\bf 1}_{N}\rangle$, and the positive
eigenvectors of $A$ necessarily correspond to $\lambda=1$ and hence belong to
$\langle{\bf 1}_{N}\rangle$.

In this paper we investigate the effects of  an edge disconnection on a
consensus network, and the possibility of detecting and identifying such a
failure.

##  III Consensus after an edge disconnection

If the communication from agent $r$ to agent $h$ is interrupted, namely the
arc $(r,h),r\neq h,$ is disconnected, then the Laplacian $\bar{\mathcal{L}}$
of the new digraph222In order not to make the notation heavy, in this part of
the paper we denote by $\bar{\mathcal{G}}$ the new digraph, by
$\bar{\mathcal{L}}$ its Laplacian and by $\bar{A}$ the new system matrix,
without highlighting in the notation the specific link that gets disconnected.
Later on, we will modify the notation to distinguish the effects of different
edge disconnections. $\bar{\mathcal{G}}$ is related to the Laplacian
${\mathcal{L}}=[\ell_{ij}]$ of the original digraph ${\mathcal{G}}$ by the
relationship

$\bar{\mathcal{L}}={\mathcal{L}}+\ell_{hr}{\bf e}_{h}{\bf
e}_{h}^{\top}-\ell_{hr}{\bf e}_{h}{\bf
e}_{r}^{\top}={\mathcal{L}}+\ell_{hr}{\bf e}_{h}[{\bf e}_{h}-{\bf
e}_{r}]^{\top},$

where $\ell_{hr}=-[{\color[rgb]{0,0,0}{\mathcal{W}}}]_{hr}<0$. Consequently,
the new state-update matrix of the multi-agent system becomes

$\bar{A}:=I_{N}-\kappa\bar{\mathcal{L}}=A-\kappa\ell_{hr}{\bf e}_{h}[{\bf
e}_{h}-{\bf e}_{r}]^{\top}.$ (7)

In the specific case when the graph is undirected, the disconnection of the
arc $(r,h)$ implies also the disconnection of the arc $(h,r)$. Consequently

$\displaystyle\bar{\mathcal{L}}$ $\displaystyle=$
$\displaystyle{\mathcal{L}}+\ell_{hr}[{\bf e}_{h}-{\bf e}_{r}][{\bf
e}_{h}-{\bf e}_{r}]^{\top},$ $\displaystyle\bar{A}$ $\displaystyle=$
$\displaystyle A-\kappa\ell_{hr}[{\bf e}_{h}-{\bf e}_{r}][{\bf e}_{h}-{\bf
e}_{r}]^{\top}.$ (8)

If the edge disconnection compromises the agents’ mutual exchange of
information, to the extent of destroying the graph connectivity, then
consensus will not be reached, and the effects of the fault on the network
will make fault detection eventually possible. On the other hand, an edge
disconnection that does not affect the graph connectivity, will allow the
system to still reach consensus but on a different value from the original
one, and the fault may hence go unnoticed and seriously affect the system
functioning. For these reasons, in this paper we will investigate the effects
of a single edge disconnection by assuming that the strong connectedness of
the communication graph is preserved after the failure.  The following
proposition, that makes use of some results derived in [23] for consensus
networks with switching topologies, highlights that under this assumption we
still have a consensus network, but in general the consensus value is
preserved after the disconnection only if the communication graph is
undirected.

######  Proposition 1.

Let ${\mathcal{L}}$ be the Laplacian of a strongly connected graph
${\mathcal{G}}$, and  set $A:=I_{N}-\kappa{\mathcal{L}}$, where $\kappa>0$ is
a fixed coupling strength, that has been chosen in order to ensure that system
(2) is a consensus network. Let $\bar{\mathcal{L}}$ be the Laplacian of the
graph $\bar{\mathcal{G}}$, obtained from ${\mathcal{G}}$ by removing the arc
$(r,h)$, and set $\bar{A}:=I_{N}-\kappa\bar{\mathcal{L}}$. If
$\bar{\mathcal{G}}$ is still strongly connected, then

  * i)

the system ${\bf x}(t+1)=(I_{N}-\kappa\bar{\mathcal{L}}){\bf x}(t)=\bar{A}{\bf
x}(t)$ is still a consensus network;

  * ii)

if the graph ${\mathcal{G}}$ is undirected, then for every choice of ${\bf
x}(0)$ and every time $\tau\geq 0$ at which the edge disconnection may occur,
the new network converges to the same consensus value to which the original
network would have converged before the disconnection;

  * iii)

if the graph ${\mathcal{G}}$ is directed, then for every $\tau\geq 0$ there
are initial states ${\bf x}(0)$ corresponding to which the consensus value
obtained by the new network, after the disconnection at $t=\tau$, differs from
the original one (6).

###### Proof.

i) Since the original network is a consensus network, ${\mathcal{L}}$ is
irreducible and $\kappa$ satisfies the constraint (5). On the other hand, by
assumption, the Laplacian $\bar{\mathcal{L}}$ is still irreducible and if we
denote by $\bar{\ell}_{ij}$ the $(i,j)$-th entry of $\bar{\mathcal{L}}$, then
$\max_{i\in[1,N]}\bar{\ell}_{ii}\leq\max_{i\in[1,N]}\ell_{ii},$ thus ensuring
that

$0<\kappa<\frac{1}{\max_{i\in[1,N]}\bar{\ell}_{ii}}.$

This is the case for both directed and undirected graphs. Consequently, also
the new network is a consensus network.

ii) and iii) Follow from the results obtained in [23] (see for instance
Theorems 4 and 9) for the consensus of continuous-time systems described as
integrators and with switching communication topologies.  ∎

##  IV Detecting an edge disconnection

In the rest of the paper we will focus on the case when the communication
graph is directed, and investigate in detail under what conditions we can
detect the edge disconnection. We will also steadily make the following
assumption.

Assumption 2. The graph $\bar{\mathcal{G}}$, describing the communication
network after the link failure, is strongly connected, and hence $\bar{A}$ is
still a positive irreducible matrix having $1$ as dominant eigenvalue and
${\bf 1}_{N}$ as dominant eigenvector.

We distinguish the case when we can observe the states of all the agents and
the case when we can observe the states of a subset of the agents. We also
adjust the definitions introduced in [4] (for the continuous-time case), to
keep into account that if the system has already reached consensus, which is
an equilibrium point for both the original network and the faulty one, then
every edge disconnection will not alter the consensus status, and hence will
produce a fault that is necessarily undetectable. Consequently, we introduce
the following definitions.

######  Definition 1.

Consider the multi-agent consensus network (2), and the network obtained from
(2) upon disconnection of the edge from agent $r$ to agent $h$:

${\bf x}(t+1)=\bar{A}{\bf x}(t),$ (9)

with $\bar{A}$ described as in (7). The two networks are said to be
discernible if for every fault time $\tau\geq 0$ and every state ${\bf
x}(\tau)\not\in\langle{\bf 1}_{N}\rangle$, there exists $t>\tau$ such that the
state trajectory of the faulty system (9) at time $t$, ${\bf
x}(t)=\bar{A}^{t-\tau}{\bf x}(\tau)$, is different from the state trajectory
of the original system at time $t$.
If only the states of $p<N$ agents are available, and we assume without loss
of generality that they are the first $p$ agents, we say that the two networks
are discernible from the observation of the first $p$ agents if for every
fault time $\tau\geq 0$ and every state ${\bf x}(\tau)\not\in\langle{\bf
1}_{N}\rangle$, the first $p$ entries of any state trajectory of the faulty
system (9) at time $t\geq\tau$, ${\bf x}(t)=\bar{A}^{t-\tau}\bar{\bf
x}_{\tau}$, are different from the first $p$ entries of the state trajectory
of the original system at time $t$ for at least one time instant $t$, namely
for every $\bar{\bf x}_{\tau}\in{\mathbb{R}}^{N}$ there exists $t\geq\tau$
such that

$\begin{bmatrix}I_{p}&0\end{bmatrix}\bar{A}^{t-\tau}\bar{\bf
x}_{\tau}\neq\begin{bmatrix}I_{p}&0\end{bmatrix}A^{t-\tau}{\bf x}(\tau).$ (10)

######  Remark 2.

If the edge fault is the outcome of an external attack, it is immediate to
realise that the concept of discernibility is in perfect agreement with the
property of a cyberphysical system to not be subjected to undetectable
attacks, explored in [28]. Note that the concept of discernibility here
adopted, and suitably adapted from the one given in [4], is different from the
concept of “detectabilty” (of an edge) adopted in [31] that only requires that
the state trajectories of the healthy and the faulty systems differ for at
least one choice of the initial condition.
Finally, discernibility is introduced here as a system theoretic property with
exact definition and mathematical characterisation. It is clear that in a
real-life environment, we need to account for disturbances and modeling
errors, that require to modify the previous theoretical condition (10) to
introduce a minimal threshold below which the disagreement of the measured
output with respect to the expected one is not interpreted as the effect of a
fault.

###  IV-A Discernibility after edge disconnection

In order to characterize discernibility, we may exploit the analysis in [4],
that refers to the matrices

$\Delta:=\begin{bmatrix}A&0\cr
0&\bar{A}\end{bmatrix}=I_{2N}-\kappa\begin{bmatrix}{\mathcal{L}}&0\cr
0&\bar{\mathcal{L}}\end{bmatrix},\quad\Gamma_{N}:=\begin{bmatrix}I_{N}&-I_{N}\end{bmatrix}.$
(11)

It is worth observing, however, that discernibility analysis in [4] is
carried out for homogeneous multi-agent systems, whose agents are generically
described by the same linear state-space model, and it is defined in such a
way that it coincides with the observability property of the pair
$(\Delta,\Gamma_{N})$. Observability, however, is impossible to guarantee when
the matrices $A$ and $\bar{A}$ are expressed in terms of the Laplacian as in
(2) and (8), and this is quite reasonable since the lack of observability is
related to the fact that if the disconnection happens when the network is
already in its steady state, then the fault cannot be detected, since the
constant trajectory $\alpha{\bf 1}_{N}$ is compatible both with the original
network and with the faulty one. We have modified the two definitions of
discernibility just to rule out this case, that is unavoidable and cannot be
regarded as a sign of bad performance. Clearly, this will lead to different
characterizations of the two discernibility properties.

We can now provide the following result, that adjusts and extends the one
given in Theorem 1 of [4].

######  Proposition 3.

Given the networks (2) and (9), this latter obtained from the former after the
disconnection of the edge $(r,h)$, assume that Assumptions 1 and 2 hold. Then
the following facts are equivalent:

  * i)

the networks (2) and (9) are discernible;

  * ii)

the unobservable states of the pair $(\Delta,\Gamma_{N})$ are those in
$\langle{\bf 1}_{2N}\rangle$ and they correspond to the unitary eigenvalue;

  * iii)

the unobservable states of the pair $(A,[{\bf e}_{r}-{\bf e}_{h}]^{\top})$ are
those in $\langle{\bf 1}_{N}\rangle$ and they correspond to the unitary
eigenvalue;

  * iv)

there is no eigenvalue-eigenvector pair $(\lambda,{\bf v})$, with
$\lambda\in{\mathbb{C}}$ and ${\bf v}\neq 0$, except for $\lambda=1$ and ${\bf
v}\in\langle{\bf 1}_{N}\rangle$, such that

$A{\bf v}=\lambda{\bf v}\quad{\rm and}\quad[{\bf v}]_{r}=[{\bf v}]_{h}.$ (12)

  * v)

there is no eigenvalue-eigenvector pair $(\lambda,{\bf v})$, with
$\lambda\in{\mathbb{C}}$ and ${\bf v}\neq 0$, common to $A$ and $\bar{A}$,
except for $\lambda=1$ and ${\bf v}\in\langle{\bf 1}_{N}\rangle$.

###### Proof.

i) $\Leftrightarrow$ ii) Suppose that the networks (2) and (9) are not
discernible. Then there exist ${\bf x}(0)\not\in\langle{\bf 1}_{N}\rangle$
such that $\bar{A}^{t}{\bf x}(0)=A^{t}{\bf x}(0)$ for every $t\geq 0$. This is
equivalent to saying that $\begin{bmatrix}{\bf x}(0)\cr{\bf
x}(0)\end{bmatrix}$ is not observable for the pair $(\Delta,\Gamma_{N})$ and
it does not belong to $\langle{\bf 1}_{2N}\rangle$.
Conversely, suppose that there exists an unobservable state of the pair
$(\Delta,\Gamma_{N})$, ${\bf v}=\begin{bmatrix}{\bf v}_{1}\cr{\bf
v}_{2}\end{bmatrix}\not\in\langle{\bf 1}_{2N}\rangle$. Clearly, ${\bf v}_{1}$
must coincide with ${\bf v}_{2}$, and hence condition ${\bf
v}\not\in\langle{\bf 1}_{2N}\rangle$ implies ${\bf v}_{1}\not\in\langle{\bf
1}_{N}\rangle$. This implies that if at some $\tau\geq 0$ the original network
gets disconnected when ${\bf x}(\tau)={\bf v}_{1}$ then $\bar{A}^{t-\tau}{\bf
x}(\tau)=A^{t-\tau}{\bf x}(\tau)$ for every $t\geq\tau$, thus ruling out
discernibility.
ii) $\Leftrightarrow$ iii) Condition ii) is easily seen to be equivalent to
the following condition, expressed in terms of PBH observabilty matrix: if
there exist $\lambda\in{\mathbb{C}}$ and $\begin{bmatrix}{\bf v}\cr\bar{\bf
v}\end{bmatrix}\neq 0$ such that

$\begin{bmatrix}\lambda I_{N}-A&0\cr 0&\lambda I_{N}-\bar{A}\cr
I_{N}&-I_{N}\end{bmatrix}\begin{bmatrix}{\bf v}\cr\bar{\bf v}\end{bmatrix}=0,$
(13)

then $\lambda=1$ and $\begin{bmatrix}{\bf v}\cr\bar{\bf
v}\end{bmatrix}\in\langle 1_{2N}\rangle$. Similarly, condition iii) is
equivalent to saying that if $\lambda\in{\mathbb{C}}$ and ${\bf v}\neq 0$
exist such that

$\begin{bmatrix}\lambda I_{N}-A\cr[{\bf e}_{h}-{\bf
e}_{r}]^{\top}\end{bmatrix}{\bf v}=0,$ (14)

then $\lambda=1$ and ${\bf v}\in\langle 1_{N}\rangle$. On the other hand, it
is easily seen that (13) is equivalent to

$\begin{bmatrix}\lambda I_{N}-A&0\cr 0&\lambda
I_{N}-\bar{A}\end{bmatrix}\begin{bmatrix}{\bf v}\cr{\bf v}\end{bmatrix}=0,$
(15)

namely to

$\displaystyle A{\bf v}$ $\displaystyle=$ $\displaystyle\lambda{\bf v},$
$\displaystyle\bar{A}{\bf v}$ $\displaystyle=$ $\displaystyle\lambda{\bf v},$

and due to the relation between $A$ and $\bar{A}$, the previous two identities
are, in turn, equivalent to

$\displaystyle A{\bf v}$ $\displaystyle=$ $\displaystyle\lambda{\bf v},$
$\displaystyle[{\bf e}_{h}-{\bf e}_{r}]^{\top}{\bf v}$ $\displaystyle=$
$\displaystyle 0,$

that can be expressed in terms of the PBH observability criterion as in (14).
This proves ii) $\Leftrightarrow$ iii).

iii) $\Leftrightarrow$ iv) Obvious.

iv) $\Leftrightarrow$ v) It is easily seen that (12) holds if and only if
$A{\bf v}=\lambda{\bf v}=\bar{A}{\bf v}.$ So, the equivalence immediately
follows. ∎

######  Remark 4.

Conditions ii), iii) and iv) in Proposition 3 could be equivalently expressed
in terms of the matrices ${\mathcal{L}}$ and $\bar{\mathcal{L}}$ (instead of
$A$ and $\bar{A}$), and by replacing $\lambda_{A}=1$ with
$\lambda_{\mathcal{L}}=0$.

In the following, we consider some special cases of matrices $A$ (or,
equivalently, graph Laplacians ${\mathcal{L}}$) for which condition iv) in
Proposition 3 is violated. These situations rule out in advance
discernibility.

If there exists $\lambda\in\sigma(A),\lambda\neq 1,$ of geometric multiplicity
greater than $1$, then an eigenvector of $A$ corresponding to $\lambda$ can be
found such that condition (12) is satisfied thus making the old network and
the new network not discernible. So, a necessary condition for discernibility
is that  all the eigenvalues of $A$ have unitary geometric multiplicity ($A$
is cyclic [37] or, equivalently, non-derogatory [10]).

######  Lemma 5.

If $A$ has an eigenvalue $\lambda\neq 1$ of geometric multiplicity greater
than $1$, then there exists an eigenvector ${\bf v}$ corresponding to
$\lambda$ such that condition (12) holds.

###### Proof.

If $\lambda\in\sigma(A),\lambda\neq 1,$ has geometric multiplicity greater
than $1$, then there exist $2$ linearly independent eigenvectors, say ${\bf
v}_{1}$ and ${\bf v}_{2}$, corresponding to $\lambda$. Suppose that neither of
these eigenvectors has the $r$-th and the $h$-th entries that coincide.
Introduce the $2\times 2$ matrix

$M_{r,h}:=\begin{bmatrix}[{\bf v}_{1}]_{r}&[{\bf v}_{2}]_{r}\cr[{\bf
v}_{1}]_{h}&[{\bf v}_{2}]_{h}\end{bmatrix}.$

If $M_{r,h}$ is nonsingular, there exist
$a_{1},a_{2}\in{\mathbb{R}}\setminus\\{0\\}$ such that

$\begin{bmatrix}1\cr 1\end{bmatrix}=M_{r,h}\begin{bmatrix}a_{1}\cr
a_{2}\end{bmatrix}.$

If $M_{r,h}$ is singular, there exist
$a_{1},a_{2}\in{\mathbb{R}}\setminus\\{0\\}$ such that

$\begin{bmatrix}0\cr 0\end{bmatrix}=M_{r,h}\begin{bmatrix}a_{1}\cr
a_{2}\end{bmatrix}.$

In both cases the eigenvector ${\bf v}:=a_{1}{\bf v}_{1}+a_{2}{\bf v}_{2}$
satisfies $[{\bf v}]_{r}=[{\bf v}]_{h}.$ ∎

######  Remark 6.

If the graph ${\mathcal{G}}$ is undirected, $A$ is symmetric and hence
diagonalizable. Therefore algebraic multiplicities and geometric
multiplicities coincide. So, a necessary condition for discernibility is that
the $N$ eigenvalues of $A$ are all distinct.

We now further explore condition (12) of Proposition 3 and connect it to a
topological condition on ${\mathcal{G}}$. To this end, we need to introduce
the concept of nontrivial almost equitable partition for a directed weighted
graph ${\mathcal{G}}$, by extending the analogous notion given for undirected
unweighted graphs in [14]. Given a directed weighted graph
${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}},{\color[rgb]{0,0,0}{\mathcal{W}}})$,
a partition $\pi=\\{{\mathcal{V}}_{1},..,{\mathcal{V}}_{k}\\}$ of the set of
vertices ${\mathcal{V}}=[1,N]$ is said to be an _equitable partition_ for
${\mathcal{G}}$ if for every pair of cells
${\mathcal{V}}_{i},{\mathcal{V}}_{j},i,j\in[1,k]$, and every node $v$ of
${\mathcal{V}}_{i}$, the sum of the weights of all edges from the nodes in
${\mathcal{V}}_{j}$ to the node $v$ is a constant value that depends only on
$i$ and $j$, not on $v$. The partition $\pi$ is said to be an _almost_ (or
_relaxed_) equitable partition if the above condition holds for every pair
$(i,j),i,j\in[1,k]$, with $j\neq i$.

In formal terms, a partition $\pi$ is an almost equitable partition for the
directed weighted graph ${\mathcal{G}}$ if for every
${\mathcal{V}}_{i},{\mathcal{V}}_{j},i,j\in[1,k],i\neq j$, and every pair of
nodes $v_{1},v_{2}$ of ${\mathcal{V}}_{i}$,

$\sum_{u\in{\mathcal{V}}_{j}}[{\color[rgb]{0,0,0}{\mathcal{W}}}]_{v_{1}u}=\sum_{u\in{\mathcal{V}}_{j}}[{\color[rgb]{0,0,0}{\mathcal{W}}}]_{v_{2}u},$

or, equivalently, by using the Laplacian entries

$\sum_{u\in{\mathcal{V}}_{j}}\ell_{v_{1}u}=\sum_{u\in{\mathcal{V}}_{j}}\ell_{v_{2}u}.$
(16)

This amounts to saying that $\sum_{u\in{\mathcal{V}}_{j}}\ell_{vu}=d_{ij}$ for
every $v\in{\mathcal{V}}_{i}$ and every $j\neq i$. Clearly, $d_{ij}<0$. Note
that for any directed weighted graph ${\mathcal{G}}$, two trivial almost
equitable partitions always exist, namely (1) the one corresponding to $k=1$
and ${\mathcal{V}}_{1}={\mathcal{V}}$, and (2) the one corresponding to $k=N$
and each ${\mathcal{V}}_{i}$ consisting of a single distinct node. In the
following, when talking about almost equitable partitions, we will always rule
out the two trivial ones.

The fact that $\sum_{u\in{\mathcal{V}}_{j}}\ell_{vu}=d_{ij}$ for any
$v\in{\mathcal{V}}_{i}$ and $j\neq i$ suggests that it is possible to define
(an adjacency matrix and hence) a Laplacian
${\mathcal{L}}_{\pi}\in{\mathbb{R}}^{k\times k}$ for ${\mathcal{G}}$,
associated with $\pi$, as follows [7]:

$[{\mathcal{L}}_{\pi}]_{ij}=\left\\{\begin{array}[]{ccc}d_{ij},&{\rm if}&i\neq
j;\\\ -\sum_{h\in[1,k]\atop h\neq i}d_{ih},&{\rm if}&i=j.\end{array}\right.$
(17)

We now provide the following result that extends the analogous one for
undirected unweighted graphs derived in [7].

######  Proposition 7.

Given a directed weighted graph
${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}},{\color[rgb]{0,0,0}{\mathcal{W}}})$,
let $\pi=\\{{\mathcal{V}}_{1},..,{\mathcal{V}}_{k}\\}$ be a partition of the
set of vertices ${\mathcal{V}}$ and let $P_{\pi}$ be the characteristic matrix
of $\pi$ (see Notation in Section I). If $\pi$ is a (nontrivial) almost
equitable partition, then:

  * i)

${\mathcal{L}}P_{\pi}=P_{\pi}{\mathcal{L}}_{\pi};$

  * ii)

the spectra of ${\mathcal{L}}_{\pi}$ and ${\mathcal{L}}$ satisfy
$\sigma({\mathcal{L}}_{\pi})\subset\sigma({\mathcal{L}})$ and the associated
eigenvectors are related as follows

${\mathbf{u}}\in{\rm ker}(\lambda I_{k}-{\mathcal{L}}_{\pi})\Rightarrow
P_{\pi}{\mathbf{u}}\in{\rm ker}(\lambda I_{N}-{\mathcal{L}});$ (18)

  * iii)

$\forall\lambda\in\sigma({\mathcal{L}}_{\pi})\subset\sigma({\mathcal{L}})$,
$\exists{\mathbf{v}}\in{\rm ker}(\lambda I_{N}-{\mathcal{L}})$ such that
$\forall j\in[1,k]$

$[{\mathbf{v}}]_{r}=[{\mathbf{v}}]_{s}\qquad\forall r,s\in{\mathcal{V}}_{j}.$
(19)

###### Proof.

i) Set $n_{i}:=|{\mathcal{V}}_{i}|,i\in[1,k].$ It entails no loss of
generality assuming that ${\mathcal{V}}_{1}=[1,n_{1}]$ and
${\mathcal{V}}_{i}=[\sum_{h=1}^{i-1}n_{h}+1,\sum_{h=1}^{i-1}n_{h}+n_{i}]$ for
$i\in[2,k]$. Consequently,

$P_{\pi}=\begin{bmatrix}{\bf 1}_{n_{1}}&&&\cr&{\bf
1}_{n_{2}}&&\cr&&\ddots&\cr&&&{\bf 1}_{n_{k}}\end{bmatrix}.$

It is easily seen that

${\mathcal{L}}P_{\pi}=\begin{bmatrix}-\sum_{j\neq 1}d_{1j}{\bf
1}_{n_{1}}&d_{12}{\bf 1}_{n_{1}}&\dots&d_{1k}{\bf 1}_{n_{1}}\cr d_{21}{\bf
1}_{n_{2}}&-\sum_{j\neq 2}d_{2j}{\bf 1}_{n_{2}}&\dots&d_{2k}{\bf
1}_{n_{2}}\cr\vdots&\vdots&\ddots&\vdots\cr d_{k1}{\bf 1}_{n_{k}}&d_{k2}{\bf
1}_{n_{k}}&\dots&-\sum_{j\neq k}d_{kj}{\bf 1}_{n_{k}}\end{bmatrix}$

where we used the fact that if $v\in{\mathcal{V}}_{i}$ then $0={\bf
e}_{v}^{\top}{\mathcal{L}}{\bf
1}_{N}=\sum_{u\in{\mathcal{V}}_{i}}\ell_{vu}+\sum_{j\neq i}d_{ij}.$ It is
immediate then to see that i) holds.

ii) Let $\lambda$ be arbitrary in $\sigma({\mathcal{L}}_{\pi})$. If ${\bf u}$
is an eigenvector of ${\mathcal{L}}_{\pi}$ corresponding to $\lambda$, then
${\mathcal{L}}_{\pi}{\bf u}=\lambda{\bf u}$. So, by making use of point i), we
get ${\mathcal{L}}P_{\pi}{\bf u}=P_{\pi}{\mathcal{L}}_{\pi}{\bf u}=\lambda
P_{\pi}{\bf u}$. This shows that $\lambda\in\sigma({\mathcal{L}})$ (and hence
$\sigma({\mathcal{L}}_{\pi})\subset\sigma({\mathcal{L}})$), and that
$P_{\pi}{\bf u}$ is an eigenvector of ${\mathcal{L}}$ corresponding to
$\lambda$.

iii) By point ii) it is immediate to see that for every eigenvalue $\lambda$
of ${\mathcal{L}}_{\pi}$ there exists an eigenvector ${\bf v}$ of
${\mathcal{L}}$ corresponding to $\lambda$, taking the form ${\bf
v}=P_{\pi}{\bf u}$. Such an eigenvector clearly satisfies (19). ∎

To highlight the impact of this condition on our objectives, consider Fig.1.
As a consequence of Proposition 7, the multi-agent system whose communication
graph is depicted in Fig. 1 is subject to undetectable edge failures, which
are highlighted in red. Indeed, according to Proposition 3 point iv), the
failure of every link $(r,h)$ such that the matrix $A$ has an eigenvector
(corresponding to some non-unitary eigenvalue) whose $r$-th and $h$-th entries
coincide is not detectable because it produces a faulty network which is not
discernible from the original one. If $r$ and $h$ belong to the same $i$-th
cell of an almost equitable partition then it follows directly from
Proposition 7 that for every non-unitary eigenvalue of $A$, related through
(3) to a nonzero eigenvalue of $\mathcal{L}_{\pi}$, there exists an
eigenvector of $A$ whose $r$-th and $h$-th entries coincide.

Some of these undetectable links are critical and their failure may
significantly change the network structure, as for example egde $(1,2)$ whose
failure affects the network strong connectivity.

Figure 1: An example of a graph with a nontrivial equitable partition.
Failures of red edges are undetectable.

###  IV-B How to detect and identify an edge disconnection when the whole
state vector is available

If the states of all the agents are available, it is possible to easily
implement a residual based fault detection scheme to detect the disconnection
of the edge $(r,h)$. Specifically, assume, first, for the sake of simplicity
that all the eigenvalues of $A$ are real and that the Jordan form of $A$ is

$J_{A}=\begin{bmatrix}1&0\cr
0&\tilde{J}_{A}\end{bmatrix}=\begin{bmatrix}1&0&\dots&0\cr
0&J_{2}&\dots&0\cr\vdots&\vdots&\ddots&\vdots\cr
0&0&\dots&J_{n}\end{bmatrix},$ (20)

where  $J_{i},i\in[2,n],$ is an elementary Jordan block (of size $k_{i,max}$)
corresponding to the eigenvalue $\lambda_{i}$, with $|\lambda_{i}|<1$. Note
that we do not assume that $\lambda_{i}\neq\lambda_{j}$ for $i\neq j$, but
each $\lambda_{i}$ corresponds to a specific chain of generalised eigenvectors
${\bf v}_{i}^{(k)},k\in[1,k_{i,max}]$, where ${\bf v}_{i}^{(k)},$ is a
generalised eigenvector of order $k$ of $A$ corresponding to $\lambda_{i}$.
Let $T\in{\mathbb{R}}^{N\times N}$ be the nonsingular transformation matrix
with columns

$T=\begin{bmatrix}{\bf 1}_{N}&{\bf v}_{2}^{(1)}&{\bf v}_{2}^{(2)}&\dots&{\bf
v}_{2}^{(k_{2,max})}&\dots&{\bf v}_{n}^{(k_{n,max})}\end{bmatrix}.$ (21)

Then $T^{-1}AT=J_{A}$ and hence $T^{-1}A=J_{A}T^{-1}$. Set

$W:=\begin{bmatrix}{\bf
0}_{N-1}&I_{N-1}\end{bmatrix}T^{-1}\in{\mathbb{R}}^{(N-1)\times N}.$ (22)

Considering (20) and (22), it is easy to verify that $WA-\tilde{J}_{A}W=0$.
Consequently, as far as the system is correctly functioning, namely ${\bf
x}(t)=A{\bf x}(t-1)$, then the residual signal

${\bf r}(t)=W{\bf x}(t)-\tilde{J}_{A}W{\bf x}(t-1),\quad t\geq 1,$

is identically zero. In the case when the matrix $A$ has also complex
conjugate eigenvalues, then we can follow the same procedure and reasoning as
above, by replacing the Jordan form with the real Jordan form, and hence
pairing together pairs of complex conjugate eigenvalues and replacing pairs of
complex generalised eigenvectors of some order with equivalent pairs of real
generalised eigenvectors of the same order (see e.g. [18], Section 3.4.1). The
details are a little bit more involved from a notational viewpoint, but the
substance of the result does not change. For this reason, we omit the details.

We want to show, now, that under the discernibility assumption, unless ${\bf
x}(\tau)\in\langle{\bf 1}_{N}\rangle$, namely the disconnection of the edge
$(r,h)$ takes place at a time $t=\tau$ when the multi-agent system has already
reached consensus, then it is not possible that ${\bf r}(t)$ is identically
zero for $t>\tau$. This allows one to detect the disconnection of the edge
$(r,h)$. Additionally, we propose conditions that ensure that the edge
disconnection is not only detected but also identified, namely the specific
broken edge can be identified from the sequence of residual vectors. To this
end, it is convenient to replace the original notation $\bar{A}$ for the
state-space matrix after disconnection with a more specific notation that
indicates which specific edge got disconnected. Accordingly, we introduce the
following notation:

$\bar{A}_{ij}:=A-\kappa\ell_{ij}{\bf e}_{i}[{\bf e}_{i}-{\bf e}_{j}]^{\top},$

which is the state matrix of the system once the edge $(j,i)$ gets
disconnected for some $i,j\in[1,N],i\neq j$, (in particular, for
$(j,i)=(r,h)$).

######  Proposition 8.

Consider the networks (2) and (9), this latter obtained from the former after
the disconnection of the edge $(r,h)$ at some time $t=\tau$. If Assumptions
1-2 hold, and the networks (2) and (9) are discernible (i.e., one of the
equivalent conditions of Proposition 3 holds), then, unless ${\bf
x}(\tau)\in\langle{\bf 1}_{N}\rangle$, namely the network has already reached
consensus, there exists $t\in[\tau+1,\tau+N]$ such that ${\bf r}(t)\neq 0$.
Moreover, if for every $j\in[1,N]\setminus\\{r,h\\}$ (and not only for $j=r$),
the following conditions hold:
(i) the faulty network obtained by disconnecting $(j,h)$ is still strongly
connected and discernible from the original network,
(ii)

$\sigma(\bar{A}_{hr})\cap\sigma(\bar{A}_{hj})=\\{1\\},$ (23)

then it is possible to identify from the residual signal the edge $(r,h)$ that
got disconnected.

###### Proof.

If the disconnection of edge $(r,h)$ takes place at $t=\tau$, then for every
$k\geq 1$

$\displaystyle{\bf r}(\tau+k)$ $\displaystyle=$ $\displaystyle
W\bar{A}_{hr}{\bf x}(\tau+k-1)-\tilde{J}_{A}W{\bf x}(\tau+k-1)$ (24)
$\displaystyle=$
$\displaystyle[W\bar{A}_{hr}-\tilde{J}_{A}W]\bar{A}_{hr}^{k-1}{\bf x}(\tau)$
$\displaystyle=$ $\displaystyle-\kappa\ell_{hr}W{\bf e}_{h}[{\bf e}_{h}-{\bf
e}_{r}]^{\top}\bar{A}_{hr}^{k-1}{\bf x}(\tau),$

where we used the identities $\bar{A}_{hr}=A-\kappa\ell_{hr}{\bf e}_{h}[{\bf
e}_{h}-{\bf e}_{r}]^{\top}$ and $WA-\tilde{J}_{A}W=0$. Therefore ${\bf
r}(\tau+k)=0$ for every $k\geq 1$ if and only if ${\bf x}(\tau)\in{\rm
ker}{\mathcal{W}}_{hr},$ where

${\mathcal{W}}_{hr}:=\begin{bmatrix}-\kappa\ell_{hr}W{\bf e}_{h}({\bf
e}_{h}-{\bf e}_{r})^{\top}\cr-\kappa\ell_{hr}W{\bf e}_{h}({\bf e}_{h}-{\bf
e}_{r})^{\top}\bar{A}_{hr}\cr\vdots\cr-\kappa\ell_{hr}W{\bf e}_{h}({\bf
e}_{h}-{\bf e}_{r})^{\top}\bar{A}_{hr}^{N-1}\end{bmatrix},$ (25)

This amounts to saying that there exist $\lambda\in{\mathbb{C}}$ and ${\bf
v}\neq 0$ such that the PBH observability matrix satisfies

$\begin{bmatrix}\lambda I_{N}-\bar{A}_{hr}\cr W{\bf e}_{h}[{\bf e}_{h}-{\bf
e}_{r}]^{\top}\end{bmatrix}{\bf v}=0,$

but this is easily seen to be equivalent to the existence of
$\lambda\in{\mathbb{C}}$ and ${\bf v}\neq 0$ such that

$\left\\{\begin{matrix}\bar{A}_{hr}{\bf v}=\lambda{\bf v}\cr[{\bf e}_{h}-{\bf
e}_{r}]^{\top}{\bf v}=0,\end{matrix}\right.$

and therefore to the existence of $\lambda\in{\mathbb{C}}$ and ${\bf v}\neq 0$
such that

$\left\\{\begin{matrix}A{\bf v}=\lambda{\bf v}\cr[{\bf v}]_{h}=[{\bf
v}]_{r}.\end{matrix}\right.$

Discernibility assumption rules out the possibility that the previous
condition holds unless $\lambda=1$ and ${\bf v}\in\langle{\bf 1}_{N}\rangle$.
On the other hand, if the previous condition holds only for $\lambda=1$ and
${\bf v}\in\langle{\bf 1}_{N}\rangle$, this means that ${\bf
x}(\tau)\in\langle{\bf 1}_{N}\rangle$, namely the disconnection had taken
place after the network had reached consensus, a situation in which detection
is not possible. This proves that there exists $k\in[1,N]$ such that ${\bf
r}(\tau+k)\neq 0$.

Now we want to prove that under the assumptions that: (i) the disconnection of
any edge $(j,h)$ results in a new strongly connected network, discernible from
the original one, and (ii) condition (23) holds, it is possible to uniquely
identify the broken link from the residuals. By the previous part of the
proof, if the disconnection takes place at $t=\tau$ and ${\bf
x}(\tau)\not\in\langle{\bf 1}_{N}\rangle$, then at least one of the values
${\bf r}(\tau+k),k=1,2,\dots,N,$ must be nonzero. Set

$k^{*}:=\min\\{k\geq 1:{\bf r}(\tau+k)\neq 0\\}.$ (26)

Then ${\bf r}(\tau+k^{*})=c_{k^{*}}\cdot W{\bf e}_{h},$ where

$\displaystyle c_{k^{*}}$ $\displaystyle:=$
$\displaystyle-\kappa\ell_{hr}({\bf e}_{h}-{\bf
e}_{r})^{\top}\bar{A}_{hr}^{k^{*}-1}{\bf x}(\tau)$ $\displaystyle=$
$\displaystyle-\kappa\ell_{hr}({\bf e}_{h}-{\bf e}_{r})^{\top}{\bf
x}(\tau+k^{*}-1)$ $\displaystyle=$ $\displaystyle-\kappa\ell_{hr}\left([{\bf
x}(\tau+k^{*}-1)]_{h}-[{\bf x}(\tau+k^{*}-1)]_{r}\right)\neq 0.$

By Lemma 12 in the Appendix, we can claim that this vector uniquely identifies
the index $h$, namely one of the extremes of the edge that got disconnected.
We now note that

$\begin{bmatrix}{\bf r}(\tau+k^{*})\cr{\bf r}(\tau+k^{*}+1)\cr\vdots\cr{\bf
r}(\tau+k^{*}+2N-1)\end{bmatrix}=\begin{bmatrix}W{\bf e}_{h}&&&\cr&W{\bf
e}_{h}&&\cr&&\ddots&\cr&&&W{\bf e}_{h}\end{bmatrix}$
$\cdot\begin{bmatrix}({\bf e}_{h}-{\bf e}_{r})^{\top}\cr({\bf e}_{h}-{\bf
e}_{r})^{\top}\bar{A}_{hr}\cr\vdots\cr({\bf e}_{h}-{\bf
e}_{r})^{\top}\bar{A}_{hr}^{2N-1}\end{bmatrix}(-\kappa\ell_{hr}){\bf
x}(\tau+k^{*}-1).$

We have just proved that we can uniquely identify $W{\bf e}_{h}$ from the
first nonzero residual. Moreover, the block diagonal matrix having $W{\bf
e}_{h}$ as diagonal block is clearly of full column rank, and hence the vector
${\color[rgb]{0,0,0}{\bf Y}}\neq 0$ such that

$\begin{bmatrix}{\bf r}(\tau+k^{*})\cr{\bf r}(\tau+k^{*}+1)\cr\vdots\cr{\bf
r}(\tau+k^{*}+2N-1)\end{bmatrix}=\begin{bmatrix}W{\bf e}_{h}&&&\cr&W{\bf
e}_{h}&&\cr&&\ddots&\cr&&&W{\bf e}_{h}\end{bmatrix}{\color[rgb]{0,0,0}{\bf
Y}}$

is uniquely determined. Now, we want to show that under assumptions (i) and
(ii) we can uniquely identify the index $r$ such that

${\color[rgb]{0,0,0}{\bf Y}}\in{\rm Im}\begin{bmatrix}({\bf e}_{h}-{\bf
e}_{r})^{\top}\cr({\bf e}_{h}-{\bf e}_{r})^{\top}\bar{A}_{hr}\cr\vdots\cr({\bf
e}_{h}-{\bf e}_{r})^{\top}\bar{A}_{hr}^{2N-1}\end{bmatrix}.$

If this were not the case, then there would be another index $j\neq r$ (and
$j\neq h$) such that

${\color[rgb]{0,0,0}{\bf Y}}\in{\rm Im}\begin{bmatrix}({\bf e}_{h}-{\bf
e}_{r})^{\top}\cr({\bf e}_{h}-{\bf e}_{r})^{\top}\bar{A}_{hr}\cr\vdots\cr({\bf
e}_{h}-{\bf e}_{r})^{\top}\bar{A}_{hr}^{2N-1}\end{bmatrix}\cap{\rm
Im}\begin{bmatrix}({\bf e}_{h}-{\bf e}_{j})^{\top}\cr({\bf e}_{h}-{\bf
e}_{j})^{\top}\bar{A}_{hj}\cr\vdots\cr({\bf e}_{h}-{\bf
e}_{j})^{\top}\bar{A}_{hj}^{2N-1}\end{bmatrix},$

and hence there would be two nonzero vectors ${\bf z}_{r}$ and ${\bf z}_{j}$
such that

${\color[rgb]{0,0,0}{\bf Y}}=\begin{bmatrix}({\bf e}_{h}-{\bf
e}_{r})^{\top}\cr({\bf e}_{h}-{\bf e}_{r})^{\top}\bar{A}_{hr}\cr\vdots\cr({\bf
e}_{h}-{\bf e}_{r})^{\top}\bar{A}_{hr}^{2N-1}\end{bmatrix}{\bf
z}_{r}=-\begin{bmatrix}({\bf e}_{h}-{\bf e}_{j})^{\top}\cr({\bf e}_{h}-{\bf
e}_{j})^{\top}\bar{A}_{hj}\cr\vdots\cr({\bf e}_{h}-{\bf
e}_{j})^{\top}\bar{A}_{hj}^{2N-1}\end{bmatrix}{\bf z}_{j}.$

Clearly, neither ${\bf z}_{r}$ nor ${\bf z}_{j}$ can belong to $\langle{\bf
1}_{N}\rangle$, otherwise ${\color[rgb]{0,0,0}{\bf Y}}$ would be zero.
Condition

$0=\begin{bmatrix}({\bf e}_{h}-{\bf e}_{r})^{\top}&({\bf e}_{h}-{\bf
e}_{j})^{\top}\cr({\bf e}_{h}-{\bf e}_{r})^{\top}\bar{A}_{hr}&({\bf
e}_{h}-{\bf e}_{j})^{\top}\bar{A}_{hj}\cr\vdots&\vdots\cr({\bf e}_{h}-{\bf
e}_{r})^{\top}\bar{A}_{hr}^{2N-1}&({\bf e}_{h}-{\bf
e}_{j})^{\top}\bar{A}_{hj}^{2N-1}\end{bmatrix}\begin{bmatrix}{\bf
z}_{r}\cr{\bf z}_{j}\end{bmatrix}$

corresponds to saying that the unobservable subspace of the matrix pair

$\left(\begin{bmatrix}\bar{A}_{hr}&0\cr
0&\bar{A}_{hj}\end{bmatrix},\begin{bmatrix}({\bf e}_{h}-{\bf
e}_{r})^{\top}&({\bf e}_{h}-{\bf e}_{j})^{\top}\end{bmatrix}\right)$

includes the vector $\begin{bmatrix}{\bf z}_{r}\cr{\bf
z}_{j}\end{bmatrix}\not\in\langle{\bf 1}_{2N}\rangle.$ Clearly, by the
irreducibility assumption on $\bar{A}_{hr}$ and $\bar{A}_{hj}$, this cannot be
an eigenvector corresponding to $\lambda=1$. On the other hand, the fact that
${\bf z}_{r}$ and ${\bf z}_{j}$ are both nonzero implies that there is an
eigenvalue $\lambda\neq 1$ common to $\sigma(\bar{A}_{hr})$ and
$\sigma(\bar{A}_{hj})$. But this contradicts assumption (ii), and hence $r$ is
uniquely determined. ∎

We want now to sketch an algorithm to identify the edge $(r,h)$ that got
disconnected. Suppose that at $t=\tau$ the edge $(r,h)$ gets disconnected and
that the first nonzero residual after $t=\tau$ is ${\bf
r}(\tau+k^{*})=c_{k^{*}}\cdot W{\bf e}_{h}$, with $k^{*}>0$ and $c_{k^{*}}\neq
0$ defined as in (26) and (IV-B), respectively. By the previous reasoning, we
can claim that there exists a unique value of $h\in[1,N]$ such that ${\bf
r}(\tau+k^{*})\in\langle W{\bf e}_{h}\rangle$, and this allows to uniquely
identify $h$ and hence the coefficient $c_{k^{*}}$. From the knowledge of $h$
and $c_{k^{*}}$ one can infer the identity of $r$ by comparing the state value
of each in-neighbour of $h$ with the state value of the same node which
produces the residual ${\bf r}(\tau+k^{*})$. Since it must hold

$[{\bf x}(\tau+k^{*}-1)]_{r}=\dfrac{c_{k^{*}}}{\kappa\ell_{hr}}+[{\bf
x}(\tau+k-1)]_{h},$ (28)

$r$ must belong to the following set

$\displaystyle r\in{\mathcal{R}}_{k^{*}}\\!\\!\\!$ $\displaystyle:=$
$\displaystyle\\!\\!\\!\\{i\in[1,N],i\neq h:\ell_{hi}\neq 0\ {\rm and}$
$\displaystyle\\!\\!\\![{\bf
x}(\tau+k^{*}-1)]_{i}=\dfrac{c_{k^{*}}}{\kappa\ell_{hi}}+[{\bf
x}(\tau+k^{*}-1)]_{h}\\}.$

If $|{\mathcal{R}}_{k^{*}}|=1$, then $r$ is identified at the first step. If
not, one can evaluate the set ${\mathcal{R}}_{k^{*}+1}$ and then the
intersection ${\mathcal{R}}_{k^{*}}\cap{\mathcal{R}}_{k^{*}+1}$. By proceeding
in this way, based on the previous proof, this procedure identifies in a
finite number of steps the value of the index $r$ that represents the first
extreme of the edge that got disconnected, since there exists $0\leq d\leq
2N-1$ such that the set $\cap_{i=0}^{d}{\mathcal{R}}_{k^{*}+i}$ consists of a
single element.

We now explore the more interesting case of discernibility from the
observation of the first $p$ agents.

##  V Discernibility from the observation of the first $p$ agents after edge
disconnection

By referring to the second part of Definition 1, it is easily seen that
discernibility of the two systems from the observation of the first $p$ agents
imposes the observability of the original system. If not, condition (10) would
be contradicted for any unobservable state ${\bf x}(\tau)$ and ${\bf
x}_{\tau}=0$.
On the other hand, the lack of observability of the faulty system could lead
to some pathological situations, since the output measurements could possibly
lead to believe that the faulty network has already reached the consensus to
some constant value, while it is still evolving. So, in the following we will
assume:

Assumption 3. Both the original system and the faulty one are observable from
the first $p$ agents, namely both $(A,\begin{bmatrix}I_{p}&0\end{bmatrix})$
and $(\bar{A}_{hr},\begin{bmatrix}I_{p}&0\end{bmatrix})$ are observable.

Under this assumption, we will characterise discernibility from the
observation of the first $p$ agents in terms of the matrix pair
$(\Delta,\Gamma_{p})$, with

$\Delta:=\begin{bmatrix}A&0\cr
0&\bar{A}_{hr}\end{bmatrix}\qquad\Gamma_{p}:=\begin{bmatrix}I_{p}&0&-I_{p}&0\end{bmatrix}.$
(29)

It is worth noticing that since $A$ is a positive irreducible matrix, having
${\bf 1}_{N}$ as dominant eigenvector corresponding to the unitary eigenvalue,
clearly $1$ is always an observable eigenvalue of the pair
$(A,\begin{bmatrix}I_{p}&0\end{bmatrix})$, and hence if the pair would not be
observable, the eigenvalues of the non-observable subsystem would necessarily
have modulus smaller than $1$. The same reasoning applies to $\bar{A}_{hr}$,
as far as it remains irreducible. Finally, the irreducibility assumption on
both $A$ and $\bar{A}_{hr}$ ensures that the eigenspace of both $A$ and
$\bar{A}_{hr}$ corresponding to $\lambda=1$ is $\langle{\bf 1}_{N}\rangle$.
So, the only unobservable eigenvectors of $(\Delta,\Gamma_{p})$ corresponding
to the unitary eigenvalue are those belonging to $\langle{\bf 1}_{2N}\rangle$.

Assumption 3 and the previous comments are fundamental to derive the following
result, that extends Proposition 3 in [4].

######  Proposition 9.

Consider the networks (2) and (9), this latter obtained from the former after
the disconnection of the edge $(r,h)$, and assume that Assumptions 1, 2 and 3
hold. The following facts are equivalent:

  * i)

the networks (2) and (9) are discernible from the observation of the first $p$
agents;

  * ii)

the unobservable states of the pair $(\Delta,\Gamma_{p})$ are those in
$\langle{\bf 1}_{2N}\rangle$ and they correspond to the unitary eigenvalue;

  * iii)

for every $\lambda\in\sigma(A)\cap\sigma(\bar{A}_{hr}),\lambda\neq 1$,

${\rm rank}\begin{bmatrix}\lambda I_{N}-A&0\cr 0&\lambda I_{N}-\bar{A}_{hr}\cr
I_{p}\ \ \ 0&-I_{p}\ \ \ 0\end{bmatrix}=2N;$

  * iv)

there are no $\lambda\in{\mathbb{C}}$ and nonzero vectors ${\bf v},\bar{\bf
v}$, except for $\lambda=1$ and ${\bf v}=\bar{\bf v}\in\langle{\bf
1}_{N}\rangle$, such that

$\left\\{\begin{array}[]{rcl}A{\bf v}=\lambda{\bf v},&&\bar{A}_{hr}\bar{\bf
v}=\lambda\bar{\bf v}\\\ \begin{bmatrix}I_{p}&0\end{bmatrix}{\bf
v}&=&\begin{bmatrix}I_{p}&0\end{bmatrix}\bar{\bf v}.\end{array}\right.$ (30)

###### Proof.

i) $\Leftrightarrow$ ii) Suppose that the networks (2) and (9) are not
discernible from the observation of the first $p$ agents. Then there exist
${\bf x}(0)\not\in\langle{\bf 1}_{N}\rangle$ and $\bar{\bf
x}_{0}\in{\mathbb{R}}^{N}$ such that
$\begin{bmatrix}I_{p}&0\end{bmatrix}\bar{A}^{t}{\bf
x}_{0}=\begin{bmatrix}I_{p}&0\end{bmatrix}A^{t}{\bf x}(0)$ for every $t\geq
0$. This is equivalent to saying that $\begin{bmatrix}{\bf x}(0)\cr{\bf
x}_{0}\end{bmatrix}$, which does not belong to $\langle{\bf 1}_{2N}\rangle$,
is not observable for the pair $(\Delta,\Gamma_{p})$.
Conversely, suppose that there exists an unobservable state of the pair
$(\Delta,\Gamma_{p})$, ${\bf x}\not\in\langle{\bf 1}_{2N}\rangle$. Since the
only eigenvectors of $\Delta$ corresponding to the unitary eigenvalue and
belonging to the unobservable subspace are those in $\langle{\bf
1}_{2N}\rangle$, this implies that there exists an eigenvector ${\bf
v}=\begin{bmatrix}{\bf v}_{1}\cr{\bf v}_{2}\end{bmatrix}\not\in\langle{\bf
1}_{2N}\rangle$ of $\Delta$ corresponding to some $\lambda\neq 1$ and
satisfying

$\begin{bmatrix}I_{p}&0\end{bmatrix}{\bf
v}_{1}=\begin{bmatrix}I_{p}&0\end{bmatrix}{\bf v}_{2}.$

Note that Assumption 3 ensures that both ${\bf v}_{1}$ and ${\bf v}_{2}$ are
nonzero vectors. Since ${\bf v}_{1}\not\in\langle{\bf 1}_{n}\rangle$, if
$\lambda$ is real then we have found a state that contradicts discernibility
from the observation of the first $p$ agents. If $\lambda$ is complex then we
can simply use the real part of ${\bf v}_{1}$ to disprove discernibility from
the observation of the first $p$ agents.
ii) $\Leftrightarrow$ iii) Condition ii) is easily seen to be equivalent to
the following condition, expressed in terms of PBH observabilty matrix: if
there exist $\lambda\in{\mathbb{C}}$ and $\begin{bmatrix}{\bf v}\cr\bar{\bf
v}\end{bmatrix}\neq 0$ such that

$\begin{bmatrix}\lambda I_{N}-A&0\cr 0&\lambda I_{N}-\bar{A}_{hr}\cr I_{p}\ \
\ 0&-I_{p}\ \ \ 0\end{bmatrix}\begin{bmatrix}{\bf v}\cr\bar{\bf
v}\end{bmatrix}=0,$ (31)

then $\lambda=1$ and $\begin{bmatrix}{\bf v}\cr\bar{\bf
v}\end{bmatrix}\in\langle 1_{2N}\rangle$. Clearly any such $\lambda$ must be
in $\sigma(\Delta)$. On the other hand, if $\lambda$ would not be a common
eigenvalue of $A$ and $\bar{A}_{hr}$ then either ${\bf v}$ or $\bar{\bf v}$
would be zero and this would mean that either
$(A,\begin{bmatrix}I_{p}&0\end{bmatrix})$ or
$(\bar{A}_{hr},\begin{bmatrix}I_{p}&0\end{bmatrix})$ are not observable. This
would contradict Assumption 3. Therefore we have proved that ii) is equivalent
to iii).

iii) $\Leftrightarrow$ iv) Obvious. ∎

######  Remark 10.

If the networks (2) and (9) are discernible from the observation of the first
$p$ agents, they are discernible. If not, a state ${\bf x}\not\in\langle{\bf
1}_{N}\rangle$ could be found such that $\bar{A}_{hr}^{t}{\bf x}=A^{t}{\bf x}$
for every $t\geq 0$, and hence a fortiori
$\begin{bmatrix}I_{p}&0\end{bmatrix}\bar{A}_{hr}^{t}{\bf
x}=\begin{bmatrix}I_{p}&0\end{bmatrix}A^{t}{\bf x}$ for every $t\geq 0$. This
implies that a necessary condition for discernibility from the observation of
the first $p$ agents is that all the nonunitary eigenvalues of $A$ and
$\bar{A}_{hr}$ have unitary geometric multiplicity.

###  V-A How to detect and identify an edge disconnection when the states of
the first $p$ agents are available

Also in this case we may detect an edge disconnection by making use of the
measurements of the states of the first $p$ agents. Since the pair
$(A,\begin{bmatrix}I_{p}&0\end{bmatrix})$ is observable, let $L$ be a matrix
in ${\mathbb{R}}^{N\times p}$ such that
$A+L\begin{bmatrix}I_{p}&0\end{bmatrix}$ is nilpotent. We can construct the
closed-loop dead-beat observer of the state of the multi-agent system [24] as

$\hat{\bf x}(t+1)=A\hat{\bf x}(t)-L[{\bf
y}(t)-\begin{bmatrix}I_{p}&0\end{bmatrix}\hat{\bf x}(t)].$ (32)

Clearly, after a finite number of steps  $\tau_{0}$333By exploiting the
observability of the pair $(A,\begin{bmatrix}I_{p}&0\end{bmatrix})$ and
Rosenbrock’s theorem, we can claim that the minimum $\tau_{0}$ ranges in the
interval $\left[\lceil\frac{N}{p}\rceil,N-p+1\right]$. that depends on the
nilpotency index of $A+L\begin{bmatrix}I_{p}&0\end{bmatrix}$, we have
$\hat{\bf x}(t)={\bf x}(t)$, and hence the residual signal

${\bf r}(t)=\begin{bmatrix}I_{p}&0\end{bmatrix}\hat{\bf x}(t)-{\bf
y}(t)=\begin{bmatrix}I_{p}&0\end{bmatrix}[\hat{\bf x}(t)-{\bf x}(t)],$

is identically zero from $t=\tau_{0}$ onward until a fault occurs. Now suppose
that at $t=\tau\geq\tau_{0}$ the disconnection of the edge $(r,h)$ takes
place444In the transient phase, until the estimation error goes to zero, the
residual signal may be not zero. As a result it is not possible to detect an
edge disconnection in a reliable way. This is the reason why a dead-beat
observer is preferable over an asymptotic observer, since this transient phase
lasts a finite number of time instants., and hence the multi-agent state
updates according to (9). We want to show that, unless the multi-agent system
has already reached consensus, under Assumptions 1, 2 and 3 and any of the
equivalent conditions of Proposition 9 the residual signal will necessarily
become nonzero at some time instant $t>\tau$.
To this goal it is sufficient to show that for the system obtained by putting
together (9) and (32), namely

$\displaystyle\\!\\!\begin{bmatrix}\hat{\bf x}(t+1)\cr{\bf
x}(t+1)\end{bmatrix}\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\begin{bmatrix}A+L\begin{bmatrix}I_{p}&0\end{bmatrix}&-L\begin{bmatrix}I_{p}&0\end{bmatrix}\cr
0&\bar{A}_{hr}\end{bmatrix}\begin{bmatrix}\hat{\bf x}(t)\cr{\bf
x}(t)\end{bmatrix}$ (33) $\displaystyle{\bf r}(t)\\!\\!$ $\displaystyle=$
$\displaystyle\\!\\!\begin{bmatrix}\begin{bmatrix}I_{p}&0\end{bmatrix}&\begin{bmatrix}-I_{p}&0\end{bmatrix}\end{bmatrix}\begin{bmatrix}\hat{\bf
x}(t)\cr{\bf x}(t)\end{bmatrix}$ (34)

the only unobservable states are those in $\langle{\bf 1}_{2N}\rangle.$
Consider the PBH observability matrix

$\begin{bmatrix}\lambda
I_{N}-A-L\begin{bmatrix}I_{p}&0\end{bmatrix}&L\begin{bmatrix}I_{p}&0\end{bmatrix}\cr
0&\lambda
I_{N}-\bar{A}_{hr}\cr\hline\cr\begin{bmatrix}I_{p}&0\end{bmatrix}&\begin{bmatrix}-I_{p}&0\end{bmatrix}\end{bmatrix}.$
(35)

By resorting to elementary operations on the rows of the matrix, it is easily
seen that the previous matrix is of full column rank for
$\lambda\in{\mathbb{C}}$ if and only if the PBH observability matrix

$\begin{bmatrix}\lambda I_{N}-A&0\cr 0&\lambda
I_{N}-\bar{A}_{hr}\cr\hline\cr\begin{bmatrix}I_{p}&0\end{bmatrix}&\begin{bmatrix}-I_{p}&0\end{bmatrix}\end{bmatrix}$
(36)

is of full column rank for that $\lambda$. Moreover when both PBH matrices
have not full column rank, they have the same kernel. By the assumption that
(2) and (9) are discernible from the observation of the first $p$ agents it
follows (see condition iii) of Proposition 9) that (36) is of full column rank
for every $\lambda\neq 1$ and for $\lambda=1$ its kernel is $\langle{\bf
1}_{2N}\rangle.$ Therefore, the only unobservable states of the overall system
are those in $\langle{\bf 1}_{2N}\rangle$, and this implies that the residual
${\bf r}(t)$ cannot remain zero after an edge disconnection.

We now want to show that, under suitable assumptions, one can deduce from the
residual the exact information about which edge got disconnected.

######  Proposition 11.

Consider the networks (2) and (9), this latter obtained from the former after
the disconnection of the edge $(r,h)$ at some time  $t=\tau\geq\tau_{0}$.
Assume that for every edge $(j,i),\ i,j\in[1,N],j\neq i$, (and not only for
$(j,i)=(r,h)$)
(i) the faulty network obtained by disconnecting $(j,i)$ is strongly connected
and discernible from the original network based on the observation of the
first $p$ states,
(ii)  Assumption 3 holds and hence $(A,\begin{bmatrix}I_{p}&0\end{bmatrix})$
and $(\bar{A}_{ij},\begin{bmatrix}I_{p}&0\end{bmatrix})$ are observable, and
(iii)

$\sigma(\bar{A}_{hr})\cap\sigma(\bar{A}_{ij})=\\{1\\}.$ (37)

Then, unless ${\bf x}(\tau)\in\langle{\bf 1}_{N}\rangle$, namely the network
has already reached consensus, it is possible to identify from the residual
signal ${\bf r}(t),t\geq\tau$, generated by (34), the edge $(r,h)$ that got
disconnected.

###### Proof.

To prove that the previous observer-based residual generator produces distinct
residual sequences corresponding to different faulty systems (provided that
${\bf x}(\tau)$, the state of the multi-agent system at the time of edge
disconnection, is not in the equilibrium, yet, namely it is not a multiple of
${\bf 1}_{N}$), it is sufficient to prove that if $(r,h)\neq(j,i)$ then the
two systems

$\left({\mathbb{A}}_{hr},\begin{bmatrix}I_{p}&0_{p\times(N-p)}&-I_{p}&0_{p\times(N-p)}\end{bmatrix}\right)$
$\left({\mathbb{A}}_{ij},\begin{bmatrix}I_{p}&0_{p\times(N-p)}&-I_{p}&0_{p\times(N-p)}\end{bmatrix}\right),$

with

${\mathbb{A}}_{hr}:=\begin{bmatrix}A_{L}&-L\begin{bmatrix}I_{p}&0_{p\times(N-p)}\end{bmatrix}\cr
0&{\bar{A}}_{hr}\end{bmatrix},$
${\mathbb{A}}_{ij}:=\begin{bmatrix}A_{L}&-L\begin{bmatrix}I_{p}&0_{p\times(N-p)}\end{bmatrix}\cr
0&{\bar{A}}_{ij}\end{bmatrix},$

generate distinct residual trajectories, provided that neither of them has
already reached the equilibrium  at the time the disconnection occurs. This
amounts to saying that the only unobservable states of the system

$\left(\begin{bmatrix}{\mathbb{A}}_{hr}&\vline&0\cr\hline\cr
0&\vline&{\mathbb{A}}_{ij}\end{bmatrix},\begin{bmatrix}I_{p}&0&-I_{p}&0&\vline\
-I_{p}&0&I_{p}&0\end{bmatrix}\right),$ (38)

taking the form $\begin{bmatrix}{\bf v}_{hr}\cr{\bf v}_{hr}\cr{\bf
v}_{ij}\cr{\bf v}_{ij}\end{bmatrix}$ are those belonging to
$\langle\begin{bmatrix}{\bf 1}_{2N}\cr 0\end{bmatrix},\begin{bmatrix}0\cr{\bf
1}_{2N}\end{bmatrix}\rangle.$
By making use of the PBH observability matrix:

$\begin{bmatrix}\lambda I_{2N}-{\mathbb{A}}_{hr}&0\cr 0&\lambda
I_{2N}-{\mathbb{A}}_{ij}\cr\hline\cr[I_{p}\ 0\ -I_{p}\ 0]&[-I_{p}\ 0\ I_{p}\
0]\end{bmatrix}$ (39)

it is easily seen that a vector with the previous block structure belongs to
the kernel of (39) for $\lambda=1$ if and only if ${\bf v}_{hr}$ is a common
eigenvector (corresponding to $\lambda=1$) of $A$ and $\bar{A}_{hr}$ and ${\bf
v}_{ij}$ is a common eigenvector (corresponding to $\lambda=1$) of $A$ and
$\bar{A}_{ij}$. Therefore the overall vector belongs to
$\langle\begin{bmatrix}{\bf 1}_{2N}\cr 0\end{bmatrix},\begin{bmatrix}0\cr{\bf
1}_{2N}\end{bmatrix}\rangle.$
On the other hand, if $\lambda\in\sigma(\bar{A}_{hr}),\lambda\neq 1,$ then it
is easy to see that under the hypothesis (37) and by the observability of
$(A_{L},\begin{bmatrix}I_{p}&0\end{bmatrix})$, we have
$\lambda\not\in\sigma({\mathbb{A}}_{ij})$, and therefore it must be ${\bf
v}_{ij}=0$. But this means that $\begin{bmatrix}{\bf v}_{hr}\cr{\bf
v}_{hr}\end{bmatrix}$ should belong to the kernel of (35), but for
$\lambda\neq 1$ the matrix (35) is of full column rank. Analogous reasoning
holds if $\lambda\in\sigma(\bar{A}_{ij}),\lambda\neq 1.$ ∎

##  VI An illustrative example

We now apply the previous results to the case of a network of $7$ agents,
whose communication graph is depicted in Figure 2 assuming that each agent is
described as a discrete-time integrator and runs the algorithm (1) with
$\kappa=0.25$. All the weights of the graph are equal to $1$. The set of the
observed nodes is $\\{1,2,3\\}$, and we apply the strategy described in
Section V. The resulting system matrix is

$A=\begin{bmatrix}0.75&0&0&0.25&0&0&0\\\ 0&0.75&0&0&0.25&0&0\\\
0&0&0.75&0&0&0.25&0\\\ 0&0&0&0.75&0&0&0.25\\\ 0.25&0&0&0&0.5&0.25&0\\\
0&0.25&0&0&0&0.75&0\\\ 0&0&0.25&0&0.25&0&0.5\\\ \end{bmatrix}$ (40)

and it is easily verified that the pair
$(A,\begin{bmatrix}I_{3}&0\end{bmatrix})$ is observable. A dead beat state
observer has been derived following three steps: (1) the pair $(A,[I_{3}\
0])$, with $A$ as in (40), is reduced to multi-output observability canonical
form $(A_{o},H_{o})$ by resorting to a suitable transformation matrix $T$ (see
e.g. [2]). (2) The matrix $L_{o}$ that makes $A_{o}+L_{o}H_{o}$ nilpotent with
minimum possible nilpotency index is trivially obtained by imposing that
$A_{o}+L_{o}H_{o}$ is block-diagonal, with diagonal blocks that are (single-
output) observability canonical forms with zero coefficients in the last
column. (3) The desired observer gain matrix is then $L=T^{-1}L_{o}$.
It is worth noticing that there is a transient phase, due to the presence of
an estimation error, consisting of $3$ time steps, after which the residual
becomes zero (i.e., $\tau_{0}=3$).

Figure 2: A sketch of the graph of the illustrative example of Section VI.

Two simulation results are plotted in Figure 3. The three curves represent, in
both cases, the multi-agent system outputs, namely the states of the first
three agents. On the other hand, instead of reporting the values of the
residual ${\bf r}(t)$, we have chosen to represent with black circles the
_detection signal_ $d(t)$ which is unitary if ${\bf r}(t)\neq 0$ and $0$ if
${\bf r}(t)=0$. In both simulations we have disconnected the edge $(6,5)$ in
the interval $[10,14]$, and the edge $(5,7)$ in the interval $[20,24]$. It is
worth noticing that $A$ and $\bar{A}_{7,5}$ do not have common eigenvalues
(apart from $1$), so the original and the faulty networks are discernible,
while $A$ and $\bar{A}_{5,6}$ have $\lambda=0.5$ and the corresponding
eigenvector in common, so this case fails to satisfy condition (v) of
Proposition 3 and, in turn, condition (iv) of Proposition 9 and condition (i)
of Proposition 11.

In the first simulation, corresponding to the upper plot of Figure 3, it is
assumed ${\bf x}(0)=[10\ -1\ 1\ 8\ 5\ 5\ 12]^{\top}$ and $\hat{\bf x}(0)=0.$
After an initial transient of 3 steps, the estimated state $\hat{\bf x}(3)$ is
equal to the real state ${\bf x}(3)$ (while ${\bf x}(t)\neq\hat{\bf x}(t)$ for
$t<3$, and this is the reason why the estimation signal is nonzero), and the
detection signal is zero up to $t=11$ when the disconnection of the edge
$(6,5)$ is detected. Then the link is restored, and the disconnection of the
edge $(5,7)$ is detected at time $t=22$.

The second simulation shows what it may happen if the conditions of
Propositions 9 and Proposition 11 are not met. It is assumed ${\bf x}(0)=[-5\
5\ 5\ -5\ -5\ 5\ -5]^{\top}$ and $\hat{\bf x}(0)=0$. After an initial
transient phase, $\hat{\bf x}(3)={\bf x}(3)$, however, the detection signal is
zero up to time $t=22$, when the second edge disconnection is detected, and
this shows that the first link disconnection remains undetected because of the
special structure of the graph topology and the specific value of the system
state at the time of the disconnection.

Figure 3: Simulation Results: output evolution and detection signal of system
(40) under different initial conditions. In the bottom plot, the first link
disconnection cannot be detected from system evolution.

##  VII Conclusions

In this paper we have addressed the problem of detecting and identifying an
edge disconnection in a discrete-time consensus network, by assuming that the
link failure does not compromise the strong connectedness of the underlying
directed communication network. The cases when the states of all the agents
are available and when only a proper subset of them is available are both
considered, and sufficient conditions ensuring that the problem is solvable
are provided. An example concludes the paper, illustrating both the case when
detection from the measurement of the states of 3 of the 7 agents is possible
and the case when it is not.

It is worth noticing that we have solved the discernibility problem from the
first $p$ states by resorting to a full order dead-beat observer, but due to
the structure of the state to output matrix the use of a reduced-order dead-
beat observer would be straightforward, and it would ensure the same
performance in terms of nilpotency index.

Future research efforts will aim at finding an algorithm to efficiently
identify the disconnected edge when only $p$ of the $N$ states are available,
as it has been done here in the case when all the agents are measured. Also,
the case of noisy measurements and/or modelling errors needs to be addressed.

As mentioned in the Introduction, distributed fault detection and
identification algorithms have been proposed by assuming that faults are
additive. It would be of extreme interest to adapt such algorithms to the
specific case when the fault is an edge disconnection, without losing the
information about the specific nature and structure of the fault.

## Appendix: A technical lemma

######  Lemma 12.

Consider the positive irreducible matrix
$A=I_{N}-\kappa{\mathcal{L}}\in{\mathbb{R}}^{N\times N}$ and let $J_{A}$ be
its (real) Jordan form. Let $T\in{\mathbb{R}}^{N\times N}$ be the nonsingular
transformation matrix such that

$T^{-1}AT=J_{A}=\begin{bmatrix}1&0\cr
0&\tilde{J}_{A}\end{bmatrix}=\begin{bmatrix}1&0&\dots&0\cr
0&J_{2}&\dots&0\cr\vdots&&\ddots&\vdots\cr 0&0&\dots&J_{n}\end{bmatrix},$

where $J_{i}$ is a Jordan block corresponding to $\lambda_{i}$ and
$\lambda_{i}\neq 1$ for every $i\in[2,n]$. Define $W$ as in (22), namely as

$W:=\begin{bmatrix}{\bf 0}_{N-1}&I_{N-1}\end{bmatrix}T^{-1}.$

Then for every pair of distinct nodes $h,i\in{\mathcal{V}}=[1,N],i\neq h,$

$\langle W{\bf e}_{i}\rangle\neq\langle W{\bf e}_{h}\rangle.$

###### Proof.

Suppose, by contradiction, that there exist $h,i\in{\mathcal{V}}=[1,N],i\neq
h,$ and nonzero $\alpha,\beta\in{\mathbb{R}}$, such that

$0=W[\alpha{\bf e}_{i}+\beta{\bf e}_{h}]=\begin{bmatrix}{\bf
0}_{N-1}&I_{N-1}\end{bmatrix}T^{-1}[\alpha{\bf e}_{i}+\beta{\bf e}_{h}].$

Since $T$ is a nonsingular matrix, there exists a vector ${\bf c}\neq 0$ such
that $\alpha{\bf e}_{i}+\beta{\bf e}_{h}=T{\bf c}.$ By replacing this
expression in the previous identity we obtain

$0=\begin{bmatrix}{\bf 0}_{N-1}&I_{N-1}\end{bmatrix}T^{-1}T{\bf
c}=\begin{bmatrix}{\bf 0}_{N-1}&I_{N-1}\end{bmatrix}{\bf c}.$

This amounts to saying that ${\bf c}=\gamma{\bf e}_{1}$ for some $\gamma\neq
0$ and

$\alpha{\bf e}_{i}+\beta{\bf e}_{h}=T\gamma{\bf e}_{1}=\gamma{\bf 1}_{N}.$

But this is clearly not possible, since the vector on the left hand side has
two nonzero entries, while the one on the right hand side has all nonzero (and
identical) entries. ∎

## References

  * [1] P. Antsaklis and J. Baillieul.  Special issue on technology of networked control systems.  Proc. IEEE, 95, no. 1:5–8, 2007.
  * [2] P. J. Antsaklis and A. N. Michel.  Linear Systems.  Birkhäuser, Boston, MA, 2006.
  * [3] J. Baillieul and P.J. Antsaklis.  Control and communication challenges in networked real-time systems.  Proc. IEEE, 95(1):9–28, 2007.
  * [4] G. Battistelli and P. Tesi.  Detecting topology variations in networks of linear dynamical systems.  IEEE Trans. Control Network Systems, 5, no. 3:1287–1299, 2018.
  * [5] A. Berman and R.J. Plemmons.  Nonnegative matrices in the mathematical sciences.  Academic Press, New York, 1979.
  * [6] F. Bullo, J. Cortés, and S. Martínez.  Distributed Control of Robotic Networks.  Princeton University Press, 2009.
  * [7] D. M. Cardoso, C. Delorme, and P. Rama.  Laplacian eigenvectors and eigenvalues and almost equitable partitions.  European J. Combinatorics, 28(3):665–673, 2007.
  * [8] C.-Y. Chong and S.P. Kumar.  Sensor networks: evolution, opportunities, and challenges.  Proc. IEEE, 91(8):1247–1256, 2003.
  * [9] J. Costanzo, D. Materassi, and B. Sinopoli.  Using Viterbi and Kalman to detect topological changes in dynamic networks.  In Proc. 2017 American Control Conference, pages 5410–5415. IEEE, 2017.
  * [10] C.G. Cullen.  Matrices and Linear Transformations.  Dover Publications; 2nd edition, 1990.
  * [11] M.R. Davoodi, K. Khorasani, H.A. Talebi, and H.R. Momeni.  Distributed fault detection and isolation filter design for a network of heterogeneous multiagent systems.  IEEE Trans. Control Systems Technology, 22(3):1061–1069, 2014.
  * [12] R. Dhal, J. A. Torres, and S. Roy.  Link-failure detection in network synchronization processes.  In Proc. 2013 IEEE Global Conference on Signal and Information Processing, pages 779–782,2013.
  * [13] R. Dhal, J. Abad Torres, and S. Roy.  Detecting link failures in complex network processes using remote monitoring.  Physica A: Statistical Mechanics and its Applications, 437:36–54, 2015.
  * [14] M. Egerstedt, S. Martini, M. Cao, K. Camlibel, and A. Bicchi.  Interacting with networks: How does structure relate to controllability in single-leader, consensus networks?  IEEE Control Systems Magazine, 32(4):66–73, 2012.
  * [15] L. Farina and S. Rinaldi.  Positive linear systems: theory and applications.  Wiley-Interscience, Series on Pure and Applied Mathematics, New York, 2000\.
  * [16] M. Fiedler.  Algebraic connectivity of graphs.  Czechoslovak Mathematical J., 23:298–305, 1973.
  * [17] H. Gharavi and S.P. Kumar.  Special issue on sensor networks and applications.  Proc. IEEE, 91(8):1151–1153, 2003.
  * [18] R.A. Horn and C.R. Johnson.  Matrix Analysis.  Cambridge Univ. Press, Cambridge (GB), 1985.
  * [19] N.E. Leonard, D.A. Paley, F. Lekien, R. Sepulchre, D.M. Fratantoni, and R.E. Davis.  Collective motion, sensor networks, and ocean sampling.  Proc. IEEE, 95(1):48–74, 2007.
  * [20] Z. Li and J. Chen.  Robust consensus of linear feedback protocols over uncertain network graphs.  IEEE Trans. Automatic Control, 62(8):4251–4258, 2017.
  * [21] S. Miah, B. Nguyen, A. Bourque, and D. Spinello.  Nonuniform coverage control with stochastic intermittent communication.  IEEE Trans. Automatic Control, 60(7):1981–1986, 2014.
  * [22] R. Olfati-Saber, J.A. Fax, and R.M. Murray.  Consensus and cooperation in networked multi-agent systems.  Proc. IEEE, 95, no. 1:215–233, 2007.
  * [23] R. Olfati-Saber and R.M. Murray.  Consensus problems in networks of agents with switching topology and time-delays.  IEEE Trans. Automatic Control, 49, no. 9:1520 –1533, 2004.
  * [24] J. O’Reilly.  Observers for Linear Systems.  Academic Press, 1983.
  * [25] P. K. Pandey, B. Adhikari, and S. Chakraborty.  A diffusion protocol for detection of link failure and utilization of resources in multi-agent systems.  IEEE Trans. Network Science and Engineering, 2019.
  * [26] F. Pasqualetti, R. Carli, A. Bicchi, and F. Bullo.  Distributed estimation and detection under local information.  In Proc. 2nd IFAC Workshop on Distributed Estimation and Control in Networked Systems, pages 263–268, Annecy, France, 2010.
  * [27] F. Pasqualetti, F. Dorfler, and F. Bullo.  Attack detection and identification in cyber-physical systems.  IEEE Trans. Automatic Control, 58, no. 11:2715–2729, 2013.
  * [28] F. Pasqualetti, F. Dorfler, and F. Bullo.  Control-theoretic methods for cyberphysical security: Geometric principles for optimal cross-layer resilient control systems.  IEEE Control Systems Magazine, 35, no. 1:110–127, 2015.
  * [29] D. Patil, P. Tesi, and S. Trenn.  Indiscernible topological variations in dae networks.  Automatica, 101:280–289, 2019.
  * [30] J. Qin, Q. Ma, Y. Shi, and L. Wang.  Recent advances in consensus of multi-agent systems: A brief survey.  IEEE Trans. Industr. Electronics, 64(6):4972–4983, 2017.
  * [31] M. Rahimian, A. Ajorlou, and A. Aghdam.  Detectability of multiple link failures in multi-agent systems under the agreement protocol.  In Proc. 2012 IEEE Conf. Decision Control, pages 118–123, Maui, HI, USA, 2012.
  * [32] M. A. Rahimian and V.M. Preciado.  Failure detection and isolation in integrator networks.  In Proc. 2015 American Control Conference, pages 677–682, 2015\.
  * [33] W. Ren, R. W. Beard, and E. M. Atkins.  A survey of consensus problems in multi-agent coordination, 2005.  In Proc. 2005 American Control Conference, pages 1859–1864, 2005\.
  * [34] W. Ren and R.W. Beard.  Distributed Consensus in Multi-vehicle Cooperative Control: Theory And Applications.  Springer, 2007.
  * [35] W. Ren, R.W. Beard, and E.M. Atkins.  Information consensus in multivehicle cooperative control.  IEEE Control Systems Magazine, 27 (2):71–82, 2007.
  * [36] W. Ren and Y. Cao.  Distributed coordination of multi-agent networks: emergent problems, models, and issues.  Springer Science & Business Media, 2010.
  * [37] E.D. Sontag.  Mathematical Control Theory. Deterministic Finite Dimensional Systems. Springer-Verlag, New York, 2nd edition, 1998.
  * [38] A. Teixeira, I. Shames, H. Sandberg, and K.H. Johansson.  Distributed fault detection and isolation resilient to network model uncertainties.  IEEE Trans. Cybernetics, 44(11):2024–2037, 2014.
  * [39] J. A Torres, R. Dhal, and S. Roy.  Detecting link failures in complex network processes using remote monitoring.  In Proc. 2015 American Control Conference, pages 189–194, 2015.
  * [40] M.E. Valcher.  Consensus in the presence of communication faults.  In Proc. 2019 European Control Conf., pages 1062–1067, Napoli, Italy, 2019.
  * [41] M.E. Valcher and G. Parlangeli.  On the effects of communication failures in a multi-agent consensus network.  In Proc. 23rd International Conference on System Theory, Control and Computing, pages 709–720, Sinaia, Romania, 2019.
  * [42] W.C. Wah.  Synchronization in complex networks of nonlinear dynamical systems.  World Scientific, 2007.
  * [43] M. Xue.  Designing local inputs to identify link failures in a diffusive network: A graph perspective.  In Proc. 58th Conference on Decision and Control, pages 5525–55230, Nice, France, 2019.
  * [44] K. You, Z. Li, and L. Xie.  Consensus condition for linear multi-agent systems over randomly switching topologies.  Automatica, 49(10):3125–3132, 2013.
  * [45] F. Zhao and L. Guibas.  Wireless sensor networks: An information processing approach.  Morgan Kaufmann, 2004.