# Resilient Multi-Dimensional Consensus in Adversarial Environment

Jiaqi Yan, Xiuxian Li, Yilin Mo†, and Changyun Wen ${\dagger}$: Corresponding
author. J. Yan, X. Li and C. Wen are with the School of Electrical and
Electronic Engineering, Nanyang Technological University, Singapore. Emails:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Y. Mo is with the
Department of Automation and BNRist, Tsinghua University, China. Email:
<EMAIL_ADDRESS>
###### Abstract

This paper considers the multi-dimensional consensus in networked systems,
where some of the agents might be misbehaving (or faulty). Despite the
influence of these misbehaviors, the healthy agents aim to reach an agreement
within the convex hull of their initial states. Towards this end, this paper
develops a resilient consensus algorithm, where each healthy agent sorts its
received values on one dimension, computes two “middle points” based on the
sorted values, and moves its state toward these middle points. We further show
that the computation of middle points can be efficiently achieved by linear
programming. Compared with the existing works, this approach has lower
computational complexity. Assuming that the number of malicious agents is
upper bounded, sufficient conditions on the network topology are then
presented to guarantee the achievement of resilient consensus. Some numerical
examples are finally provided to verify the theoretical results.

###### Index Terms:

Resilient algorithms, Cyber-security, Robust graphs, Multi-dimensional
systems.

##  I Introduction

The past decades have witnessed remarkable research interest in networked
systems. One of its fundamental focuses would be the canonical consensus
problem, which has been widely investigated in various applications including
formation control of mobile robots [1, 2, 3, 4], data fusion in sensor network
[5, 6], etc. Given a set of autonomous agents (such as vehicles, sensors),
such problem seeks a distributed protocol that the agents can utilize to reach
a common decision/agreement on the average of their initial opinions.

In these years, considerable attention has been paid to the development of
consensus algorithms [4, 1, 7]. Such protocols are normally based on the
hypothesis that every computing agent is trustworthy and cooperate to follow
the algorithms throughout their execution. Nevertheless, as the scale of the
network increases, it becomes more difficult to secure every agent. On one
hand, autonomous agents will communicate with each other to make control
decisions. This opens the system to malicious attacks [8]. On the other hand,
some agents may not be willing to follow the given rules if they weigh their
private interests more than the public ones. It is reported that such
misbehaving agents can either dictate the final consensus value, or prevent
the network from reaching an agreement [9]. Given the wide applications of
consensus algorithm in safety-critical systems, the need for resilient
protocols has received much research interest.

In fact, the issue related to resilient consensus has been addressed in the
literature over decades. Most approaches adopt the idea of simply ignoring the
suspicious values. For example, Dolev et al. consider the scenario in a
complete network, where an approximate agreement is desired in the presence of
misbehaving agents [10]. In order to overrule the effects of malicious nodes,
a secure updating strategy is proposed. The essential idea is that each normal
agent discards the most extreme values in its neighborhood and updates the
state based on the remaining ones at any time. Such protocol has then inspired
a family of algorithms, namely Mean-Subsequence Reduced (MSR) algorithm [11,
12, 13]. In a recent work [14], Leblanc et al. modify MSR and present the
Weighted Mean-Subsequence-Reduced (W-MSR) algorithm. Different from that in
MSR, a normal agent only removes the extreme values that are strictly larger
or smaller than its current state. This mechanism results in its own state
being kept in the update law and turns out to keep more useful information
than MSR. Furthermore, instead of the complete graphs, they analyze W-MSR in
more general topologies. A novel property named network robustness is hereby
introduced, which characterizes the resilience of W-MSR in terms of the graph
structure. Later, Dibaji et al. generalize the above results to second-order
systems [15].

The aforementioned strategies ensure the resilient consensus in uni-
dimensional systems where agents’ states are assumed to be scalars. The final
agreement is guaranteed to be within the range limited by the minimum and
maximum values of normal nodes’ initial states. The implication on scalar
variables, however, produces crucial limitations in various practical
applications such as vehicle formation control on a 2D-plane. A naive way to
generalize the results on a scalar system to a multi-dimensional system is to
apply MSR or W-MSR to each entry of the state vectors. The region that the
final value converges to can be immediately identified as a multi-dimensional
“box”. Particularly, each edge of this “box” is limited by the minimum and
maximum values of benign agents’ initial state in one dimension. A question
thus arises naturally: is this result too conservative? Or are there any
alternatives that can provide better convergence results?

To answer these questions, resilient consensus in multi-dimensional spaces has
been investigated, aiming at achieving a more accurate agreement within the
convex hull formed by healthy agents’ initial states. In order to ensure
system security, in every iteration, the normal node seeks a resilient convex
combination, referring to be a point within the convex hull of its benign
neighboring states. Some works achieve this through Tverberg points (see [16,
17] for examples). While the results therein are elegant, the calculation of
Tverberg points is rather costly and almost impossible in many cases ( [18]).
The existing works unfortunately do not provide an efficient way to do it,
which leads to a major concern on applying Tverberg points to facilitate
resilient vector consensus. This work, thereby, follows another line of
research. The main contributions are summarized below:

1) Instead of Tverberg points, we design the resilient consensus algorithm
based on the intersection of convex hulls. More specifically, the normal
agents sort the received values at one dimension each time. Then every of them
computes two “middle points” based on the sorted values, and moves its states
towards an average of these points. By proving that the middle points achieve
resilient convex combination, we conclude the faulty nodes have limited
influence on system performance.

2) An explicit approach for the computation of middle points is also given,
which can be implemented by linear programming. Note that this calculation
only requires a subset of the neighboring states. Since the cardinality of the
subset is fixed, the computational cost is independent of the network
complexity. Compared with most of the existing works, the proposed strategy is
achieved with a lower computational complexity.

3) This paper is interested in the requirement on networks to achieve the
resilient consensus and hereby focuses on the more general incomplete graphs.
Sufficient topological conditions are established to facilitate the resilient
agreement. Since the idea behind canonical consensus serves as a fundamental
principle in many distributed coordination settings, this method provides a
powerful tool in handling misfunctioning components in multi-dimensional
networked systems.

Some preliminaries results are contained in our former work [19]. While both
works are inspired by Helly’s Theorem and achieve the resilient convex
combination through the intersection of convex hulls, the major difference
between it and this paper lies in the design of algorithms. Particularly, [19]
requires each normal agent to calculate a safe kernel at every step. After
that, it exploits the vertices of the kernel for updates. Although correct,
the major concern of applying [19] is the requirement of high computational
complexity. More specifically, existing approaches for computing the safe
kernel are usually $\\#p$-hard ( [27]). Also, since this computation depends
on every state in the neighborhood, the algorithm may fail in a complex
network where some agents have abundant neighbors. Finally, given the safe
kernel, calculating its vertices is also not an easy task ( [20]). Compared
with it, the algorithm proposed in this paper is of more lightweight since,
instead of the total safe kernel, only two “middle points” in it are going to
be calculated. As previously mentioned, this step can be achieved through a
linear programming with a lower computational cost independent of the network
complexity. Note by doing so, the vertex enumeration problem for a polytope is
also avoided. Finally, due to the page limitation of conference proceedings,
the proofs of the results in [19] are unavailable. In this paper, we present
the full proofs of lemmas and theorems.

The rest of this paper is organized as follows. After introducing some
technical preliminaries in Section II, Section III formulates the problem of
interest. To achieve the resilient consensus in multi-dimensional spaces, a
“middle points” based algorithm is detailed in Section IV, where an approach
for the computation of middle points is also given. The efficiency of this
algorithm is theoretically analyzed in Section V. Section VI further discusses
the ideas and implementations of the proposed strategy. We then test the main
results through numerical examples in Section VII. Finally, Section VIII
concludes the paper.

Notations:

For a vector $a$, $a_{i}$ denotes its $i$-th component. For a point set
$\mathcal{S}\subset\mathbb{R}^{d}$, let $\operatorname*{Conv}(\mathcal{S})$ be
its convex hull, namely the set of all convex combinations of the points in
$\mathcal{S}$. Furthermore, given two positive numbers $x$ and $y$,
$x\operatorname*{mod}y$ represents the remainder of the Euclidean division of
$x$ by $y$. In this work, $e_{p}$ denotes the $p$-th canonical basis vector in
$\mathbb{R}^{d}$.

##  II Preliminaries

We start by introducing some technical preliminaries, which would be useful in
our further analysis.

Consider the graph $\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$, where
$\mathcal{V}$ is the set of agents, and
$\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ is the set of edges. An edge
between agents $i$ and $j$ is denoted by $e_{ij}\in\mathcal{E}$, indicating
these two agents can communicate directly with each other. The neighborhood of
an agent $i\in\mathcal{V}$ is then defined as

$\mathcal{N}_{i}=\\{j\in\mathcal{V}|e_{ij}\in\mathcal{E}\\}.$

As one might imagine, there is a close coupling between the network topology
and maximum number of tolerable faulty agents. For the resilient algorithm
employed in this paper, we characterize its efficiency in terms of network
robustness. It was first introduced in [14] and is formally defined below:

######  Definition 1.

($r$-robustness): A network $\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$ is
said to be $r$-robust, if for any pair of disjoint and nonempty subsets
$\mathcal{V}_{1},\mathcal{V}_{2}\subsetneq\mathcal{V}$, at least one of the
following statements hold:

  1. 1.

There exists an agent in $\mathcal{V}_{1}$, such that it has at least $r$
neighbors outside $\mathcal{V}_{1}$;

  2. 2.

There exists an agent in $\mathcal{V}_{2}$, such that it has at least $r$
neighbors outside $\mathcal{V}_{2}$.

######  Definition 2.

(($r,s$)-robustness): A network $\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$ is
said to be ($r,s$)-robust, if for any pair of disjoint and nonempty subsets
$\mathcal{V}_{1},\mathcal{V}_{2}\subsetneq\mathcal{V}$, at least one of the
following statements holds:

  1. 1.

Any agent in $\mathcal{V}_{1}$ has at least $r$ neighbors outside
$\mathcal{V}_{1}$;

  2. 2.

Any agent in $\mathcal{V}_{2}$ has at least $r$ neighbors outside
$\mathcal{V}_{2}$;

  3. 3.

There are no less than $s$ agents in $\mathcal{V}_{1}\cup\mathcal{V}_{2}$,
such that each of them has at least $r$ neighbors outside the set it belongs
to ($\mathcal{V}_{1}$ or $\mathcal{V}_{2}$).

Intuitively, the network robustness is a connectivity measure for graphs. It
claims that for any two disjoint and nonempty subsets of agents, there are
“many” agents within these sets that have a sufficient number of neighbors
outsides.

##  III Problem Formulation

Consider a group of $N$ agents who cooperate over the undirected graph
$\mathcal{G}=\\{\mathcal{V},\mathcal{E}\\}$. At any time $k\geq 0$, let
$x^{i}(k)\in\mathbb{R}^{d}$ denote the current state of agent $i$. The agents
are said to reach a (distributed) consensus if and only if there exists a
constant $\bar{x}$, such that $\lim_{k\rightarrow\infty}x^{i}(k)=\bar{x}$
holds for every agent $i$. In particular, if
$\bar{x}=1/N\sum_{i=1}^{N}x^{i}(0)$, an average consensus is achieved.

Observe that many practical applications fit into the framework of average
consensus (e.g., [1, 21]). Various strategies have been developed to
facilitate it in the literatures (see [22] and [4] for examples), the details
of which are omitted here due to the space limitation.

###  III-A Resilient consensus problem

It is worth noticing that an implicit assumption for the effectiveness of the
existing approaches is that all agents are reliable throughout the execution,
and cooperate to achieve the desired value. However, as the number of local
agents increases, certain concerns arise that make this assumption to be
violated. As discussed before, the strong dependence of distributed algorithms
on the communication infrastructures creates lots of vulnerabilities for cyber
attacks, where the transmitted information might be manipulated by external
adversaries. Additionally, “non-participant” agent may exist, who deviates
from the normal update rule and sends out self-designed information to its
neighbors for its own benefits. Clearly, such misbehaviors would degrade the
performance of consensus protocols: they can either prevent the benign agents
from reaching a consensus, or manipulate the final agreement to be false. In
fact, as shown in [9], a single “stubborn” agent can cause all agents to agree
on an arbitrary value, by simply keeping this value constant.

These security concerns lead to the study of resilient consensus protocols.
That is, we intend to present a secure strategy to achieve the agreement among
healthy agents while raising its resilience so as to avoid being influenced by
the network misbehaviors too much. By saying “resilient”, we aim to achieve
the following objectives, regardless of the choice of initial states and even
in the adversarial environment:

  1. 1.

_Agreement:_ As $k$ goes to infinity, it holds that $x^{i}(k)=\bar{x}$ with
some $\bar{x}\in\mathbb{R}^{d}$, for any benign agent $i$;

  2. 2.

_Validity:_ At any time and for any benign agent, its state remains in the
convex hull of all benign agents’ initial values.

We elucidate these conditions as below. Firstly, the states of the benign
agents should converge to the same constant value even in the presence of
misbehaving ones. In addition, they are not allowed to leave the convex hull
of their initial states throughout the procedure. It is observed that if $1$D
problem is considered, the validity condition would be equivalent to the
standard one adopted in the existing literatures [10, 11, 12, 13, 14, 15].
That is, the states of benign agents should always remain in the interval
formed by the minimum and maximum of their initial values.

There has been much work proved to be effective in the simple scalar case
(e.g., MSR in [10] and W-MSR in [14]). Therefore, one might consider a naive
way to tackle this problem in vector spaces by simply applying the existing
scalar protocols to each component of the states. Nevertheless, by doing so,
the region that benign agents converge to is only guaranteed as the smallest
hypercube which contains their initial state. The validity condition thus
fails to be ensured. To see this, we present a $2$-dimensional illustration in
Fig. 1, indicating this naive way cannot guarantee the convergence to a point
inside the convex hull of normal agents’ initial states. Therefore, this paper
intends to address this problem and come up with an alternate method
satisfying both Conditions 1) and 2).

Figure 1: A $2$D illustration with agents marked with circles. The location of
the node indicates its initial value. With the direct application of existing
algorithms to each dimension, the final agreement is ensured to be within the
rectangle. However, a better solution satisfying the validity condition of
converging to the green triangle is expected.

###  III-B Attack model

We define $\mathcal{F}$ as the set of malicious/faulty agents. Any agent
$i\in\mathcal{F}$ could either be the adversarial one with the value being
manipulated by the attacker, or the non-participant agent who does not follow
the standard updating rule. On the other hand, $\mathcal{B}$ is the collection
of benign agents who will always follow the predefined updating strategy and
compute the desired function. It is clear that
$\mathcal{B}\cap\mathcal{F}=\varnothing$ and
$\mathcal{B}\cup\mathcal{F}=\mathcal{V}$.

The network misbehaviors could be characterized by the scope of threats:

  1. 1.

($F$-total attack model) There are at most $F$ misbehaving agents in the
network. That is, $|\mathcal{F}|\leq F$.

  2. 2.

($F$-local attack model) There are at most $F$ misbehaving agents in the
neighborhood of any agent. That is, $|\mathcal{F}\cap\mathcal{N}_{i}|\leq F$,
for any agent $i\in\mathcal{V}$.

This paper focuses on the worst-case situation, where no restrictions are
imposed on the transmitted information of agent $i\in\mathcal{F}$. Namely both
adversarial and non-participant agents are allowed to send out arbitrary and
different data to their neighbors. Furthermore, the faulty agents could also
collude among themselves to decide on the deceptive values to be communicated.

In this paper, we impose the following assumption on network topology:

######  Assumption 1.

For any $i\in\mathcal{V}$, it is held that $|\mathcal{N}_{i}|\geq(d+1)F+1$.

##  IV A Resilient Multi-dimensional Consensus Strategy

To simplify notations, the following definitions are given beforehand:

######  Definition 3.

Consider a set $\mathcal{A}\subset\mathbb{R}^{d}$ with cardinality $m$111To be
more precise, $\mathcal{A}$ should be defined as a multi-set since we allow
duplicate elements in the set, e.g., the states of $m$ agents shall be counted
as $m$ points even if some of them may be identical.. For some
$n\in\mathbb{Z}_{\geq 0}$ and $n\leq m$, let $\mathcal{S}(\mathcal{A},n)$ be
the set of all its subset with cardinality $m-n$.

It is clear that the set $\mathcal{S}(\mathcal{A},n)$ contains $\binom{m}{n}$
elements, and each of them is associated with a convex hull. The intersection
of all these convex hulls plays a crucial role in our algorithm, which is
formally defined below:

######  Definition 4.

Consider a set $\mathcal{A}\subset\mathbb{R}^{d}$ with cardinality $m$. For
some $n\in\mathbb{Z}_{\geq 0}$ and $n\leq m$, we define
$\varPsi(\mathcal{A},n)$ as

$\displaystyle\varPsi(\mathcal{A},n)\triangleq\bigcap_{S\in\mathcal{S}(\mathcal{A},n)}\operatorname*{Conv}(S).$
(1)

In view of Definition 4, $\varPsi(\mathcal{A},n)$ is a subset of convex hulls
formed by any $m-n$ points in $\mathcal{A}$.

###  IV-A Description of the resilient algorithm

In this part, we shall provide a resilient solution to the multi-dimensional
consensus. Each normal agent $i\in\mathcal{B}$ starts with an initial state
$x^{i}(0)\in\mathbb{R}^{d}$. At any instant $k>0$, it makes updates as
outlined in Algorithm 1.

1: Receive the states from all neighboring agents $j\in\mathcal{N}_{i}$, and
collect these values in $\mathcal{X}^{i}(k)$.
2: Let $p=(k\operatorname*{mod}d)+1$. Sort points in $\mathcal{X}^{i}(k)$
according to their $p$-th entries in an ascending order. Initialize
$\mathcal{Y}^{i}(k)$ and $\mathcal{Z}^{i}(k)$ as empty.
3: Based on the sorted points, pick up the first $(d+1)F+1$ ones and collect
them in $\mathcal{Y}^{i}(k)$. Clearly, each point in $\mathcal{Y}^{i}(k)$ has
a smaller $p$-th entry than all the ones in
$\mathcal{X}^{i}(k)\backslash\mathcal{Y}^{i}(k)$. Calculate any point
$y^{i}(k)$, such that $y^{i}(k)\in\varPsi(\mathcal{Y}^{i}(k),F)$.
4: Similarly, pick up the last $(d+1)F+1$ ones of the sorted points and
collect them in $\mathcal{Z}^{i}(k)$. Compute any point
$z^{i}(k)\in\varPsi(\mathcal{Z}^{i}(k),F)$.
5: Agent $i$ updates its local state as:

$\begin{split}x^{i}(k+1)=\frac{x^{i}(k)+y^{i}(k)+z^{i}(k)}{3}.\end{split}$ (2)

6: Transmit the new state $x^{i}(k+1)$ to all neighbors $j\in\mathcal{N}_{i}$.

Algorithm 1 Resilient multi-dimensional consensus algorithm

We make some explanations on Algorithm 1. At each time $k$, the normal agents
sort the $p$-th entry of the received values, where $p$ varies alternatively
in $\\{1,2,...,d\\}$. We refer $y^{i}(k)$ and $z^{i}(k)$ as the “middle
points” in this paper. We would prove later that these points are “safe” as
they belong to the convex hull formed by benign states. Calculating any of
them requires a subset of neighboring states, which contains exactly
$(d+1)F+1$ points in $\mathcal{X}^{i}(k)$. As will be shown later (in Section
VI-A), the proposed protocol is of more lightweight than the existing ones
proposed in [23, 19]. Moreover, the update law (2) always involves the normal
agent’s own state. As claimed in [14], this mechanism helps to keep more
useful information each step. Finally, as every fault-free agent is only
required to access the information in its neighborhood, Algorithm 1 can be
implemented in a distributed manner.

###  IV-B Computation of “middle points”

This part discusses the computation of $y^{i}(k)$ in Step 3, by which
$z^{i}(k)$ can be calculated similarly. For simplicity, we omit the time index
$k$ in the sequel of this subsection.

For simplicity, we denote $\kappa=(d+1)F+1$. Note that
$\varPsi(\mathcal{Y}^{i},F)$ is an intersection of
$r\triangleq\binom{\kappa}{F}$ convex hulls, each of which is formed by a set
of $p=dF+1$ points. For each of these sets, let us define the matrix with the
points in it as

$Y_{j}=\left[\begin{array}[]{llll}x^{j_{1}}&x^{j_{2}}&\cdots&x^{j_{p}}\end{array}\right]\in\mathbb{R}^{d\times
p}.$

We then denote

$Y\triangleq\operatorname{diag}\left\\{Y_{j},j=1,2,\ldots,r\right\\}\in\mathbb{R}^{dr\times
pr}.$

For example, suppose $\mathcal{Y}^{i}=\\{x^{1},x^{2},x^{3}\\}$ and $F=1$. One
has

$\displaystyle Y_{1}$
$\displaystyle=\left[\begin{array}[]{ll}x^{1}&x^{2}\end{array}\right],Y_{2}=\left[\begin{array}[]{ll}x^{1}&x^{3}\end{array}\right],Y_{3}=\left[\begin{array}[]{ll}x^{2}&x^{3}\end{array}\right],$

and

$Y=\left[\begin{array}[]{lll}Y_{1}&0&0\\\ 0&Y_{2}&0\\\
0&0&Y_{3}\end{array}\right].$

The following lemma provides an equivalent representation of
$\varPsi(\mathcal{Y}^{i},F)$ in terms of equality and inequality constraints:

######  Lemma 1 ( [24, Lemma 4]).

Let $C\in\mathbb{R}^{r\times r}$ be the circulant matrix with the first row as
$\left[\begin{array}[]{lllll}1&-1&0&\cdots&0\end{array}\right].$ Then

$\varPsi(\mathcal{Y}^{i},F)=\left\\{\frac{1}{r}\left(\mathbf{1}_{r}^{\prime}\otimes
I_{d}\right)Y\beta\right\\},$

for all $\beta\in\mathbb{R}^{pr}$ such that

$\displaystyle\begin{bmatrix}\left(C\otimes I_{d}\right)Y\\\
\left(I_{r}\otimes\mathbf{1}_{p}^{\prime}\right)\end{bmatrix}\beta$
$\displaystyle=\begin{bmatrix}\mathbf{0}_{dr}\\\ \mathbf{1}_{r}\end{bmatrix},$
(3) $\displaystyle\beta$ $\displaystyle\geq\mathbf{0}_{pr}.$

Note that any point in $\varPsi(\mathcal{Y}^{i},F)$ is acceptable. We could,
thereby, choose any $\beta^{*}$ satisfying (3). Then
$y^{i}=\left(\mathbf{1}_{r}^{\prime}\otimes I_{n}\right)Y\beta^{*}/r$. There
are various manners to achieve this end. For example, Phase I method in [25,
Section 11.4] can be adopted by solving the following linear programming:

$\displaystyle\max$ $\displaystyle\alpha$ (4) $\displaystyle s.t.$
$\displaystyle\begin{bmatrix}\left(C\otimes I_{d}\right)Y\\\
\left(I_{r}\otimes\mathbf{1}_{p}^{\prime}\right)\end{bmatrix}\beta=\begin{bmatrix}\mathbf{0}_{dr}\\\
\mathbf{1}_{r}\end{bmatrix},$
$\displaystyle\beta_{i}\geq\alpha,\;\;i=1,2,...,pr.$

