Resilient Consensus with Multi-hop Communication

Cyber security of multi-agent systems and distributed algorithms has become an important research area in systems control in the last decade. For multi-agent systems, consensus is one of the fundamental problems [1], [2]. Based on consensus algorithms, various applications and distributed algorithms have been developed to solve different industrial problems, e.g., clock synchronization [3], energy management [4], distributed state estimation [5], distributed optimization [6, 7], and so on. As concerns for cyber security have rised in general, consensus problems in the presence of adversarial agents creating failures and attacks have attracted much attention; see, e.g., [8, 9, 10, 11]. One class of interdisciplinary problems that has been studied in both control and computer science is that of resilient consensus [12, 9, 13]. In these works, the adversarial agents are categorized into basically two types: Malicious agents and Byzantine agents. These agents are capable to manipulate their data arbitrarily and may even collaborate with each other. However, certain differences lie between them since malicious agents are limited as they must broadcast the same messages to all of their neighbors, while Byzantine agents can send individual messages to different neighbors (e.g., [9, 2, 14]).

Resilient consensus problems under the Byzantine model have a rich history in the area of distributed computing [2]. In [15], it has been shown that given a network with $n$ nodes and at most $f$ Byzantine nodes, a necessary and sufficient condition to reach resilient exact consensus is that $n\geq 3f+1$ and the graph connectivity is no less than $2f+1$. Furthermore, in [16], it has been reported that under deterministic asynchronous updates, even one misbehaving agent can make it impossible for the system to reach exact consensus. Then, to avoid this constraint of exact consensus, the authors of [17] introduced the approximate Byzantine consensus problem in complete networks (i.e., all-to-all communication), where the non-adversarial, normal nodes are required to achieve approximate agreement by converging to a relatively small interval in finite time. In [13], the authors proposed a necessary and sufficient condition for the approximate Byzantine consensus problem in networks with general topologies.

In this paper, we study resilient asymptotic (approximate) consensus under malicious model from the viewpoint of the so-called mean subsequence reduced (MSR) algorithms, which are known for the simplicity and scalability (e.g., [18, 9, 13, 19, 20, 21, 22]). This line of work has gained much attention in the last decade as the malicious model can be widely assumed for broadcasting networks [9], wireless sensor networks [3], and so on. A basic assumption in MSR algorithms is the knowledge regarding an upper bound on the maximum number of malicious agents among the neighbors; this bound is denoted by $f$ throughout this paper. Such a bound represents the level of caution assumed by the system operator and can be set based on past experience, with possibly some safety margin. Then, at each iteration, each node eliminates extreme values received from neighbors to avoid being influenced by such potentially faulty values. In particular, it removes the $f$ largest values and the $f$ smallest values from neighbors. Moreover, the graph property called robustness is shown to be critical for the network structure, guaranteeing the success of resilient consensus algorithms in static networks [12, 9] as well as time-varying networks [23]. A recent work [24] attempts to check robustness of given graphs using mixed integer linear programming. Nevertheless, such robustness requires the networks to be relatively dense and complex. Therefore, how to enhance resilience of more sparse networks without changing the original network topologies has become an urgent problem.

There are several directions for developing solutions to tackle this problem. In [25], the authors improved the graph robustness by introducing trusted nodes, which are assumed to be fault-free with extra security measures. They also provided another alternative method [26] to enhance the graph robustness by introducing different types of nodes in the network and by assuming that the attackers can only compromise a certain type of nodes. On the other hand, the works [27, 28] pursue approaches based on detection of malicious agents in the network. Compared to MSR algorithms, which do not have such detection capabilities, the algorithms are applicable to more sparse networks with the same tolerance of adversaries. Furthermore, in [10], by introducing multi-hop communication in MSR algorithms, the authors solved the approximate Byzantine consensus problem with a weaker condition on network structures compared to that derived under the one-hop communication model [13]. In [29], the authors tackled the same problem under asynchronous updates based on rounds, which is different from the asynchrony setting used in this paper (see the discussions in Section VI). The work [30] studied Byzantine binary consensus under the local broadcast model (malicious model) using a flooding algorithm, where nodes relay their values over the entire network.

Multi-hop communication techniques are commonly used in the areas of wireless communication [31] and computer science [2]. Such techniques are also used for consensus problems in many works. In [32], a multi-hop relay technique is introduced in the consensus problem to increase the speed of consensus forming. In [33], a similar method based on multi-hop relay is developed to solve the global leader-following consensus problem. Moreover, application of multi-hop communication in wireless sensor networks from the viewpoint of control is investigated in [34]. It is clear that with multi-hop communication, each node can have more information for updating compared to the one-hop case. Thus, the network may have more resilience against adversary nodes. Yet, only few works have looked into resilient consensus with multi-hop communication. As mentioned earlier, the work [10] is restricted to the Byzantine adversary case. To the best of our knowledge, resilient consensus with multi-hop communication under malicious attacks still remains as an open problem. Moreover, for many applications of multi-agent systems, time delays in the communication among agents can happen naturally [35], [36]. Especially, in the multi-hop communication setting, the length of time delays should increase as the messages are relayed by more agents. It is hence of significant importance to extend our algorithm to the case of asynchronous updates with time delays. We must note that such a case is not considered in [10] and [30].

The main contribution of this paper can be outlined as follows. Inspired by the definition of graph robustness of [9], we extend this notion to the multi-hop setting and name it as robustness with $l$ hops. Specifically, we formally characterize the ability of normal nodes to be influenced by normal multi-hop neighbors outside a given node set in the malicious environment. Furthermore, we provide analysis for the properties of the new notion of robustness.

Unlike in the case with one-hop communication, the MSR algorithm in the multi-hop case may not exclude all the possible effects from malicious nodes if each normal node just eliminates the $f$ largest and the $f$ smallest received values. Since a malicious node can manipulate not only its own value but also the values it relays, such nodes can produce more than $f$ false values even if there are at most $f$ malicious nodes. To completely exclude the effects from malicious nodes, we propose the multi-hop weighted mean subsequence reduced (MW-MSR) algorithm. Normal nodes using the MW-MSR algorithm will exclude the extreme values which are produced precisely by $f$ multi-hop neighbors. To realize this trimming capability in the multi-hop setting requires the notion of message cover, which represents the set of nodes intersecting with a given set of different message paths.

In this paper, we consider the malicious model, which is suitable for broadcast network and is different from the Byzantine model studied in [10]. Then we derive necessary and sufficient graph conditions based on the new notion of robustness with $l$ hops for the proposed MW-MSR algorithms to achieve resilient consensus under synchronous updates and asynchronous updates with time delays in the communication. Moreover, we present examples to illustrate how multi-hop communication helps to improve graph robustness without changing the network topology. As a side result, we prove that for the case of unbounded path length in message relaying, our graph condition is equivalent to the necessary and sufficient graph condition for binary consensus under malicious attacks studied in [30].

The rest of this paper is organized as follows. In Section II, we outline preliminaries on graphs and the system model. In Sections III and IV, we present the MW-MSR algorithm and define graph robustness with multi-hop communication, respectively. Then in Sections V and VI, we derive tight graph conditions under which the MW-MSR algorithms guarantee resilient asymptotic consensus under synchronous and asynchronous updates, respectively. In Section VII, we provide some properties of the new robustness and in Section VIII, we present examples to demonstrate that multi-hop communication can improve robustness of graphs in general. Lastly, in Section IX, we conclude the paper. A preliminary version of this paper appeared as [37]. The current paper contains all the proofs of the theoretical results, further discussions, as well as more extensive simulations.

In this section, we provide preliminaries on the network models and introduce the basic settings for the resilient consensus problems studied in this paper.

In this section, we introduce the multi-hop weighted MSR (MW-MSR) algorithm, which is designed to solve the resilient consensus problem under the multi-hop setting. We first introduce the notion of message cover which plays a key role in the trimming function of our MSR algorithm. Then we outline the structure of the MW-MSR algorithm and provide examples to illustrate the idea behind the algorithm.

The notion of message cover [10] is crucial in the update rule of our algorithm to be proposed in this section. It evaluates the effects of adversary nodes that can possibly manipulate the updates of normal nodes in a multi-hop communication setting. Its formal definition is given as follows.

As a simple example, consider the set $\mathcal{M}$ of paths connecting node $i$ to node $j$ which do not overlap. Then, its message cover must contain at least one node per path. Clearly, there may be multiple minimum message covers if the paths are of length greater than three.