We will prove in Corollary 1 that $\varPsi(\mathcal{Y}^{i},F)\neq\varnothing$.
Therefore, one can always find some $\beta^{*}$ such that the optimal value
$\alpha^{*}\geq 0$. The computational complexity of achieving $\beta^{*}$
could be $\mathcal{O}\left((pr)^{3}\right)$ [25]. It is not surprising that
this computational cost is independent of $|\mathcal{N}_{i}|$, as the
cardinality of $\mathcal{Y}^{i}$ is fixed as $(d+1)F+1$. As a consequent, the
algorithm will not introduce higher complexity in the network where agent $i$
has a large number of neighbors.

##  V Algorithm Analysis

This section is devoted to the theoretical analysis of Algorithm 1. We shall
show that the proposed algorithm is both realizable and resilient.

###  V-A Realizability

In order to demonstrate its realizability, we need to prove the existence of
$y^{i}(k)$ and $z^{i}(k)$. To this end, it is helpful to introduce Helly’s
Theorem, which is a key supporting technique of this paper:

Helly’s Theorem [26].  Let $X_{1},\cdots,X_{p}$ be a finite collection of
convex subsets in $\mathbb{R}^{d}$, with $p>d$. If the intersection of every
$d+1$ of these sets is nonempty, then the whole collection has a nonempty
intersection. That is,

$\bigcap_{j=1}^{p}X_{j}\neq\varnothing.$

Below is an immediate result of Helly’s Theorem:

######  Corollary 1.

Let $\mathcal{A}$ be a set with cardinality $m$ in $\mathbb{R}^{d}$. For any
$n\in\mathbb{Z}_{\geq 0}$, if $m\geq n(d+1)+1$, then the following result
holds

$\varPsi(\mathcal{A},n)\neq\varnothing.$

###### Proof.

See Appendix. ∎

Invoking Assumption 1, $\mathcal{Y}^{i}(k),\mathcal{Z}^{i}(k)\neq\varnothing$.
Therefore, $y^{i}(k)$ and $z^{i}(k)$ are well-defined.

###  V-B Resiliency: validity

After proving Algorithm 1 is realizable, we next show it ensures the validity
condition of resilient consensus. Let us define a set

$\mathcal{S}^{i}(k)\triangleq\varPsi(\mathcal{X}^{i}(k),F).$ (5)

Recall that $\mathcal{X}^{i}(k)$ is the collection of states from
$j\in\mathcal{N}_{i}$. In this paper, we interpret $\mathcal{S}^{i}(k)$ as a
“safe kernel” as illustrated in Fig. 2.

Figure 2: A $2$D illustration of “safe kernel”. Suppose agent
$i\in\mathcal{B}$ has $5$ neighbors and each of their states is represented by
the location of a circle. Let $F=1$. The green region denotes the safe kernel
$\mathcal{S}^{i}(k)=\varPsi(\mathcal{X}^{i}(k),1)$. The points marked by blue
circle and red square are $y^{i}(k)$ and $z^{i}(k)$, respectively.

The below results would be helpful, with proofs given in Appendix:

######  Lemma 2.

Consider two collections of sets $\left\\{A_{i}\right\\}_{i\in I}$ and
$\left\\{B_{j}\right\\}_{j\in\mathcal{J}}$. If for any $j\in\mathcal{J}$,
there exists an $i^{*}\in\mathcal{I}$ such that $A_{i^{*}}\subset B_{j}$, then

$\displaystyle\bigcap_{i\in\mathcal{I}}A_{i}\subset\bigcap_{j\in\mathcal{J}}B_{j}.$

######  Lemma 3.

Consider any set $\mathcal{A}_{1}$ with cardinality $m_{1}$ and
$\mathcal{A}_{2}$ with cardinality $m_{2}$. If
$\mathcal{A}_{1}\subset\mathcal{A}_{2}$, then for any $n\leq m_{1}$, the
following statement holds:

$\varPsi(\mathcal{A}_{1},n)\subset\varPsi(\mathcal{A}_{2},n).$

From Algorithm 1, it is clear that
$\mathcal{Y}^{i}(k),\mathcal{Z}^{i}(k)\subset\mathcal{X}^{i}(k)$. In view of
Lemma 3, one has $y^{i}(k),z^{i}(k)\in\mathcal{S}^{i}(k)$, namely the middle
points are always within the safe kernel.

Now consider the validity condition of resilient consensus. For simplicity, we
denote the convex hull formed by the benign agents’ states at time $k$ as
$\varOmega(k)$. The following proposition presents the non-expansion property
of $\varOmega(k)$:

######  Proposition 1 (Validity).

Consider the network $\mathcal{G}=(\mathcal{V},\mathcal{E})$. Suppose the
misbehaving agents follow either $F$-local or $F$-total attack model. With
Algorithm 1, the following relation holds at any $k\geq 0$:

$\varOmega(k+1)\subset\varOmega(k).$ (6)

###### Proof.

Consider the scenario under either $F$-local or $F$-total attacks. For a
benign agent $i$, there exist no less than $|\mathcal{X}^{i}(k)|-F$ benign
ones in its neighborhood. By definitions, one obtains that
$\mathcal{S}^{i}(k)$ is included in the convex hull formed by any
$|\mathcal{X}^{i}(k)|-F$ neighboring values. Hence, it is trivial to derive
that $\mathcal{S}^{i}(k)$ is a subset of the convex hull of the benign
neighbors’ states, that is, $\mathcal{S}^{i}(k)\subset\varOmega(k).$ Recall
(2), one directly has that $x^{i}(k+1)\in\varOmega(k)$ as it is a convex
combination of some points in $\varOmega(k)$.

Because the above relation holds for any normal node, one has
$\varOmega(k+1)\subset\varOmega(k)$. ∎

Hence, the safe kernel is “safe” in the sense that it is contained in the
convex hull formed by benign states. With two middle points in it, Algorithm 1
guarantees the validity condition of resilient consensus. That is, the healthy
agents would never move out of the convex hull formed by their initial values,
namely $\varOmega(0)$, despite the influence of the misbehaving ones.

###  V-C Resiliency: agreement

This subsection presents the guarantee of agreement condition. We first
introduce the below lemma:

######  Lemma 4.

Let $\mathcal{A}$ be a set with $|\mathcal{A}|=(d+1)n+1$. The following
relations hold for any linear function $l(x)$:

  1. 1.

If there exists at least $dn+1$ points $\bar{x}$ in $\mathcal{A}$, such that
$l(\bar{x})\leq m$, then for any point $y\in\varPsi(\mathcal{A},n)$, $l(y)\leq
m$ holds;

  2. 2.

If there exists at least $dn+1$ points $\bar{x}$ in $\mathcal{A}$, such that
$l(\bar{x})\geq M$, then for any point $z\in\varPsi(\mathcal{A},n)$, $l(z)\geq
M$ holds.

###### Proof.

By Corollary 1, $\varPsi(\mathcal{A},n)\neq\varnothing$. We then show the
rationale of the statements as follows:

  1. 1.

There exist $dn+1$ points $\bar{x}$ in $\mathcal{A}$ such that $l(\bar{x})\leq
m$. Consider the convex hull formed by these $\bar{x}$’s. Clearly, any element
$x$ in this convex hull also has $l(x)\leq m$. We could infer from Definition
4 that $\varPsi(\mathcal{A},n)$ is a subset of this convex hull, and thus the
first statement holds.

  2. 2.

The second statement is proved in a similar manner as above.

∎

For simplicity, let $l_{p}(x)=e_{p}^{T}x$, a linear function which returns the
$p$-th entry of $x\in\mathbb{R}^{d}$. Then among all $l_{p}(x)$’s, where
$x\in\mathcal{X}^{i}(k)$, we respectively denote $\underline{m}_{p}(k)$ and
$\overline{M}_{p}(k)$ as the $(dF+1)$-th smallest and largest values. From
Lemma 4, the next result gives the bounds on middle points:

######  Corollary 2.

Consider the network $\mathcal{G}=(\mathcal{V},\mathcal{E})$. Suppose normal
agent $i\in\mathcal{B}$ updates by Algorithm 1, then it holds that:

$\displaystyle y^{i}_{p}(k)$ $\displaystyle\leq\underline{m}_{p}(k),$ (7)
$\displaystyle z^{i}_{p}(k)$ $\displaystyle\geq\overline{M}_{p}(k).$

Now it is ready to provide the main results. In what follows, we shall present
sufficient conditions on network topology, under which the agreement condition
of resilient consensus will be guaranteed.

######  Proposition 2 (Agreement).

Consider the network $\mathcal{G}=(\mathcal{V},\mathcal{E})$. Suppose the
misbehaving agents follow an $F$-local attack model. If the network is with
$((d+1)F+1)$-robustness, then with Algorithm 1, all the benign agents are
guaranteed to achieve consensus exponentially, regardless of the actions of
misbehaving agents.

###### Proof.

This proof follows the general structure of that in scalar systems [14], with
some subtle changes to account for our specific update rules including
$y^{i}(k)$ and $z^{i}(k)$.

To proceed, at any $p\in\\{1,2,...,d\\}$, let us respectively denote
$m_{p}(k)$ and $M_{p}(k)$ as the minimum and maximum value among the $p$-th
components of normal agents’ states at time $k$. That is,

$\begin{split}&m_{p}(k)\triangleq\min_{i\in\mathcal{B}}x^{i}_{p}(k),\\\
&M_{p}(k)\triangleq\max_{i\in\mathcal{B}}x^{i}_{p}(k).\end{split}$ (8)

As a direct result of Proposition 1, $m_{p}(k+1)\geq m_{p}(k)$ and
$M_{p}(k+1)\leq M_{p}(k)$ for any $p$ and $k$.

To establish the achievement of consensus, it is equivalent to prove that the
benign agents reach an agreement at any dimension. Due to the symmetry between
different dimensions, without loss of generality, we would only focus on the
first component of local states. The temporal difference is thereby defined as
$\Delta_{1}(k)=M_{1}(k)-m_{1}(k)$. We attempt to show that $\Delta_{1}(k)$
asymptotically approaches $0$.

For notation convenience, the following definitions are further imposed for
any $\bar{k}\geq k$, and any $\epsilon\in\mathbb{R}$:

$\begin{split}\mathcal{V}^{M}(k,\bar{k},\epsilon)\triangleq\\{i\in\mathcal{V}:x^{i}_{1}(\bar{k})>M_{1}(k)-\epsilon\\},\\\
\mathcal{V}^{m}(k,\bar{k},\epsilon)\triangleq\\{i\in\mathcal{V}:x^{i}_{1}(\bar{k})<m_{1}(k)+\epsilon\\}.\end{split}$
(9)

Note that the subscript is dropped in the above notations for the sake of
brevity. Clearly, $\mathcal{V}_{M}(k,\bar{k},\epsilon)$ [resp.
$\mathcal{V}_{m}(k,\bar{k},\epsilon)$] includes all agents whose state’s first
component is greater [resp. less] than $M(k)-\epsilon$ [resp. $m(k)+\epsilon$]
at time $\bar{k}$. We then define

$\begin{split}\mathcal{B}^{M}(k,\bar{k},\epsilon)\triangleq\mathcal{V}^{M}(k,\bar{k},\epsilon)\cap\mathcal{B},\\\
\mathcal{B}^{m}(k,\bar{k},\epsilon)\triangleq\mathcal{V}^{m}(k,\bar{k},\epsilon)\cap\mathcal{B},\end{split}$
(10)

which contains only benign agents in $\mathcal{V}^{M}(k,\bar{k},\epsilon)$ and
$\mathcal{V}^{m}(k,\bar{k},\epsilon)$, respectively.

Consider the time step $k$ with $p=(k\operatorname*{mod}d)+1=1$. Suppose that
$M_{1}(k)\neq m_{1}(k)$, i.e., $\Delta_{1}(k)>0$. Let us define
$\epsilon_{0}=\Delta_{1}(k)/2$. It is easy to know that
$\mathcal{B}^{M}(k,k,\epsilon_{0})$ and $\mathcal{B}^{m}(k,k,\epsilon_{0})$
are disjoint. Furthermore, since each of these sets contains a benign agent
with the first component being $M_{1}(k)$ or $m_{1}(k)$, both of them are
nonempty. As the network is $((d+1)F+1)$-robust, there exists one benign node
in either $\mathcal{B}^{M}(k,k,\epsilon_{0})$ or
$\mathcal{B}^{m}(k,k,\epsilon_{0})$ that has at least $(d+1)F+1$ neighboring
agents outside its set.

Without loss of generality, let $i\in\mathcal{B}^{M}(k,k,\epsilon_{0})$ be
such an agent who has no less than $(d+1)F+1$ neighbors in
$\mathcal{V}\backslash\mathcal{B}^{M}(k,k,\epsilon_{0})$. Moreover, under the
$F$-local attack model, no less than $dF+1$ points in agent $i$’s neighborhood
have their first components upper bounded by $M_{1}(k)-\epsilon_{0}$.
Therefore one has that $\underline{m}_{1}(k)\leq M_{1}(k)-\epsilon_{0}$.

Invoking Corollary 2, $y^{i}_{1}(k)\leq\underline{m}_{1}(k)\leq
M_{1}(k)-\epsilon_{0}$. We thus obtain that

$\begin{split}x^{i}_{1}(k+1)&=\frac{1}{3}(x^{i}_{1}(k)+y^{i}_{1}(k)+z^{i}_{1}(k))\\\
&\leq\frac{2}{3}M_{1}(k)+\frac{1}{3}(M_{1}(k)-\epsilon_{0})\\\
&=M_{1}(k)-\frac{1}{3}\epsilon_{0}.\end{split}$ (11)

It is pointed out that this upper bound also applies to any benign agent in
$\mathcal{V}\backslash\mathcal{V}^{M}(k,k,\epsilon_{0})$, as it will apply its
own value for updates.

Similarly, if the benign agent $j\in\mathcal{B}^{m}(k,k,\epsilon_{0})$ has at
least $(d+1)F+1$ neighbors outside its set, we know that
$z^{i}_{1}(k)\geq\overline{M}_{1}(k)\geq m_{1}(k)+\epsilon_{0}$ and shall have
an analogous result that $x^{j}_{1}(k+1)\geq m_{1}(k)+\epsilon_{0}/3,$ which
again, is the lower bound for every benign agent in
$\mathcal{V}\backslash\mathcal{V}^{m}(k,k,\epsilon_{0})$.

Define $\epsilon_{1}=\epsilon_{0}/3$. From former discussions, one knows that
at least one benign agent in $\mathcal{B}^{M}(k,k,\epsilon_{0})$ has its first
component decreased to below $M_{1}(k)-\epsilon_{1}$, or one benign agent in
$\mathcal{B}^{m}(k,k,\epsilon_{0})$ has its first component increased to above
$m_{1}(k)+\epsilon_{1}$, or both. As a result, it must be either
$\mathcal{B}^{M}(k,k+1,\epsilon_{1})\subsetneq\mathcal{B}^{M}(k,k,\epsilon_{0}),$
or
$\mathcal{B}^{m}(k,k+1,\epsilon_{1})\subsetneq\mathcal{B}^{m}(k,k,\epsilon_{0}),$
or both.

Then consider the update at $k+2$. For any normal agent in
$\mathcal{V}\backslash\mathcal{V}^{M}(k,k+1,\epsilon_{1})$, it is trivial to
see that