Now, we are ready to introduce the structure of the synchronous MW-MSR algorithm in Algorithm 1. Note that the one-hop version of the MW-MSR algorithm (i.e., with $l=1$) is equivalent to the W-MSR algorithm in [9]. However, we can see that the difference between the MW-MSR algorithm and the W-MSR algorithm mainly lies in the trimming function in step 2 when $l\geq 2$. For general MSR algorithms of one-hop communication, the essential idea for the normal nodes to avoid being affected by adversary nodes is that each normal node $i$ will exclude the effects from $f$ neighbors with extreme values (possibly sent by faulty nodes). This can guarantee that values outside the safety interval will not be used by any normal node at any time step. In the one-hop case, for each normal node $i$, the number of values received from such $f$ neighbors is exactly $f$, i.e., node $i$ will trim away $f$ largest and $f$ smallest values at each step. This is because each neighbor sends only one value of its own to node $i$ at each step under the typical assumptions made in MSR-related works [9], [13].

Under the multi-hop setting, the situation changes significantly even if we assume that each node can only send out one value of its own to its neighbors at each step. Since each node relays the values from different neighbors, normal node $i$ can receive more than one value from one direct neighbor. Thus, in the MW-MSR algorithm, normal node $i$ cannot just trim away $f$ largest and $f$ smallest values at each step. Instead, it needs to trim away the largest and smallest values from exactly $f$ nodes within $l$ hops away, which is the generalization of the essential idea in the one-hop W-MSR algorithm.

To characterize the number of the extreme values from exactly $f$ nodes for node $i$, the notion of minimum message cover (MMC) is designed. Intuitively speaking, for normal node $i$, $\overline{\mathcal{R}}_{i}[k]$ and $\underline{\mathcal{R}}_{i}[k]$ are the largest sized sets of received messages containing very large and small values that may have been generated or tampered by $f$ adversary nodes, respectively. Here, we focus on how $\underline{\mathcal{R}}_{i}[k]$ is determined, as $\overline{\mathcal{R}}_{i}[k]$ can be obtained in a similar way. When the cardinality of the MMC of set $\underline{\mathcal{M}}_{i}[k]$ is no more than $f$, node $i$ simply takes $\underline{\mathcal{R}}_{i}[k]=\underline{\mathcal{M}}_{i}[k]$. Otherwise, node $i$ will check the first $f+1$ values of $\underline{\mathcal{M}}_{i}[k]$, and if the MMC of these values is of cardinality $f$, then it will check the first $f+2$ values of $\underline{\mathcal{M}}_{i}[k]$. This procedure will continue until for the first $f+h$ ($h\geq 1$) values of $\underline{\mathcal{M}}_{i}[k]$, the MMC of these values is of cardinality $f+1$. Then $\underline{\mathcal{R}}_{i}[k]$ is taken as the first $f+h-1$ values of $\underline{\mathcal{M}}_{i}[k]$. After sets $\overline{\mathcal{R}}_{i}[k]$ and $\underline{\mathcal{R}}_{i}[k]$ are determined, in the control input $u_{i}(k)$ computed by (4) in step 3, values in these sets are excluded. Note that this control is consistent with the one in (1) when $f=0$.

We also illustrate the determination of such subsets through a simple example. Consider the network in Fig. 1 with initial states $x[0]=[2\ 4\ 100\ 8\ 10]^{T}$, where node 3 is set to be malicious ($f=1$) and constantly broadcasts the value 100 as its own value as well as those in the relayed messages. We look at node 1 at time $k=0$ and drop the time index $k$. In the one-hop version of the MW-MSR algorithm, the input for node 1 is $\{x_{1},x_{2},x_{5},x_{3}\}$, and it chooses $\overline{\mathcal{R}}_{1}[0]=\{x_{3}=100\}$ and $\underline{\mathcal{R}}_{1}[0]=\emptyset$ in step 2 of the algorithm (since the value $x_{1}$ is the smallest in the input).

In the two-hop version of the MW-MSR algorithm, node 1 receives the state values $x_{2},x_{3},$ and $x_{5}$ directly from nodes 2, 3, and 5, respectively. Moreover, it receives the relayed values of node 4 through nodes 2, 3, and 5, denoted by $x_{4}^{2},x_{4}^{3},$ and $x_{4}^{5}$. Then the sorted input for node 1 is $\{x_{1},x_{2},x_{4}^{2},x_{4}^{5},x_{5},x_{4}^{3},x_{3}\}$, and node 1 checks the MMC of the subset of the largest values starting from the $(f+1)$th value (since the values before the $f$th one are definitely removed by node 1). First, it evaluates $\{x_{4}^{3},x_{3}\}$, and the MMC of this message set is the node set $\{3\}$ with cardinality 1. Then, it evaluates $\{x_{5},x_{4}^{3},x_{3}\}$ and the MMC of this message set can be found to be the node set $\{3,5\}$ with cardinality 2, which is bigger than $f=1$. As a result, node 1 confirms that $\{x_{4}^{3},x_{3}\}$ is the largest sized set of the large values that may have been generated or tampered by $f$ adversary nodes. Therefore, node 1 chooses $\overline{\mathcal{R}}_{1}[0]=\{x_{4}^{3}=100,x_{3}=100\}$ and $\underline{\mathcal{R}}_{1}[0]=\emptyset$ in step 2 of the algorithm.

In this paper, the key question to be addressed is, under what conditions on the network can the above algorithm achieve resilient asymptotic consensus? Our approach is to develop a generalization of the results and analysis of the one-hop case. In particular, this necessitates us to extend the notion of graph robustness by taking account of multi-hop communication. This is carried out in the next section.

In this section, we discuss the notion of graph robustness. This notion was first introduced in [9], which corresponds to the one-hop case. We provide its multi-hop generalization, which plays a crucial role in our resilient consensus problem.

As in the definition of robustness for the one-hop case [9], we start with the definition of $r$-reachability. Specifically, when the communication is only one-hop, a node set is said to be $r$-reachable if it contains at least one node that has at least $r$ incoming neighbors outside this set. This notion basically captures the capability of a set to be influenced by the outside of the set when the nodes apply the MSR algorithms with parameter $r-1$.

In generalizing this notion to the case of multi-hop communication, it is crucial to extend the above-mentioned capability. In particular, the influence from the outside of the set may come from remote nodes and are not restricted to direct neighbors. With a slight change, in the multi-hop setting, we define the $r$-reachability as follows.

Intuitively speaking, for any set $\mathcal{F}\subset\mathcal{V}$ and for node $i\in\mathcal{V}_{\text{1}}$ to have the above-mentioned property, there should be at least $r$ source nodes outside $\mathcal{V}_{\text{1}}$ and at least one independent path of length at most $l$ hops from each of the $r$ source nodes to node $i$, where such a path does not contain any internal node from the set $\mathcal{F}$. It is clear that for the one-hop case, to count the independent paths simply becomes to count the in-neighbors.

As an example, consider the graph in Fig. 2(a), where the two node sets $\mathcal{V}_{1}$ and $\mathcal{V}_{2}$ are taken as indicated and the set $\mathcal{F}=\{j\}$. Here, node $i\in\mathcal{V}_{1}$ has two independent paths of at most two hops originating from the nodes outside $\mathcal{V}_{1}$ with respect to the set $\mathcal{F}$. In contrast, in a similar graph shown in Fig. 2(b), such a property is lost and node $i$ has only one path from the outside of $\mathcal{V}_{1}$ w.r.t. the set $\mathcal{F}$.

Now, we are ready to generalize this notion to the entire graph and define $r$-robustness and $(r,s)$-robustness with $l$ hops as follows.

Generally, robustness of a graph increases as the relay range $l$ increases. We will illustrate this point using the graphs in Fig. 3. Note that graph robustness with multi-hop communication needs to be checked for every possible set $\mathcal{F}$ satisfying the $f$-total model. In the context of this paper, we are interested to check $(r,s)$-robustness under $(r-1)$-total model.