$\begin{split}x^{i}_{1}(k+2)&=\frac{1}{3}(x^{i}_{1}(k+1)+y^{i}_{1}(k+1)+z^{i}_{1}(k+1))\\\
&\leq\frac{1}{3}(M_{1}(k)-\epsilon_{1})+\frac{2}{3}M_{1}(k+1)\\\
&\leq\frac{1}{3}(M_{1}(k)-\epsilon_{1})+\frac{2}{3}M_{1}(k)\\\
&=M_{1}(k)-\epsilon_{2},\end{split}$ (12)

with $\epsilon_{2}=\epsilon_{1}/3$. Thereby,
$\mathcal{B}^{M}(k,k+2,\epsilon_{2})\subset\mathcal{B}^{M}(k,k+1,\epsilon_{1})$.
Hence, for each $1\leq t\leq d$, we can recursively define
$\epsilon_{t}=\epsilon_{0}/3^{t}$ and obtain that
$\mathcal{B}^{M}(k,k+d,\epsilon_{d})\subset\mathcal{B}^{M}(k,k+1,\epsilon_{1})\subsetneq\mathcal{B}^{M}(k,k,\epsilon_{0})$.
Similarly,
$\mathcal{B}^{m}(k,k+d,\epsilon_{d})\subsetneq\mathcal{B}^{m}(k,k,\epsilon_{0})$.

Note that $\epsilon_{d}<\epsilon_{0}$, and therefore the sets
$\mathcal{B}^{M}(k,k+d,\epsilon_{d})$ and
$\mathcal{B}^{m}(k,k+d,\epsilon_{d})$ are still disjoint. If both sets are
nonempty, as above, one can conclude that at least one of the following
statements is true:
$\mathcal{B}^{M}(k,k+2d,\epsilon_{2d})\subsetneq\mathcal{B}^{M}(k,k+d,\epsilon_{d}),$
or
$\mathcal{B}^{m}(k,k+2d,\epsilon_{2d})\subsetneq\mathcal{B}^{m}(k,k+d,\epsilon_{d})$.

Hence, for any $\kappa\geq 1$, as long as both $\mathcal{B}^{M}(k,k+\kappa
d,\epsilon_{\kappa d})$ and $\mathcal{B}^{m}(k,k+\kappa d,\epsilon_{\kappa
d})$ are nonempty, we can repeat the above analysis and conclude that at least
one of these two sets will shrink at the next time step. Since
$|\mathcal{B}^{M}(k,k,\epsilon_{0})|+|\mathcal{B}^{m}(k,k,\epsilon_{0})|\leq|\mathcal{B}|$,
there must be the case that either
$\mathcal{B}^{M}(k,k+d|\mathcal{B}|,\epsilon_{d|\mathcal{B}|})=\varnothing,$
or
$\mathcal{B}^{m}(k,k+d|\mathcal{B}|,\epsilon_{d|\mathcal{B}|})=\varnothing,$
or both. We assume the former statement holds. From (9), at time step
$k+d|\mathcal{B}|$, all the fault-free agents have their first elements being
at most $M_{1}(k)-\epsilon_{d|\mathcal{B}|}$, i.e.,
$M_{1}(k+d|\mathcal{B}|)\leq M_{1}(k)-\epsilon_{d|\mathcal{B}|}.$ On the other
hand, from Proposition 1, we have $m_{1}(k+d|\mathcal{B}|)\geq m_{1}(k).$ As a
result,

$\Delta_{1}(k+d|\mathcal{B}|)\leq\Big{(}1-\frac{1}{2\cdot
3^{d|\mathcal{B}|}}\Big{)}\Delta_{1}(k).$ (13)

Therefore we conclude that $\Delta_{1}(k)$ vanishes exponentially. ∎

The next result elaborates a different condition for the proposed algorithm to
succeed in $F$-total threats:

######  Proposition 3 (Agreement).

Consider the network $\mathcal{G}=(\mathcal{V},\mathcal{E})$. Suppose the
misbehaving agents follow an $F$-total attack model. If the network is with
$(dF+1,F+1)$-robustness, then with Algorithm 1, all the benign agents are
guaranteed to achieve consensus exponentially, regardless of the actions of
misbehaving agents.

###### Proof.

See Appendix-D. ∎

######  Remark 1.

By definitions, we note that a $((d+1)F+1)$-robust graph is
$(dF+1,F+1)$-robust as well, but not vice versa. That is to say, the network
which is able to tolerate $F$-local attacks could also survive the $F$-total
ones, while the converse is not true. This observation is consistent with the
fact that the $F$-globally bounded threats are special versions of locally
bounded ones.

Given the above results, one thus immediately concludes that the proposed
algorithm facilitates the resilient consensus, as stated below:

######  Theorem 1.

Consider the network $\mathcal{G}=(\mathcal{V},\mathcal{E})$. Suppose the
network satisfies one of the following conditions:
1) under $F$-local attack model, and is $((d+1)F+1)$-robust,
2) under $F$-total attack model, and is $(dF+1,F+1)$-robust.
With Algorithm 1, benign agents exponentially achieve the resilient consensus,
regardless of the actions of misbehaving ones. That is, as $k\to\infty$,

$x^{i}(k)=x^{j}(k)=\hat{x}\quad\mbox{ for any }i,j\in\mathcal{B},$ (14)

where $\hat{x}\in\varOmega(0).$

###### Proof.

The theorem is immediately achieved as both the validity and agreement
conditions have been established in Propositions 1-3. ∎

Theorem 1 indicates that under certain topological conditions, the safe kernel
approach guarantees all benign agents reach an agreement on a weighted average
of their initial states. It protects the local states of benign agents from
being driven to arbitrary values, and thus could withstand the compromise of
partial agents while providing a desired level of security. Furthermore, since
its convergence does not depend on the actions of misbehaving agents, it works
effectively even in the worst-case scenario, where the faulty agents could
have full knowledge of graph topology, updating rules, etc, and could also be
Byzantine agents that are able to send different information to different
neighbors. Finally, let us consider the scenario when there is no faulty
agents at all, i.e., $|\mathcal{F}|=0$. Theorem 1 shows that the proposed
strategy only guarantees a ‘decent’ solution (i.e., within $\varOmega(0)$)
instead of the exact average value. This implies that in order to increase the
system’s resilience, we sacrifice its performance during normal operations.
Hence, there exists a trade-off between security and optimality.

##  VI Discussions

Some discussions would be presented in this section.

###  VI-A Remarks on the safe kernel

Consider the updating rules in resilient consensus algorithms. At every step,
the normal agent $i$ obtains the states in its neighborhood, whereas up to $F$
of them might be faulty. To ensure its state updated in a safe manner, agent
$i$ hopes to use only good inputs. Yet as it has no knowledge on the
identities of these values, it intends to achieve a resilient convex
combination, which lies in the convex hull of any $|\mathcal{N}_{i}|-F$
neighboring states.

Different from [16, 17], where Tverberg points are applied, this paper,
inspired by Helly’s Theorem, achieves the resilient convex combination through
the intersection of convex hulls. Let us recall the safe kernel
$\mathcal{S}^{i}(k)$ illustrated in Fig. 2. From Definitions 3 and 4, it
intuitively ignores the effects from combination of any $F$ values. At any
time, the healthy agent modifies its state towards this kernel. The impacts of
malicious agents on the benign ones are thus limited, with formal proof given
in Proposition 1.

Note that, in [23] and our previous work [19], the safe kernel
$\mathcal{S}^{i}(k)$ is required to be exactly calculated. Although the
results therein are elegant, a major concern of applying them is the high
computational complexity. More specifically, $\mathcal{S}^{i}(k)$ is the
intersection of $\binom{|\mathcal{N}_{i}|}{F}$ convex hulls, and existing
approaches for the computation of this intersection are usually $\\#p$-hard (
[27]). Moreover, since this computation depends on every state in
$\mathcal{X}^{i}(k)$, these algorithms may fail in a large neighborhood where
node $i$ has a large number of neighbors. As a contrast, although the proof of
this work is established on $\mathcal{S}^{i}(k)$, we indeed do not need to
compute the whole kernel, but two “middle points” insides. As shown in Section
IV-B, this step can be achieved by a linear programming, the computational
complexity of which will not increase within a larger neighborhood.

###  VI-B Remarks on the computation cost

Compared with the simple approach to directly use the existing scalar
algorithms (like MSR or W-MSR) to each dimension of the state vectors, the
proposed algorithm inevitably introduces a higher computational cost,
especially when $d$ or $F$ is large. However, on the other hand, it would
provide a better convergence result as shown in Fig. 1. This fact indicates
the trade-off between the high consensus accuracy and low computational
complexity.

Our work enables a fine tuning of this trade-off. To see this, one can choose
to divide the $d$ dimensions into several subgroups and apply our algorithm
within each subgroup. The updated states will then be rejoined in order as a
$d$-dimensional vector to be broadcast to its neighbors for next iteration.
Clearly, a larger group indicates a more accurate result but a higher
computational cost. For example, let us consider a $4$D system with $F=1$.
Recalling discussions in Section IV-B, resilient agreement within
$\varOmega(0)$ is achieved with computational complexity
$\mathcal{O}\left((pr)^{3}\right)$, where $p=5$ and $r=6$. Alternatively, one
could, for example, divide the first and second entries of system states into
one group and the remaining entries into another group. By applying Algorithm
1 within each $2$D subgroup, the computational cost reduces to the one with
$p=3$ and $r=4$. However, this approach leads to a compromise of system
security. Namely only the validity condition within each subgroup can be
guaranteed.

In practice, it also might be the case that certain components of the system
variables represent more critical information. Then, one can choose to use
Algorithm 1 on the group of these critical ones to better protect the system,
while applying MSR or W-MSR to each of the other components to reduce
computational burden.

###  VI-C Discussions on the network failing to meet sufficient conditions

The resiliency analysis shows the required network robustness increases
linearly with the dimension of state. Thus, one might ask: what if the network
is not “robust” enough to meet these assumptions?

A naive way to handle this problem works in a similar way to that in Section
VI-B. Specifically, suppose the given network can tolerate $F$ faulty agents
only when the system dimension is no more than $d^{\prime}(<d)$. Then one
could divide the $d$ components into several groups with the cardinality of
each group no more than $d^{\prime}$. At any time step, Algorithm 1 is applied
within every group. As discussed before, this approach fails to guarantee the
convergence within $\varOmega(0)$. Particularly, if $d^{\prime}=1$, its
performance will degrade to that of directly applying MSR or W-MSR to each
component.

Another possible solution is to establish the so-called “trusted agents” in
network, which are the well-protected ones and cannot be compromised by any
attacker [28]. Under this case, if the benign agent have some trusted nodes in
neighborhood, the middle points will be the ones in the convex hull formed by
these trusted neighbors. Assumption 1 can be further relaxed as: For any
$i\in\mathcal{V}$, it either contains at least one trusted neighbor or holds
that $|\mathcal{N}_{i}|\geq(d+1)F+1$. With the help of trusted nodes,
resilient consensus can be achieved under more relaxed topological conditions.
Due to the space limitation, the detailed algorithm and proofs are omitted in
this paper.

##  VII Numerical Example

In this section, we provide a numerical example to verify the theoretical
results established in the previous sections. The $(3,2)$-robust graph in Fig.
3 is chosen as the communication network 222This network is established based
on the $(3,2)$-robust network given in [29] and Theorem 1 therein, which shows
how to construct an $(r,s)$-robust digraph with an existing $(r,s)$-robust
one., where the node set is $\mathcal{V}=\\{1,2,\cdots,20\\}$. Proposition 3
indicates that the network can tolerate a single misbehaving node in a
$2$-dimensional system. This agent intends to prevent others from reaching a
correct consensus by violating the rule in Algorithm 1 and setting its states
as $x^{2}_{1}(k)=4.5*\sin(k/5)$ and $x^{2}_{2}(k)=k/25+1$ at any time $k$. On
the other hand, the benign agents are initialized randomly within
$[-3,3]\times[0,5]$ and always follow (2) for updates.

Figure 3: A $(3,2)$-robust communication network. Faulty agent Figure 4: The
trajectory of local states under Algorithm 1, where the area surrounded by the
dashed lines is the convex hull of the initial states of benign agents.
$5$$10$$15$$20$$-2$$0$$2$$x^{i}_{1}(k)$$5$$10$$15$$20$$0$$2$$4$Time
$k$$x^{i}_{2}(k)$ Figure 5: The states of normal agents $x^{i}(k),\forall
i\in\mathcal{B}$.

The performance of Algorithm 1 is tested in Figs. 4 and 5. The result shows
that the states of benign agents are guaranteed to be within the convex hull
of their initial states at any time and they finally achieve a common value,
which validates the established results. Since the malicious agent is unable
to affect the final agreement too much, our protocol helps to improve the
system security.

##  VIII Conclusion

Due to their wide applications, the distributed coordinations in networked
systems have attracted much research interest. In this paper, we are
interested in the achievement of consensus under malicious agents. A resilient
“middle points” based algorithm is proposed in this work, which is also
applicable in the high dimensional spaces. By solving the middle points
through a linear programming, the proposed strategy introduces a lower
computational complexity than most of the existing works. Under certain
network topology, it guarantees the benign agents exponentially reach an
agreement within the convex hull of their initial states. Finally, as the
consensus arguably forms the foundation for distributed computing, the results
in this paper lay a solid foundation for future works to develop resilient
coordination protocols in other consensus-based problems.

##  Appendix A Proof

###  A-A Proof of Corollary 1

Corollary 1 is obvious when $n=0$. Thus we only focus on the scenario when
$n\geq 1$.

According to Definition 4, $\varPsi(\mathcal{A},n)$ is an intersection of
$\binom{m}{n}$ convex hulls. Since $m\geq n(d+1)+1$, it is trivial to prove
that $\binom{m}{n}>d$ holds.

On the other hand, each of these convex hulls is created by excluding $n$
elements of $\mathcal{A}$. Then consider any $d+1$ of them, they discard at
most $n(d+1)$ points in all. Since $m\geq n(d+1)+1$, it must be the case that
at least one element in $\mathcal{A}$ is retained by all of them. This
indicates that any $d+1$ convex hulls must have a nonempty intersection. By
applying Helly’s Theorem, the proof is completed.

###  A-B Proof of Lemma 2

Denote a subset of $\left\\{A_{i}\right\\}_{i\in I}$ as
$\left\\{A_{i^{*}}\right\\}_{i^{*}\in I}$, such that
$\left\\{A_{i^{*}}\right\\}_{i^{*}\in I}$ contains all $A_{i^{*}}$ which has a
superset in $\left\\{B_{j}\right\\}_{j\in\mathcal{J}}$. The proof is then
completed by noticing that

$\displaystyle\bigcap_{i\in\mathcal{I}}A_{i}\subset\bigcap_{i^{*}\in\mathcal{I}}A_{i^{*}}\subset\bigcap_{j\in\mathcal{J}}B_{j}.$

###  A-C Proof of Lemma 3

We shall prove that every set $S_{2}$ in $\mathcal{S}(\mathcal{A}_{2},n)$ is a
superset for some set $S_{1}$ in $\mathcal{S}(\mathcal{A}_{1},n)$. To see
this, notice that

$\displaystyle S_{2}$ $\displaystyle=\mathcal{A}_{2}\backslash
S_{2}^{c}\supset\left(\mathcal{A}_{2}\backslash
S_{2}^{c}\right)\cap\mathcal{A}_{1}$
$\displaystyle=\mathcal{A}_{1}\backslash\left(S_{2}^{c}\cap\mathcal{A}_{1}\right),$