First, the graph in Fig. 3(a) is not $(2,2)$-robust with one hop since for the sets $\{1,2\}$ and $\{3,4\}$, none of the nodes has two in-neighbors outside the corresponding set. However, under the 1-total model, this graph is $(2,2)$-robust with $2$ hops. For instance, we first check the condition for the set $\mathcal{F}=\{1\}$. For sets $\{1,2\}$ and $\{3,4\}$, all of the nodes 1, 3 and 4 have two independent paths of at most two hops originating from the outside of the set with node 1 not being the internal node. After checking all the possible subsets of $\mathcal{V}$, one can confirm that this graph is $(2,2)$-robust with $2$ hops with respect to set $\mathcal{F}=\{1\}$. Since this graph is actually symmetric for each node, we can conclude that for the set $\mathcal{F}=\{v\}$ ($v=2,3,4$), this graph is $(2,2)$-robust with $2$ hops with respect to this set. Hence, this graph is $(2,2)$-robust with $2$ hops.

Next, we look at the graph in Fig. 3(b). When $l=1$, this graph is $(2,2)$-robust with $1$ hop but not $(3,3)$-robust with $1$ hop. When $l=2$, it becomes $(3,3)$-robust with $2$ hops. It is further noted that the level of robustness is constrained by the in-degrees of the nodes. In the graph of Fig. 3(b), each node has four incoming edges. As a result, for $r\geq 4$, this graph cannot be $(r,s)$-robust with any number of hops. We elaborate more on this aspect in Section VII.

In this section, we analyze the MW-MSR algorithm under synchronous updates, i.e., each normal node will update its value using those received from all of its $l$-hop neighbors in a synchronous manner with other nodes at each time $k$.

In this section, we analyze the MW-MSR algorithm under asynchronous updates with time delays in the communication among nodes.

We employ the control input taking account of possible delays in the values from the neighbors as

where $x_{j}^{P}[k]$ denotes the value of node $j$ at time $k$ sent along path $P$ and $\tau_{ij}^{P}[k]\in\mathbb{Z}_{+}$ is the delay in this $(j,i)$-path $P$ at time $k$. The delays are time varying and may be different in each path, but we assume the common upper bound $\tau$ on any normal path $P$, over which all internal nodes are normal, as

Hence, each normal node $i$ becomes aware of the value of each of its normal $l$-hop neighbor $j$ on each normal $(j,i)$-path $P$ at least once in $\tau$ time steps, but possibly at different time instants [12]. Although we impose this bound on the delays for transmission of messages, the normal nodes need neither the value of this bound nor the information that whether a path $P$ is a normal one or not.

The structure of the asynchronous MW-MSR algorithm can be outlined as follows. At each time $k$, each normal node $i$ chooses to update or not. If it chooses not to update, then it keeps its value as $x_{i}[k+1]=x_{i}[k]$. Otherwise, it uses the most recently received values of all its $l$-hop neighbors on each $l$-hop path to update its value using the MW-MSR algorithm in Algorithm 1. Like the one-hop MSR algorithm, if node $i$ does not receive any value along some path $P$ originating from its $l$-hop neighbor $j$ (i.e., the crash model), then node $i$ will take this value on path $P$ as an empty value and will discard this value when it applies the WM-MSR algorithm. As we discussed earlier in Section II-E, in the asynchronous case also, manipulating message paths is equivalent to manipulating message values only and hence can be disregarded in our analysis.

Let $D[k]$ be a diagonal matrix whose $i$th entry is given by $d_{i}[k]=\sum_{j=1}^{n}a_{ij}[k].$ Then, let the matrices $A_{\gamma}[k]\in\mathbb{R}^{n\times n}$ for $0\leq\gamma\leq\tau$ and $L_{\tau}[k]\in\mathbb{R}^{n\times(\tau+1)n}$ be given by

and $L_{\tau}[k]=\Big{[}D[k]-A_{0}[k]\medspace-A_{1}[k]\medspace\cdots\medspace-A_{\tau}[k]\Big{]}$, respectively. Note that the summation of each row of $L_{\tau}[k]$ is zero. The delay $\tau_{ij}[k]$ will be set to be one of the delays $\tau_{ij}^{P}[k]$ corresponding to the normal paths as we discuss further later.

Now, the control input can be expressed as

where $z[k]=[x[k]^{T}x[k-1]^{T}\cdots x[k-\tau]^{T}]^{T}$ is a $(\tau+1)n$-dimensional vector for $k\geq 0$ and $L_{\tau}^{N}[k]$ is a matrix formed by the first $n_{N}$ rows of $L_{\tau}[k]$. Here, to simplify the discussion, we assume that $z[0]$ consists of the given initial values of the agents. Then, the agent dynamics can be written as