where $S_{2}^{c}=\mathcal{A}_{2}\backslash S_{2}$ is a set with cardinality
$n$. Notice that $S_{2}^{c}\cap\mathcal{A}_{1}$ has cardinality no greater
than $n$, which means that
$\mathcal{A}_{1}\backslash\left(S_{2}^{c}\cap\mathcal{A}_{1}\right)$ is a
superset of some set in $\mathcal{S}(\mathcal{A}_{1},n)$. The proof is thus
finished by invoking Lemma 2.

###  A-D Proof of Proposition 3

Proposition 3 is proved in a similar manner to that of Proposition 2. The
essential point is that if $\mathcal{V}^{M}(k,k+\kappa d,\epsilon_{\kappa d})$
and $\mathcal{V}^{m}(k,k+\kappa d,\epsilon_{\kappa d})$ are nonempty and
disjoint, and if both of these sets contain some benign agents, then under
$(dF+1,F+1)$-robust graph, there exists at least one benign agent in either
$\mathcal{V}^{M}(k,k+\kappa d,\epsilon_{\kappa d})$ or
$\mathcal{V}^{m}(k,k+\kappa d,\epsilon_{\kappa d})$ that has no less than
$dF+1$ neighboring agents outside its set. Suppose the benign agent
$i\in\mathcal{V}^{M}(k,k+\kappa d,\epsilon_{\kappa d})$ is such a node.
Following a similar proof procedure of Proposition 2, we know that agent $i$
will always apply a state who has its first entry being no more than
$M_{1}(k)-\epsilon_{\kappa d}$ for updating, under Algorithm 1. The result can
be finally concluded by applying the proof techniques as before.

## References

  * [1] W. Ren, R. W. Beard, and E. M. Atkins, “Information consensus in multivehicle cooperative control,” _IEEE Control Systems Magazine_ , vol. 27, no. 2, pp. 71–82, 2007.
  * [2] ——, “A survey of consensus problems in multi-agent coordination,” in _Proceedings of the 2005, American Control Conference, 2005._ IEEE, 2005, pp. 1859–1864.
  * [3] R. L. Raffard, C. J. Tomlin, and S. P. Boyd, “Distributed optimization for cooperative agents: Application to formation flight,” in _Decision and Control, 2004. CDC. 43rd IEEE Conference on_ , vol. 3. IEEE, 2004, pp. 2453–2459.
  * [4] R. Olfati-Saber, J. A. Fax, and R. M. Murray, “Consensus and cooperation in networked multi-agent systems,” _Proceedings of the IEEE_ , vol. 95, no. 1, pp. 215–233, 2007.
  * [5] D. P. Spanos, R. Olfati-Saber, and R. M. Murray, “Distributed sensor fusion using dynamic consensus,” in _IFAC World Congress_. Citeseer, 2005.
  * [6] C. C. Moallemi and B. Van Roy, “Consensus propagation,” _IEEE Transactions on Information Theory_ , vol. 52, no. 11, pp. 4753–4766, 2006.
  * [7] E. Wei and A. Ozdaglar, “Distributed alternating direction method of multipliers,” in _Decision and Control (CDC), 2012 IEEE 51st Annual Conference on_. IEEE, 2012, pp. 5445–5450.
  * [8] Y. Mo, T. H.-J. Kim, K. Brancik, D. Dickinson, H. Lee, A. Perrig, and B. Sinopoli, “Cyber–physical security of a smart grid infrastructure,” _Proceedings of the IEEE_ , vol. 100, no. 1, pp. 195–209, 2012.
  * [9] S. Sundaram and B. Gharesifard, “Distributed optimization under adversarial nodes,” _IEEE Transactions on Automatic Control_ , 2018.
  * [10] D. Dolev, N. A. Lynch, S. S. Pinter, E. W. Stark, and W. E. Weihl, “Reaching approximate agreement in the presence of faults,” _Journal of the ACM (JACM)_ , vol. 33, no. 3, pp. 499–516, 1986.
  * [11] R. M. Kieckhafer and M. H. Azadmanesh, “Reaching approximate agreement with mixed-mode faults,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 5, no. 1, pp. 53–63, 1994.
  * [12] N. H. Vaidya, L. Tseng, and G. Liang, “Iterative approximate byzantine consensus in arbitrary directed graphs,” in _Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing_. ACM, 2012, pp. 365–374.
  * [13] M. M. de Azevedo and D. M. Blough, “Multistep interactive convergence: An efficient approach to the fault-tolerant clock synchronization of large multicomputers,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 9, no. 12, pp. 1195–1212, 1998.
  * [14] H. J. LeBlanc, H. Zhang, X. Koutsoukos, and S. Sundaram, “Resilient asymptotic consensus in robust networks,” _IEEE Journal on Selected Areas in Communications_ , vol. 31, no. 4, pp. 766–781, 2013.
  * [15] S. M. Dibaji and H. Ishii, “Consensus of second-order multi-agent systems in the presence of locally bounded faults,” _Systems & Control Letters_, vol. 79, pp. 23–29, 2015.
  * [16] N. H. Vaidya and V. K. Garg, “Byzantine vector consensus in complete graphs,” in _Proceedings of the 2013 ACM symposium on Principles of distributed computing_ , 2013, pp. 65–73.
  * [17] N. H. Vaidya, “Iterative byzantine vector consensus in incomplete graphs,” in _International conference on distributed computing and networking_. Springer, 2014, pp. 14–28.
  * [18] P. K. Agarwal, M. Sharir, and E. Welzl, “Algorithms for center and tverberg points,” _ACM Transactions on Algorithms (TALG)_ , vol. 5, no. 1, pp. 1–20, 2008.
  * [19] J. Yan, Y. Mo, X. Li, and C. Wen, “A” safe kernel” approach for resilient multi-dimensional consensus,” _arXiv preprint arXiv:1911.10836_ , 2019.
  * [20] D. Avis and K. Fukuda, “A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra,” _Discrete & Computational Geometry_, vol. 8, no. 3, pp. 295–313, 1992.
  * [21] L. Xiao, S. Boyd, and S.-J. Kim, “Distributed average consensus with least-mean-square deviation,” _Journal of Parallel and Distributed Computing_ , vol. 67, no. 1, pp. 33–46, 2007.
  * [22] A. Nedic, A. Ozdaglar, and P. A. Parrilo, “Constrained consensus and optimization in multi-agent networks,” _IEEE Transactions on Automatic Control_ , vol. 55, no. 4, pp. 922–938, 2010.
  * [23] H. Mendes and M. Herlihy, “Multidimensional approximate agreement in byzantine asynchronous systems,” in _Proceedings of the forty-fifth annual ACM symposium on Theory of computing_ , 2013, pp. 391–400.
  * [24] X. Wang, S. Mou, and S. Sundaram, “A resilient convex combination for consensus-based distributed algorithms,” _arXiv preprint arXiv:1806.10271_ , 2018.
  * [25] S. Boyd, S. P. Boyd, and L. Vandenberghe, _Convex optimization_. Cambridge university press, 2004.
  * [26] L. Danzer, B. Grünbaum, and V. Klee, “Helly’s theorem and its relatives,” _Proceedings of Symposia in Pure Mathematics_ , pp. 101–180, 1963.
  * [27] L. A. Rademacher, “Approximating the centroid is hard,” in _Proceedings of the twenty-third annual symposium on Computational geometry_ , 2007, pp. 302–305.
  * [28] W. Abbas, A. Laszka, and X. Koutsoukos, “Improving network connectivity and robustness using trusted nodes with application to resilient consensus,” _IEEE Transactions on Control of Network Systems_ , vol. 5, no. 4, pp. 2036–2048, 2017.
  * [29] H. J. LeBlanc, H. Zhang, S. Sundaram, and X. Koutsoukos, “Consensus of multi-agent networks in the presence of adversaries using only local information,” in _Proceedings of the 1st international conference on High Confidence Networked Systems_ , 2012, pp. 1–10.