Resilient Randomized Quantized Consensus

arXiv:1710.06994v1 [cs.SY] 19 Oct 2017

Seyed Mehran Dibaji, Hideaki Ishii, and Roberto Tempo

Abstract—We consider the problem of multi-agent consensus
where some agents are subject to faults/attacks and might make
updates arbitrarily. The network consists of agents taking integervalued (i.e., quantized) states under directed communication
links. The goal of the healthy normal agents is to form consensus
in their state values, which may be disturbed by the non-normal,
malicious agents. We develop update schemes to be equipped by
the normal agents whose interactions are asynchronous and subject to non-uniform and time-varying time delays. In particular,
we employ a variant of the so-called mean subsequence reduced
(MSR) algorithms, which have been long studied in computer
science, where each normal agent ignores extreme values from
its neighbors. We solve the resilient quantized consensus problems
in the presence of totally/locally bounded adversarial agents
and provide necessary and sufficient conditions in terms of the
connectivity notion of graph robustness. Furthermore, it will
be shown that randomization is essential both in quantization
and in the updating times when normal agents interact in
an asynchronous manner. The results are examined through a
numerical example.

I. I NTRODUCTION
In recent years, studies on networked control systems with
an emphasis on cyber security have received a growing attention. Due to the use of general purpose networks in largescale control systems, security against malicious intrusions
is becoming a key issue. One of the fundamental problems
is the so-called resilient consensus, which is the multi-agent
consensus problem (e.g., [27], [33]) in the presence of agents
subject to faults and attacks. In such problems, non-faulty
agents collaborate with each other to attain global agreement
while the faulty agents may make updates arbitrarily, which
can affect the behavior of the normal agents. The resilient
versions of the consensus algorithms provide the means to
protect multi-agent systems from faults and cyber attacks in
applications such as autonomous mobile agents and sensor
networks.
More specifically, in resilient consensus problems, each
non-faulty (or normal) agent is assumed to be aware of only
local information available from its neighbors regarding their
states. In contrast, malicious agents may have more global
information regarding the behavior of normal agents, by even
exchanging information over links not present in the network.
The objective in these problems is to design distributed control
protocols for the normal agents to achieve consensus among
S. M. Dibaji is with the Department of Mechanical Engineering, Massachusetts Institute of Technology, Cambridge, MA 02139, USA. E-mail:
dibaji@mit.edu
H. Ishii is with the Department of Computer Science, Tokyo Institute of
Technology, Yokohama, 226-8502, Japan. E-mail: ishii@c.titech.ac.jp
R. Tempo is with CNR-IEIIT, Politecnico di Torino, 10129 Torino, Italy.
E-mail: roberto.tempo@polito.it
This work was supported in part by the JST CREST Grant No. JPMJCR15K3, by the CNR-JST International Joint Lab COOPS, and by JSPS
under Grant-in-Aid for Scientific Research Grant No. 15H04020.

themselves and to establish conditions under which such
resilient consensus can be attained.
Resilient consensus has a rich history in the area of distributed algorithms in computer science (see, e.g., [26] and the
references therein). It is however highlighted that many works
there deal with networks of complete graphs. This may be due
to the fact that agents in this area are often models of computer
terminals connected over wired networks, performing load
balancing through consensus algorithms. From the current
perspective of multi-agent consensus in systems and control,
it is of interest to find the minimum requirement on networks
to warrant resiliency against faults and attacks. In this paper,
we will address this fundamental issue in a problem setting
that is in accordance with the computer science literature.
In particular, we consider resilient consensus problems in
the setting where the agents take integer-valued states and
the underlying network for their communication is directed
and non-complete. Quantized consensus has been motivated
by concerns on limited capabilities in communications and
computations of the agents, and various studies have recently
been carried out for the case without any malicious agents
[1], [4], [6], [7], [16], [17], [19], [20], [22], [25], [29]. For
enhancing resiliency, we employ a distributed update scheme
in which each normal agent ignores its neighbors whose states
appear extreme and unsafe in the sense that they differ the
most from its own. By assuming that the maximum number
f of malicious agents in the network is known, each normal
agent neglects up to f largest and up to f smallest values
from its neighbors. Such update schemes are often called
mean subsequence reduced (MSR) type algorithms. We study
the problem for both synchronous and asynchronous updates
for the normal agents and obtain necessary and sufficient
conditions in the underlying network structure for the agents’
communication.
For resilient consensus in our problem setting, the critical
notion for network structures is called graph robustness. It is a
measure of connectivity within a graph and characterizes how
well groups within the network are connected via multiple
paths. It was first introduced by [24] for resilient consensus in
the real-valued states case with first-order agent dynamics and
then was further explored in [9], [37]. The resilient approach
has moreover been extended to networks with higher-order
agents. In [10], [13], we derived similar results for vehicle
agents having second-order dynamics. Furthermore, an MSRtype algorithm is constructed for the application of clock
synchronization in wireless sensor networks [21], where each
node is equipped with an update scheme of two states.
Our viewpoint has been motivated by the recent literature
in control on multi-agent systems and has led us to introduce
features in the update schemes and communication delays
different from those in computer science. It is evident that in

control, real-time aspects in algorithms have more significance.
On the other hand, the condition on graph structures may be
relaxed by following an approach based on fault detection
and isolation techniques; this will however require to equip
all agents with banks of observers (e.g., [30]), which may be
difficult to implement considering the limited computational
resources on the agents.
We emphasize that the proposed update schemes employ
probabilistic techniques, which turn out to be very important in
the implementation of our algorithms. For general references
on randomization-based algorithms in systems and control,
we refer to [35], [36]. Randomization is introduced for two
objectives. One is in quantization. Since the update schemes
involve iterative weighted averaging of integer-valued states,
the resulting real number must be rounded by a quantizer. We
employ quantizers that perform randomization. They have an
effect similar to dithering, commonly used in speech and video
processing, for controlling statistical properties introduced by
quantization noises [39]. It will be shown that deterministic
quantizers are not sufficient. Related phenomena have been
found in [1], [6], [7], [19] for quantized average consensus
problems over undirected graphs with no malicious agent.
The other part where randomization is utilized is in the updating times of the agents. This is sometimes called gossiping
(see, e.g., [20], [32], [36]), but has not been exploited in the recent studies of resilient consensus discussed above. Our novel
finding is that for asynchronous updates in the normal agents,
randomized updating is essential in establishing resilient consensus under the minimal robustness requirement in the agent
network. The intuitive reason is that due to gossipping, the
malicious agents have less information about the normal agents
and thus cannot coordinate their behaviors well to misguide
them. In particular, with randomization in updating times,
the necessary and sufficient condition coincides with that for
the synchronous counterpart. We will show some scenarios
under deterministic updates, where consensus fails on graphs
possessing sufficient connectivity for the synchronous updates
case.
Our results suggest that randomization is critical in resilient
consensus. We would like to mention an interesting connection
to computer science; for more details, see [8]. There, randomization is used as an important component for many algorithms
to enhance efficiency [28]. This has in fact been well explored
in the context of binary-valued consensus problems when
adversaries are present [26]. For example, under asynchronous
deterministic updates, even one agent halting its operation
can make it impossible for the system to reach consensus
[15]; however, the use of probabilistic techniques can relax
the situation [3]. Another example is the so-called Byzantine
general problem, where randomization is necessary to obtain
algorithms scalable in convergence times with respect to the
size of the networks [28], [31]. We note that our results can
be applied to the binary state case by simply restricting the
initial values to 0 and 1.
Regarding the interaction among agents, we consider two
cases where the communications are immediate and also those
which experience non-uniform and time-varying delays. In
both cases, we characterize the network structures in terms

of robustness and provide sufficient conditions and necessary
conditions, which sometimes coincide. It however becomes
clear that time delays bring further vulnerabilities into the
agent system. As a result, we find that additional connectivity
is necessary to achieve resilient consensus for both deterministic and probabilistic updating schemes. We show through a
numerical example how a malicious agent can exploit the delays in such a way that the normal agents become divided into
groups. However, without delays in communication, this type
of vulnerability can be prevented by means of randomization
as discussed above.
Furthermore, as a side result, we show that when no
malicious agent is present in the network (i.e., with f = 0),
the necessary and sufficient conditions in our main results
coincide, establishing the topological condition of having a
spanning tree in the network for quantized consensus. Though
this condition is well known in the literature of consensus, in
the particular problem setting of quantized states and directed
networks, the result is new to the best of our knowledge.
The paper is organized as follows: In Section II, we present
preliminary material and introduce the problem setting. Section III is devoted to the quantized consensus problem in
the presence of malicious agents when the update schemes
for the normal agents are synchronous. Then, in Section IV,
the asynchronous counterpart without any delay is analyzed,
where randomization in update times is proven to be useful.
In Section V, the problem is solved in the presence of delays
in communication among the agents. Further, Section VI
provides numerical examples to illustrate the effectiveness of
the proposed algorithms. Finally, in Section VII, we discuss
concluding remarks and future directions. This paper is an
expanded version of the conference papers [11], [12] and
contains the full proofs of the theoretical results with extended
discussions on the role of randomizations, the relations to the
literature in computer science, and the simulation results.
II. P RELIMINARIES

AND

P ROBLEM S ETUP

In this section, we first provide preliminary material on
graphs and then introduce the basic problem setting for the
resilient consensus problems studied in this paper.
A. Graph Theory Notions
In this section, we recall some concepts on graphs [27].
A weighted directed graph with n agents is defined as a
triple G = (V, E, A) with the set of nodes V = {1, . . . , n},
the set of edges E ⊆ V × V, and the adjacency matrix A ∈
Rn×n . The edge (j, i) ∈ E means that node i has access to
the information of node j. We do not allow self-loops, that
is, (i, i) ∈
/ E. If each node has an edge to all other nodes, the
corresponding graph is said to be complete. For node i, the
set of its neighbors consists of all nodes which have directed
edges toward i, and it is denoted by Ni = {j : (j, i) ∈ E}. The
degree of node i is the number of its neighbors and is denoted
by di = |Ni |. If the edge (j, i) exists, the associated entry aij
in the adjacency matrix A is in (α, 1), and
aij is
Potherwise
n
zero, where 0 < α < 1. We assume that j=1,j6=i aij < 1.
Let L = [lij ] be the Laplacian matrix of G whose entries are

Pn
defined as lii = j=1,j6=i aij and lij = −aij for i 6= j. It is
clear that the sum of the elements of each row of the Laplacian
matrix is zero.
A path from node i1 to ip is a sequence of distinct nodes
(i1 , i2 , . . . , ip ), where (im , im+1 ) ∈ E for m = 1, . . . , p − 1.
If for all distinct nodes i and j, there is a path from i to j, the
graph is called strongly connected. A directed graph is said to
have a directed spanning tree if there is a node having a path
to every other node in the graph.
For the algorithms proposed in this paper, we characterize
topological properties of networks in terms of graph robustness. It measures the connectivity in a graph by showing
how well groups within the network are connected over
different paths. It was first introduced by [24] for analysis
of resilient consensus of real-valued first-order multi-agent
systems. Related works include [9] which studied the case
with delays in communication and [10], [13] for the case
of agents with real-valued second-order dynamics. We use
the more general notion of (r, s)-robust graphs, which plays
an important role to obtain a tight necessary and sufficient
condition.
Definition 2.1: The graph G = (V, E, A) is (r, s)-robust
(r, s < n) if for every pair of nonempty disjoint subsets
V1 , V2 ⊂ V, at least one of the following conditions holds:
1) XVr1 = V1 ,
2) XVr2 = V2 ,
3) |XVr1 | + |XVr2 | ≥ s,
where XVrℓ is the set of nodes in Vℓ having at least r incoming
edges from outside Vℓ . As the special case with s = 1, graphs
which are (r, 1)-robust are called r-robust.
The following lemma provides a better understanding of
robust graphs [23]. Here, ⌈y⌉ denotes the ceiling function and
gives the smallest integer value greater than or equal to y.
Lemma 2.2: For an (r, s)-robust graph G, the following hold:
(i) G is (r′ , s′ )-robust, where 0 ≤ r′ ≤ r and 1 ≤ s′ ≤ s,
and in particular, it is r-robust.
(ii) G is (r − 1, s + 1)-robust.
(iii) G has a directed spanning tree. Moreover a graph is 1robust if and only if it has a directed spanning tree.
(iv) r ≤ ⌈n/2⌉. Further, if r = ⌈n/2⌉, G is a complete graph.
Moreover, a graph G is (r, s)-robust if it is (r + s − 1)-robust.
It is clear that (r, s)-robustness is stronger than r-robustness.
The graph with seven nodes in Fig. 1 can be shown to
be (2, 2)-robust, but not 3-robust. In general, to determine
whether a given graph possesses a robustness property is
computationally difficult because the problem involves combinatorial issues. It is known that certain random networks are
robust when they are sufficiently connected [34], [40], [41].
B. Consensus among Integer-Valued Agents
In the remaining of this section, we give the problem
formulation of resilient consensus for the case without time
delays in the interactions among the agents.
Consider a network of agents cooperating over the directed
graph G = (V, E, A). Each agent applies a control rule
consisting of its neighbors’ state values to make updates by
xi [k + 1] = xi [k] + ui [k],

(1)

2
1

3
4

7
6

5

Fig. 1. A (2, 2)-robust graph with seven nodes.

where xi [k] and ui [k] represent the state and the control input
of agent i at time k.
To achieve consensus means that the agents converge to a
globally common value. In typical consensus problems, the
agents are real-valued (i.e., xi [k] ∈ R), and they approach
consensus asymptotically. A well-known approach for updating is to apply the weighted average of the relative state values
of the agent and its neighbors as
X
ui [k] =
aij [k](xj [k] − xi [k]),
(2)
j∈Ni

where aij [k] is the (i, j)th entry of the adjacency matrix A[k]
of the graph G[k] at time k.
Here, we consider the situation where limited communication and memory of the agents enforce them to take integer
values. Hence, the states and the inputs are constrained as
xi [k] ∈ Z and ui [k] ∈ Z for i ∈ V.
In the update rule, we employ the quantization function Q :
R → Z to transform the real-valued input in (2) to an integervalued one. This is done in a probabilistic manner as [1]
(
⌊y⌋ with probability p(y),
Q(y) =
(3)
⌈y⌉ with probability 1 − p(y),
where p(y) = ⌈y⌉ − y, and the floor function ⌊y⌋ gives the
greatest integer less than or equal to y. Based on (2), the
quantized control input of agent i can be written as
X

ui [k] = Q
aij [k](xj [k] − xi [k]) .
(4)
j∈Ni

It is noteworthy that the probabilistic quantizer equipped on
each agent is independent and determines whether to choose
the floor or ceil function at each time. Thus, the control (4)
can be implemented in a distributed fashion. Probabilistic
quantizers have been studied in [1], [6], [7], [19] for average consensus of real-valued agent networks with quantized
communications. Moreover, it can be shown that probabilistic
quantization is equivalent to the well-known dithering [1],
which has a range of applications in digital signal processing.
In our problem setting, we also introduce asynchrony in the
updates. That is, at each time k, agent i may or may not make
an update by applying its control ui [k]. If an agent does not
update its value, it keeps its previous value, i.e., xi [k + 1] =
xi [k]. Denote by U[k] ⊂ V the set of agents that update their
values at time k. The agent system is said to be synchronous if
U[k] = V for all k, and otherwise it is asynchronous. It is noted

that the control in (4) already represents the asynchronous
case: If i ∈
/ U[k], then aij [k] = 0 for j ∈ Ni .
The objective of the agent network is to achieve global consensus among all agents in a probabilistic sense by applying
the possibly asynchronous local control input (4). In this work,
the network is assumed to have some misbehaving agents that
do not follow the control in (4). In the next subsection, we
provide the required notions to study this case. Note that
networks without any malicious agents form a special case;
for such normal networks, we obtain consensus conditions as
a direct consequence of the results obtained in this paper.
C. Resiliency Notions and Algorithm
We introduce notions related to malicious agents and consensus in the presence of such agents [9], [10], [24].
Definition 2.3: Agent i is called normal if it updates its state
based on the predefined control (4). Otherwise, it is called
malicious and may make arbitrary updates. The index set of
malicious agents is denoted by M ⊂ V.
The numbers of normal agents and malicious agents are
denoted by nN and nM , respectively. Also, the states for the
normal agents and malicious agents are given in vector forms
as xN [k] ∈ ZnN and xM [k] ∈ ZnM , respectively.
In the agent dynamics in (1), the control inputs for the
normal agents are given by (4) while the malicious agents can
choose their control arbitrarily, and hence ui [k] for i ∈ M are
left unspecified at this point. Thus, the update rules for the
agents can be written in the following form:

 
Q P
w
[k]x
[k]
if i ∈ V \ M,
j
j∈Ni ∪{i} ij
xi [k + 1] =

xi [k] + ui [k]
if i ∈ M.
(5)

Here, we have W [k] = (wij [k]) = I − L[k], where L[k] is
the Laplacian matrix associated with the graph G[k]. From the
definition of the Laplacian matrix, it follows that W [k] is row
stochastic, that is, all entries are nonnegative and each row
sum is equal to one; moreover, each positive entry of W [k]
is lower bounded by α. Thus, each normal agent makes an
update by a quantized convex combination of its neighbors’
state values.
With respect to the number of misbehaving agents in the
network, we assume that an upper bound denoted by f is
known to all agents. More precisely, we consider the two cases
defined below.
Definition 2.4: The network is said to be f -total malicious
if the number nM of faulty agents in the entire network is
at most f , i.e., nM ≤ f . On the other hand, the network is
called f -local malicious if for each normal agent i ∈ V \ M,
the number nM of faulty agents in its neighborhood is at most
f , i.e., |M ∩ Ni | ≤ f .
We now introduce the notion of resilient consensus for the
network of probabilistic quantized agents in the presence of
misbehaving agents.
Definition 2.5: If for any initial states, any malicious inputs, and any possible set of malicious agents, the following
conditions are met, then the network is said to reach resilient
quantized consensus:

1) Safety condition: For each set of initial values of the
normal agents, there exists a set S such that for all normal
agents i ∈ V \ M, it holds that xi [k] ∈ S for k ∈ Z+ .
2) Agreement condition:
There exists a finite time ka ≥ 0

such that Prob xN [ka ] ∈ CnN | x[0] = 1, where the
consensus set CnN is defined as
CnN = {x ∈ ZnN | x1 = · · · = xnN }.
Next, we outline the algorithm employed for achieving consensus in the presence of misbehaving agents. The algorithm
is the quantized version of the weighted mean subsequence
reduced (W-MSR) algorithm studied in [9], [24] and thus will
be referred to as the QW-MSR algorithm. Using similar ideas,
resilient consensus of second-order agent networks has been
studied as well [10], [13].
Algorithm 2.6 (QW-MSR Algorithm):
1) At each time step k, if the normal agent i makes an update
in its value, i.e., i ∈ U[k], then it receives the state values
of its neighbors j ∈ Ni and sorts them in a descending
order.
2) If there are less than f agents which have state values
strictly larger than xi [k], then the normal node i ignores
the incoming edges from those agents. Otherwise, it
ignores the incoming edges from f agents which have
the largest state values. Similarly, if there are less than f
agents which have state values strictly smaller than xi [k],
then node i ignores all incoming edges from these nodes.
Otherwise, it ignores the f incoming edges from those
which have the smallest values.
3) Apply the update rule (5) by substituting aij [k] = 0 for
all edges (j, i) which are neglected in step 2.
The main feature of this algorithm lies in its simplicity.
Each normal node ignores the information received from its
neighbors which may be misleading. The normal agents do not
make attempts to identify the malicious agents in the network.
In particular, it always ignores up to f edges from neighbors
whose values are large, and f edges from neighbors whose
values are small. As we will see, in applying the algorithm,
there is no need for information more than that of each agent’s
neighbors and the upper bound f for the number of malicious
agents. The underlying graph G[k] at time k is determined by
the edges not ignored by the agents. The adjacency matrix
A[k] and the Laplacian matrix L[k] at time k are determined
accordingly.
The assumption on the number f of malicious agents in
the network is standard in the problem setting of computer
science (e.g., [26]). It will become clear that, for the MSR
algorithm to function properly, the maximum f depends on
the size and the topology of the given network. There is a
history of results showing the maximum number of malicious
agents that can be tolerated in MSR-type algorithms when the
network is a complete graph; see, for example, [3], [26], [31].
Our main results are significant in that we obtain tight bounds
on f through the necessary and sufficient conditions expressed
in terms of robust graphs.
The first problem studied in this paper is formulated as
follows: Under the f -total malicious model, find a condition

on the network topology such that the normal agents reach
resilient quantized consensus almost surely using the QWMSR algorithm outlined above. We consider the case of
synchronous updates and asynchronous updates separately
in Sections III and IV. Then, in Section V, we study the
more realistic situation when time delays are present in the
communication among agents.
III. R ESILIENT C ONSENSUS FOR S YNCHRONOUS
N ETWORKS
We provide the solution to the resilient consensus problem
for the synchronous update case. The result will be given in the
form of a necessary and sufficient condition on the underlying
network structure.
A. Characterization Based on Robust Graphs
We are ready to present the main result of this section.
The following theorem provides a necessary and sufficient
condition for resilient quantized consensus for synchronous
updating times. It shows that robustness in the network is a key
property to guarantee sufficient connectivity among the normal
agents to avoid being misguided by the malicious agents. Let
S be the interval given by


S = min xN [0], max xN [0] ,
(6)

where the minimum and maximum are taken over all entries
of vectors. This set will be shown to be the safety interval.
Theorem 3.1: Under the f -total malicious model, the network of quantized agents with the QW-MSR algorithm reaches
resilient quantized consensus almost surely with respect to the
randomized quantization if and only if the underlying graph
is (f + 1, f + 1)-robust.
To establish quantized consensus in this probabilistic setting, we follow the arguments introduced in [20]. In the
following, we restate Theorem 2 from this reference with
minor modifications to accommodate our problem setup.
Lemma 3.2: Consider the network of quantized agents
interacting over the graph G through the QW-MSR algorithm.
Suppose that the following three conditions are met for the
normal agents:
(C1) There exists a set S such that for each normal agent i,
xi [k] ∈ S for all k ∈ Z+ and all xN [0].
(C2) For each state x[k] = x0at time k, there exists a finite
time kx such that Prob xN [k + kx ] ∈ CnN | x[k] =
x0 > 0.
(C3) If x[k] ∈ CnN , then x[k ′ ] ∈ CnN , ∀k ′ > k.
Then, the network reaches quantized consensus almost surely.
Remark 3.3: The result in [20] holds for a general class of
algorithms, but there it is given for the case of quantized average consensus. In the lemma above, it is adapted to the regular
quantized consensus. In the proof of Theorem 3.1, we show
that the QW-MSR algorithm satisfies the conditions (C1)–(C3)
in the lemma when it is applied to robust graphs. Intuitively, if
the algorithm satisfies these conditions for normal agents, then
the scenarios for reaching consensus occur infinitely often with
high probability. This is because the probability for such an

event to occur is positive based on the condition (C2). Then,
as soon as normal agents reach consensus, they do not change
their values by (C3).
Proof of Theorem 3.1: (Necessity) If the graph is not (f +
1, f + 1)-robust, the set of its nodes includes two disjoint
and nonempty subsets V1 and V2 that do not meet any of the
three conditions in Definition 2.1. Thus, for i = 1, 2, the total
number of nodes in Vi that have at least f + 1 incoming edges
from V \Vi is less than f +1. Here, we take all malicious nodes
to be in the sets XVf1+1 and XVf2+1 . It then follows that V1 \
XVf1+1 and V2 \ XVf2+1 are two disjoint and nonempty subsets
of normal agents. Now, assign a, b and ⌊(a + b)/2⌋ to the
nodes in V1 , V2 , and the rest of the nodes, respectively, where
a, b ∈ Z and a < b − 1. Suppose that the malicious agents do
not change their state values. Then, the normal agents in V1
and V2 will ignore all of their neighbors that have different
values from themselves and they will stay at their states. Thus,
the normal agents contained in V1 \ XVf1+1 and V2 \ XVf2+1
remain at the values a and b at all times. This implies that the
agreement condition cannot be met.
(Sufficiency) We must show that by applying QW-MSR to
the network of f -total model, the conditions (C1)–(C3) in
Lemma 3.2 hold. First, we prove (C1), which is the safety
condition. Denote the minimum and maximum values of the
normal agents at time k by
x[k] = min xN [k], x[k] = max xN [k].

(7)

In the network, there are at most f malicious agents, and, at
each time step, each normal agent removes the values of at
most 2f neighbors, f from above and f from below.
 Hence,
those faulty agents with values outside the interval x[k], x[k]
are all ignored at each time step. In other words,
 each normal

agent i is affected by only the values within x[k], x[k] . It
thus follows that the value of the normal agent i in the update
rule (5) is upper bounded by
m
l X
wij [k]xj [k]
xi [k + 1] ≤
j∈Ni ∪{i}

≤

l

X

j∈Ni ∪{i}

m 

wij [k]x[k] = x[k] = x[k].

This implies that x[k + 1] ≤ x[k], that is, x[k] is a monotonically nonincreasing function of time. Likewise, agent i’s value
can be bounded from below as
k
j X
wij [k]xj [k]
xi [k + 1] ≥
j∈Ni ∪{i}

≥

j

X

j∈Ni ∪{i}

k 

wij [k]x[k] = x[k] = x[k].

Thus, we have x[k + 1] ≥ x[k], which shows that x[k] is a
monotonically nondecreasing function of time. Consequently,
we conclude
that for the normal agent i, its state satisfies

xi [k] ∈ x[k], x[k] ⊂ S for all k with the interval S given in
(6). Thus, (C1) is established.
Next, we prove (C2) in Lemma 3.2. Since x[k] and x[k]
are contained in S and are monotone, there is a finite time kc
such that they both reach their final values with probability

1. Denote the final values of x[k] and x[k] by x∗ and x∗ ,
respectively. Now, to conduct a proof by contradiction, we
assume x∗ < x∗ . Denote by X1 [k] the set of all agents
including the malicious ones at time k ≥ kc with state values
equal to x∗ or larger. Likewise, denote by X2 [k] the set of
agents whose states are equal to x∗ or smaller. That is,

X1 [k] = i ∈ V : xi [k] ≥ x∗ ,

(8)
X2 [k] = i ∈ V : xi [k] ≤ x∗ .

We show that with positive probability, the normal agents in
X1 [k] decrease their values, and the normal agents in X2 [k]
increase their values at the next time step. These two sets
X1 [k] and X2 [k] are nonempty and disjoint by assumption.
Moreover, the underlying graph is (f + 1, f + 1)-robust. Thus,
one of the conditions in Definition 2.1 must be fulfilled. In
particular, there always exists a normal agent i either in X1 [k]
or X2 [k] with (f + 1) edges from V \ X1 [k] or V \ X2 [k],
respectively. Without loss of generality, we suppose that the
normal agent i in X1 [k] has this property. Its value clearly
is xi [k] = x∗ . In step 2 of QW-MSR, it neglects at most f
values from V \X1 [k]. Hence, it makes an update using at least
one agent from its neighbors whose value is smaller than x∗ .
In step 2 of QW-MSR, it also neglects all values larger than
x∗ since there are at most f such values coming from the
malicious agents. Thus, by the update rule (5), we write
xi [k + 1] ≤ Q (1 − α)x∗ + α(x∗ − 1)) = Q(x∗ − α). (9)
Here, by (3), the quantizer output takes the truncated value
as Q(x∗ − α) = x∗ − 1 with probability 1 − α. Thus, with
positive probability, we have
xi [k + 1] ≤ x∗ − 1.

This indicates that with positive probability, one of the normal
agents taking the maximum value x∗ decreases its value by
at least one. Similarly, if the normal agent i is in X2 [k], then
with positive probability, it chooses the ceil quantization, in
which case its value will increase above x∗ .
We must next show that with positive probability, none of
the normal agents in V \ X1 [k] enters X1 [k + 1] at the next
time step. If the normal agent i at time k is in V \ X1 [k],
it is upper bounded by x∗ − 1. According to the update rule
(5), the inequality (9) holds in this case as well. Thus, with
probability 1 − α, agent i does not come into X1 [k + 1]. The
same steps show that any of the normal agents in V \ X2 [k]
will not go into X2 [k + 1] with positive probability.
From the above, we conclude that for any k ≥ kc + nN , the
number of normal agents in one of the sets X1 [k] and X2 [k] is
zero with positive probability because there are only nN such
agents. This is a contradiction and proves (C2).
In the last step, we have to show (C3) in Lemma 3.2,
i.e., when all normal agents reach agreement and go inside
CnN , they stay there from that time on. Assume that the
normal agents have reached the common value x∗ . Since the
maximum number of malicious agents is f , all such agents j
with values xj [k] 6= x∗ are ignored by the normal agents.
Thus, in the third step of QW-MSR, when they apply the
update rule (5), xi [k + 1] = x∗ , ∀i ∈ V \ M. We have thus
shown (C3), and this concludes the proof.


The (f + 1, f + 1)-robustness as a necessary and sufficient
condition is consistent with the resilient consensus problems
in [24] and [13] for the real-valued agent cases with firstorder and second-order dynamics, respectively. However, these
works consider consensus in real-valued agent networks and
establish convergence in an asymptotic fashion; moreover, the
updating rules there are without any randomization. This paper
studies agents taking quantized values and the convergence is
in finite time in a probabilistic sense.
It is noted that our approach can be applied to the binaryvalued consensus case [3], [15], [26], [31]. As long as the
initial states of all agents are restricted to 0 and 1, the safety
interval in (6) indicates that the normal agents’ values will
remain binary and come to agreement eventually. This fact
remains true for all results presented in this paper.
Remark 3.4: Analysis on the convergence rate for quantized
consensus problems has recently gained attention, where upper
bounds on the worst-case convergence times are derived with
respect to the number n of agents. In [20], some common
classes of agent networks are considered while further studies
on static and time-varying networks can be found in [14], [42].
It is however noted that these works deal with the problem of
average consensus where the underlying graph is undirected.
The paper [5] carries out an analysis for average quantized
consensus over directed graphs based on a specific algorithm
employing additional dynamics in each agent. In contrast to
these works, in our resilient consensus problem, the algorithm
is synchronous, but the network is directed and moreover
switches according to the MSR mechanism. Hence, for the
convergence time analysis of the algorithm, it seems difficult to
apply existing results. This problem is left for future research.
We now consider the special case when no malicious agent
is present in the network (i.e., with f = 0). Then, the QWMSR algorithm reduces to the update rule in (5) with a
static matrix W . The following corollary of Theorem 3.1
demonstrates that in this case, to achieve quantized consensus,
it is necessary and sufficient that a spanning tree exists in the
network, which is the well-known topological condition for
multi-agent consensus when the states take real values [27].
Corollary 3.5: When no malicious agent is present, the
network of quantized agents based on the update rule (5)
reaches quantized consensus almost surely with respect to the
randomized quantization if and only if the underlying graph
has a directed spanning tree.
Proof : With f = 0, by Theorem 3.1, the necessary and
sufficient condition for reaching consensus in normal networks
is (1, 1)-robustness. Then, by Lemma 2.2 (iii), a graph is
(1, 1)-robust, or 1-robust, if and only if it has a directed
spanning tree.

In the literature of quantized consensus, to the best of our
knowledge, the above necessary and sufficient condition has
not been reported elsewhere. Related works include [29] which
established strong connectivity as a sufficient condition, and
[20], [22] which deal with undirected communications. In
contrast, we have studied the more general directed graphs.
The same condition appears in [5], but is for a specific class
of gossip-based time-varying networks. In Section V, we will
present further generalization for the case with delays in

1

n

2

Fig. 2. A line graph with no malicious agent fails to reach consensus with
ceil quantizers when the initial value for node i is taken to be its index i.

2
1

3

5

4

Fig. 3. A (2, 2)-robust graph which fails to reach consensus by using ceiling
quantization or floor quantization.

communication.

and X2 [k] have been introduced. It is shown that one of them
loses all normal agents in finite time steps almost surely. In
one of these sets, there is a normal agent i that has at least
f + 1 edges from nodes outside the set it belongs to. Now, if
agent i is in the set X1 [k] and if the quantization is always
based on ceiling, there is no guarantee that it goes out of
X1 [k + 1]. Likewise, if agent i is contained in X2 [k] and if
floor quantization is employed at all times, then this agent will
remain in X2 [k + 1].

IV. A SYNCHRONOUS N ETWORKS : E NHANCING
R ESILIENCE VIA P ROBABILISTIC U PDATES
In this section, we consider asynchronous update schemes.
We will highlight that asynchrony in the updates can create
weaknesses in the algorithm that can be exploited by the
malicious agents. However, we show that this problem can
be overcome by employing a probabilistic updating scheme.

B. Role of Probabilistic Quantization
Quantization is necessary in the update scheme (5) of
the agents for keeping their states to take integer values
from the weighted average of the neighbors’ states. In this
subsection, we show that randomization in the quantizers
plays an important role in the consensus problem. Similar
discussions can be found in, e.g., [1], [6], [7], [19], [20],
but are focused on average consensus over undirected graphs
without any malicious agents.
First, to show the limitation of deterministic quantization
even when no malicious agent is present in the network (i.e.,
f = 0), we use the line graph example in Fig. 2. Suppose
that in the update rules, the ceil quantizers Q(y) = ⌈y⌉ are
used instead of the probabilistic ones. Let agent i take an
initial value of xi [0] = i for all i. Then, we easily conclude
that the agents stay at their initial states for all times and
thus consensus is impossible. A similar argument holds for the
floor quantizer Q(y) = ⌊y⌋ by changing the initial values to
xi [0] = n − i. Note however that line graphs contain spanning
trees. It is clear that neither ceil nor floor is sufficient in such
examples and we need a combination of both with a suitable
switching mechanism. This can be achieved by means of the
probabilistic quantizers in (3).
Next, we provide an example with a malicious agent. The
network in Fig. 3 with five nodes is (2, 2)-robust. We set f = 1
and take agent 5 to be malicious. This agent keeps its value
unchanged from the initial time. The values of the agents are
initialized as x[0] = [2 2 2 3 5]T . Using ceil quantizers in
QW-MSR forces each normal agent to stay at its initial value,
and hence no consensus is reached. In this case, the malicious
agent 5 is ignored at all times since it is set to be the largest
value. It is interesting to notice that removal of node 5 from
the graph in Fig. 3 results in a graph with a spanning tree.
We can reach similar conclusions with floor quantization by
initializing the values as x[0] = [4 4 4 3 1]T .
At a more general level, we can explain the importance
of the probabilistic quantization in the proof of Theorem 3.1
as follows. There, two disjoint and nonempty subsets X1 [k]

A. Deterministic Update Scheme
Recall that the QW-MSR algorithm in Algorithm 2.6 is
applicable to the case of asynchronous update rules. The set of
normal agents updating at time k is represented by U[k]. When
no update is made, the control input simply becomes ui [k] = 0
and thus the state remains unchanged as xi [k + 1] = xi [k].
In the deterministic setting, we assume that each normal
agent i makes an update at least once in k̄ time steps, that is,
k+k−1
[

U[ℓ] = V \ M for k ∈ Z+ .

(10)

ℓ=k

On the other hand, the malicious agents need not follow these
schemes and may even be aware of the updates of the whole
network.
Now, we state a sufficient condition for deterministic asynchronous networks in terms of graph robustness, but with a
more restrictive requirement than that in Theorem 3.1.
Theorem 4.1: Under the f -total malicious model, the network of asynchronous quantized agents with the QW-MSR
algorithm satisfying (10) reaches resilient quantized consensus
almost surely with respect to the randomized quantization if
the underlying graph is (2f + 1)-robust.
The proof of Theorem 4.1 is skipped for now. In the next
section, we present a more general result for deterministic
asynchronous networks, from which the theorem above follows (see Theorem 5.1 and Remark 5.2).
It is noted that a (2f +1)-robust graph is also (f +1, f +1)robust by Lemma 2.2 (ii). This indicates that there is a gap
between Theorem 3.1 and Theorem 4.1 for the synchronous
scheme and the asynchronous scheme, respectively. This gap
originates from the fact that asynchrony in the updating times
creates more ways for malicious agents to deceive the normal
agents. This point is demonstrated through an example in the
next subsection.

(0, 1] in an i.i.d. fashion. That is, for agent i, at each time k,

1

6

2

5

3
4

Fig. 4. A complete graph which is (3, 3)-robust, but fails to reach consensus
under asynchronous updates when agents 1 and 2 are malicious.

B. Discussion on Synchronous versus Asynchronous
Now, we discuss why the sufficient condition for the case of
asynchronous normal agents is more restrictive than the case
of synchronous agents in the previous section.
Consider the 6-node complete graph depicted in Fig. 4. This
graph is (3, 3)-robust due to Lemma 2.2 (iv). In this graph,
agents 1 and 2 are taken to be malicious. They switch their
values according to xi [2m] = i and xi [2m + 1] = i + 6
for m ∈ Z+ . For each agent i, let’s assign xi [0] = i. Also,
assume that agents 3 and 4 make updates only at even time
steps (k = 2m) and agents 5 and 6 make updates only at
odd time steps (k = 2m + 1). By applying the QW-MSR
algorithm, we observe that with probability 1, agents 3 and
4 reach agreement among themselves (at either 3 or 4), and
agents 5 and 6 agree upon a different value (at either 5 or 6).
Here, although the underlying graph is complete, the agents
cannot reach consensus because the graph is not sufficiently
robust to have two malicious agents.
Using Lemma 2.2 (iv) and the above results, we note that,
with less than 4f + 1 nodes in the network, it is impossible
to reach consensus in f -total malicious models under asynchronous updates even when the graph is complete; there will
be some scenarios of updates and adversaries’ behaviors that
prevent it. However, when the normal agents make updates
synchronously, having a complete graph with 2f + 1 nodes is
sufficient to reach consensus.
We would like to tighten the topological condition for
asynchronous updates. As seen in the above example, since
the normal agents 3 and 4 make updates at time steps when the
normal agents 5 and 6 are in idle mode, the malicious agents
take advantage of this asynchrony and appear at different states
at the times of their updates. For instance, at the time of
updates, agents 3 and 4 receive values x1 [k] = 1 and x2 [k] = 2
from the malicious agents 1 and 2. Then, the values from
agents 1, 2, 5, and 6 are ignored.
Such an undesirable situation can be avoided, for example,
if there are chances that all normal agents simultaneously make
updates, even if they occur very seldom. This type of feature
in fact will allow us to obtain (f + 1, f + 1)-robustness as a
necessary and sufficient condition for resilient consensus. To
this aim, we make use of randomized update times.
C. Probabilistic Update Scheme
In the probabilistic setting, we assume that each normal
agent i makes an update at time k ≥ 0 with probability pi ∈



Prob i ∈ U[k] = pi , Prob i ∈
/ U[k] = 1 − pi .

(11)

Note that with such updates, the algorithm remains fully
distributed. Even the probabilities pi need not be identical.
An advantage of introducing randomization for the normal
agents is that the malicious agents cannot predict the update
times in advance. In this respect, randomization in update
times is utilized as a defensive means against potential conspiracy of the malicious agents. Moreover, there is always nonzero
probability that any normal agents in the system update their
states. This feature enables us to establish a stronger result
than that for the deterministic case.
The following theorem is the main result of this section.
It shows that for the probabilistic updating scheme, the requirement on graph robustness is the same as that for the
synchronous case in Theorem 3.1.
Theorem 4.2: Under the f -total malicious model, the network of randomly asynchronous quantized agents with the
QW-MSR algorithm satisfying (11) reaches resilient quantized
consensus almost surely with respect to the randomized quantization and updates if and only if the underlying graph is
(f + 1, f + 1)-robust.
Proof : (Necessity) This part follows from the necessity part
of Theorem 3.1 since the synchronous updating scheme is a
special case of asynchronous updating schemes.
(Sufficiency) We must show that the three conditions (C1)–
(C3) in Lemma 3.2 hold. This can be done as in the proof
of Theorem 3.1, and thus we provide only an outline for the
probabilistic asynchronous case considered here.
For (C1), it is enough to notice that the values x[k] and x[k]
as defined in (7) are bounded in the interval S in (6) and are
monotone. Furthermore, these facts imply that x[k] and x[k]
arrive at their final values x∗ and x∗ in some finite time kc
almost surely.
We show (C2) by contradiction and assume x∗ < x∗ . Take
the sets X1 [k] and X2 [k] as in (8). By assumption, these sets
are disjoint and nonempty. We have two claims at this point.
The first is that, at each k ≥ kc , a normal agent in at least
one of these sets goes out from the corresponding set at the
next time step with positive probability. This can be shown
because by (f + 1, f + 1)-robustness, there is a normal agent
i in either X1 [k] or X2 [k] which has at least f + 1 incoming
links from outside the set X1 [k] or X2 [k], respectively. In
the probabilistic asynchronous updating case, for this normal
agent i, the probability to update at this time k is positive.
The second claim is that with positive probability, none of the
normal agents outside Xj [k] enters Xj [k + 1] for j = 1, 2.
This can be proved similarly as in the first one. By these two
claims, we conclude that for any k ≥ kc + nN , one of the two
sets, X1 [k] or X2 [k], contains no normal agent with positive
probability, which is clearly a contradiction.
The condition (C3) holds as well since once all of the
normal agents arrive at consensus, whether a normal agent
makes an update or not, it will keep its state unchanged at the
consensus value.


V. R ESILIENCE

UNDER

D ELAYED C OMMUNICATIONS

Thus far, we assumed that the interactions among the
agents do not experience any time delay and the neighbors’
information can be transferred immediately. In this section,
we consider the more realistic situation where agents have
access to only delayed information of the neighbors’ states. We
demonstrate that the malicious agents can exploit the delays to
prevent consensus among the normal agents when the graph
is not sufficiently robust.
A. Problem Formulation and Algorithm
In the case with delayed information, the control input of
the normal agent i in (4) is given by
X

ui [k] = Q
aij [k](xj [k − τij [k]] − xi [k]) ,
(12)
j∈Ni

where the delays τij [k] are present in each communication
channel. They are assumed to be time varying, non-uniform,
and bounded, i.e., 0 ≤ τij [k] ≤ τ for some nonnegative
constant τ . Note that this bound τ need not be known to any
of the normal agents. As before, non-updating agents apply no
input, i.e., ui [k] = 0 with aij [k] = 0 for j ∈ Ni if i ∈
/ U[k].
For the malicious agent, in contrast, we assume that the
control input ui [k] can be arbitrary and may be based on the
current (non-delayed) state information of any agent in the
network.
To ease the problem formulation, we introduce the following
notations. Let D[k] be a diagonal matrix whose ith entry is
given by
n
X
aij [k].
(13)
di [k] =
j=1

Then, let the matrices Aℓ [k] ∈ Rn×n for 0 ≤ ℓ ≤ τ , and
Lτ [k] ∈ Rn×(τ +1)n , respectively, be given by
(
aij [k] if i 6= j and τij [k] = ℓ,
Aℓ [k] =
(14)
0
otherwise,
and


Lτ [k] = D[k] − A0 [k] −A1 [k] · · ·

−Aτ [k] .

Furthermore, let

Wτ [k] = In

0 ···




0 − Lτ [k].

Similarly to the usual Laplacian matrices, Lτ [k] has the
property that the sum of elements of each row is zero. Thus,
each row sum of Wτ [k] is one, and each non-zero entry of
Wτ [k] is lower bounded by some β ∈ (0, 1).
Finally, denote by z[k] ∈ Z(τ +1)n the extended state vector
containing the past states given by
T

z[k] = xT [k] xT [k − 1] · · · xT [k − τ ] .

The update rule for each agent i is based on the control
(12) for a normal agent. Meanwhile, the malicious agents can
choose their control arbitrarily and thus for them, we leave

ui [k] unspecified at the current stage. Consequently, the update
schemes for the agents can be written as
(
Q(eTi Wτ [k]z[k]) if i ∈ V \ M,
xi [k + 1] =
(15)
xi [k] + ui [k]
if i ∈ M,
where ei ∈ R(τ +1)n is the unit vector whose ith entry is 1
and the rest are zero. Thus, each agent makes an update by
a quantized convex combination of its neighbors’ state values
which may be delayed.
The objective of the agent network is to reach resilient
consensus among all agents by applying the local control rule
(12) with the probabilistic quantizers under the deterministic
update scheme (10). To this end, we again employ the QWMSR algorithm in Algorithm 2.6, but this time, we interpret
the neighbors’ states to be the delayed information available
at each update time k.
From the viewpoint of multi-agent systems in control, the
delay model in the input (12) is reasonable and commonly
adopted [33]. It uses the most recent information of the
neighbors available at the time of updates. In contrast, the
works [2], [38] from the computer science literature employ a
delay model based on the so-called rounds. An agent transmits
its value along with its current round, i.e., the number of
transmissions that it made so far. Updates are made at an
agent only after it receives the neighbors’ data with the
same round. This indicates that if there is one agent whose
transmission takes time, all of its neighbors would have to wait
before making the next update, which clearly slows down the
convergence of the overall system.
B. Robust Graph Conditions: Deterministic Updates
We are now in the position to state the main result of this
section. The theorem below establishes a sufficient condition
for resilient quantized consensus in the asynchronous setting
with delays and deterministic updating times. The randomized
counterpart will be given later.
Let Sτ be the interval given by


(16)
Sτ = min z N [0], max z N [0] ,

where the minimum and maximum are taken over all entries of
the vector z N [0] containing the initial values of normal agents.
This set will be shown to be the safety interval.
Theorem 5.1: Under the f -total malicious model, the network of quantized agents with delayed information and deterministic asynchronous update times in the asynchronous QWMSR algorithm reaches resilient quantized consensus almost
surely with respect to the randomized quantization if the
underlying graph is (2f + 1)-robust. Moreover, the safety
interval is determined by Sτ in (16).
The proof of this theorem is presented in the Appendix.
Remark 5.2: Theorem 5.1 is a generalized version of Theorem 4.1 where no delay is assumed with τ = 0. The proof
of Theorem 5.1 may appear similar to that of Theorem 3.1
for the synchronous problem. However, there are considerable
differences between them. One technical difference lies between the definitions of the two sets X1τ [k] and X2τ [k] and
those of X1 [k] and X2 [k] in Section III. As a consequence,

further discussions are required for showing that X1τ [k] and
X2τ [k] are nonempty for k ≥ kc , which is not the case in the
proof of Theorem 3.1. Notice that the sets X1τ [k] and X2τ [k]
do not include the malicious agents, while the sets X1 [k] and
X2 [k] there involve both normal and malicious agents. This
difference originates from the definitions of (2f + 1)- and
(f + 1, f + 1)-robust graphs. In fact, in the f -total model, we
see that the second term f + 1 in (f + 1, f + 1) guarantees
that at least one of the agents in X1 [k] or X2 [k] is normal and
has a sufficient number of incoming links for convergence.
However, (2f + 1)-robustness is a more local notion. Since
the worst-case behavior of the malicious agents happens in
the neighborhood of each normal agent, the sets X1τ [k] and
X2τ [k] are defined in this way.
Note that the networks with asynchrony and delays are
the generalized case of the synchronous networks without
time delays. Thus, for the necessary condition on the network
structure, the result of Theorem 3.1 is valid here. This fact is
stated as a proposition in the following.
Proposition 5.3: Under the f -total malicious models, if
the network of quantized agents with delayed information in
the QW-MSR algorithm reaches resilient quantized consensus
almost surely with respect to the randomized quantization, then
the underlying graph is (f + 1, f + 1)-robust.
C. Effect of Non-uniform Delays and Probabilistic Updates
Similarly to the discussion in Section IV-B, for networks
with delays, there is also a gap between the sufficient condition
in Theorem 5.1 and the necessary condition in Proposition 5.3.
We have seen in Section IV-C that using randomization can be
effective to obtain tighter results. In particular, randomization
enables the normal agents to have a chance to make updates at
the same time. This has facilitated us to obtain (f + 1, f + 1)robustness as a necessary and sufficient condition for resilient
consensus of asynchronous networks without delay.
However, when there are delays in the network, it seems
difficult to gain similar benefits through randomization. By
exploiting non-uniform delays, a malicious agent can appear
as having different states at the same time by different normal
agents. This is possible if the agent changes its value, but sends
its state with different delays. This means that randomization
in update times may not be enough in such cases to relax the
topological condition. We will examine this type of malicious
behavior in the numerical examples in the next section.
The following proposition gives a sufficient condition with
the same condition in terms of graph robustness as in the
deterministic case in Theorem 5.1.
Proposition 5.4: Under the f -total malicious model, the
network of randomly asynchronous quantized agents with
time-varying delayed information satisfying (11) in the QWMSR algorithm reaches resilient quantized consensus almost
surely with respect to the randomized quantization and updates
if the underlying graph is (2f +1)-robust. Moreover, the safety
interval is determined by Sτ in (16).
Proof : We must show that the three conditions (C1)–(C3)
in Lemma 3.2 hold. This can be done as in the proof of
Theorem 5.1. For the randomized updates considered here,

the only difference is in showing (C2). In the deterministic
scheme, each normal agent makes updates at least once in
each k̄ whereas in the probabilistic scheme the agents make
updates at each time step with probability pi > 0. This fact
reflects on the minimum k̄ · nN and nN steps for X1τ [kc ]
and X2τ [kc ] to become empty with positive probability in the
deterministic and probabilistic schemes, respectively.

The (2f + 1)-robustness as a sufficient condition is consistent with the resilient consensus problems in [9] and [13]
for the real-valued agent cases with first-order and secondorder dynamics, respectively. However, these works consider
consensus without any randomization in their updates. This
paper studies agents taking only quantized values and the
convergence is in finite time in a probabilistic sense.
D. Further Results
In what follows, we discuss a few extensions of our results
concerning agent systems with communication delays.
1) Normal Networks: We consider the special case when
no malicious agent is present in the network with f = 0.
Then, the QW-MSR algorithm reduces to the update rule
in (15) with a static matrix Wτ . The following corollary of
Theorem 5.1 demonstrates that to achieve quantized consensus
in this setting with delays and asynchrony, it is necessary and
sufficient that a spanning tree exists in the network. This is the
well-known topological condition for multi-agent consensus
when the states take real values [27].
Corollary 5.5: When no malicious agent is present, the
network of quantized agents based on the update rule (15)
with delayed information reaches quantized consensus almost
surely with respect to the randomized quantization if and only
if the underlying graph has a directed spanning tree.
Proof: With f = 0, the conditions in Theorem 5.1 and
Proposition 5.3 coincide. Consequently, we obtain a necessary
and sufficient condition for reaching quantized consensus in
normal networks to be (1, 1)-robust. By Lemma 2.2 (iii), this
condition is equivalent to having a directed spanning tree. 
The above corollary is an extension of Corollary 3.5 where
there is no information delay in the network. The system
model in this section with delays also generalizes the models
studied for quantized consensus in [1], [4], [6], [7], [16], [17],
[25].
2) f -Local Malicious Models: The following corollary
states that the same condition fulfills the sufficiency of f local malicious models instead of the f -total models studied
so far. This is because in the proofs of Theorem 5.1 and
Proposition 5.4, the presence of at most f malicious agents in
the neighborhood of each normal agent is the only assumption.
In other words, the total number of malicious agents is not
used in the proof. Note that the necessary condition stated in
Proposition 5.3 is valid for f -local case as well.
Corollary 5.6: Under the f -local malicious models, the
network of deterministic/randomized asynchronous quantized
agents with/without information delays in the asynchronous
QW-MSR algorithm reaches resilient quantized consensus
almost surely with respect to the randomized quantization and
updates if the underlying graph is (2f + 1)-robust and only if
the graph is (f + 1, f + 1)-robust.

1.6
1.4
1.2

2

2
3

Agent

3

1
4

3

4

5

6

7

4

7

7
6

2

Fig. 6. Line colors of the normal agents in the plots.

0.8
0.6

10

5

6

(a) (2,2)-robust

5

(b) Strongly connected

0.4
0.2

-4

State Values

1

8

-2

2

2

4

0
0

3

1

6

10
5

10

15
Time

20

12
25

14
30

Fig. 7. Synchronous QW-MSR algorithm over a nonrobust graph.

4
7
10

5

(c) 3-robust
Fig. 5. Networks with seven agents

State Values

6

8
6
4
2

Finally, we mention that in the results of Theorem 5.1,
Proposition 5.4, and Corollary 5.6, the minimum number of
nodes in the underlying graph to reach resilient quantized
consensus with asynchronous QW-MSR algorithms over f total/f -local malicious models is 4f + 1 (with complete
graphs). This minimum originates from Lemma 2.2 (iv). It
is noteworthy that for real-valued first-order asynchronous
settings, the sufficient condition (3f + 1)-robustness proposed
in [23] has been improved in this paper and in [9]. For a
thorough comparison with the problem setting in [23], the
reader can refer to [8], [9].
VI. N UMERICAL E XAMPLE
In this section, we illustrate the effectiveness of the proposed
resilient consensus algorithms through a numerical example.
Consider the network with seven nodes in Fig. 5(a), which
is the same as the one in Fig. 1. As discussed in Section II-A, this graph is (2,2)-robust. Throughout the example,
it is assumed that the agents start from the initial values
x[0] = [1 10 1 10 1 10 1]T . To misguide the normal agents,
agent 1 is chosen to be malicious, and it alternates between two
values as x1 [2m] = 1 and x1 [2m+1] = 10 for m ∈ Z+ , which
are the values in xN [0]. In the plots, the malicious agent’s
behavior is not shown as it tends to move very frequently in
the different scenarios. The line colors used in the plots for
the normal agents 2, 3, . . . , 7 are shown in Fig. 6.
1) Synchronous Networks: First, we conducted simulations
on the graph in Fig. 5(b), which is constructed by removing the
edges (1, 7), (3, 2), (5, 6), (6, 3), and (6, 7) from the original
graph G in Fig. 5(a). The obtained graph is no longer (2,2)robust, but is strongly connected. After applying the QW-MSR
algorithm on the network, the normal agents are deceived by
agent 1 and do not reach agreement. Fig. 7 illustrates how
the normal agents make updates under this configuration. As
it is seen, while agents 2, 4, and 6 stay at 10 and agents 3
and 7 stay at 1, agent 5 fluctuates between these two values.

0
0

5

10

15

Time

20

25

30

Fig. 8. Synchronous QW-MSR algorithm over a (2, 2)-robust graph

This shows that for resilient consensus, strong connectivity
may not be sufficient. It is noteworthy that by removing
the malicious node 1, the network of normal agents has a
spanning tree. Hence, although the normal agents form a graph
satisfying the well-known necessary and sufficient condition
for reaching consensus, the adversarial effect of the malicious
agent prevents agreement among them.
Next, we made simulations for the original (2, 2)-robust
graph G in Fig. 5(a). As shown in Fig. 8, the normal agents
after 17 steps meet at x∗ = 8. This confirms the result of
Theorem 3.1 for the case of synchronous interactions.
2) Asynchronous Networks without Delay: Then, we carried out simulations for the case where normal agents make
asynchronous updates. First, we examined a deterministic rule
by assigning different updating times for agents 3, 5, and 7,
whose initial values are 1, and agents 2, 4, and 6, whose initial
values are 10, as follows:
(
{3, 5, 7} if k = 2m,
U[k] =
(17)
{2, 4, 6} if k = 2m + 1
for m ∈ Z+ . After applying the QW-MSR algorithm on the
original G in Fig. 5(a), the normal agents do not change their
state values at all as shown in Fig. 9. Note that the underlying
graph satisfies the necessary condition, but not the sufficient
condition.
In the next simulation, we examined the sufficient condition
stated in Theorem 4.1 by modifying G to become 3-robust. We
added the edges (3, 6), (4, 3), (5, 4), (6, 5), and (7, 6) to G to
this aim and obtained the graph in Fig. 5(c). The result is seen
in Fig. 10 where the normal agents agree upon x∗ = 4 after
20 time steps.

10

8

8

State Values
e

State Values

10

6
4

6
4
2

2
0
0

0

5

10

15
Time

20

25

30

8

State Values

State Values

10

8
6
4
2
10

15

Time

20

30

40

Fig. 12. Asynchronous QW-MSR algorithm over a 3-robust graph under
delays and deterministic updates (f = 1).

10

5

10

Time

Fig. 9. Asynchronous QW-MSR algorithm over a (2, 2)-robust graph with
deterministic update times.

0
0

0

20

25

30

6
4
2
0

0

10

20

30

40

Time

Fig. 10. Asynchronous QW-MSR algorithm over a 3-robust graph with
deterministic update times.

Fig. 13. Asynchronous QW-MSR algorithm over a 3-robust graph under
delays and randomized updates (f = 1).

State Values

10

same as those in Fig. 9. Thus, again, they form two clusters
at 1 and 10 and fail to reach consensus.

8
6
4
2
0
0

5

10

15
Time

20

25

30

Fig. 11. Asynchronous QW-MSR algorithm over a (2, 2)-robust graph with
probabilistic update times.

As the last step, we employed the probabilistic update rule
over the (2, 2)-robust graph in Fig. 5(a), where each normal
agent makes updates with probability p = 0.5. The result is
shown in Fig. 11. We observe that the normal agents reach
x∗ = 7 after 28 time steps. This verifies that randomization
in the update times is capable to relax the required robustness
of the network. However, compared to Fig. 10, it takes longer
to reach its final value, which may be because of the sparser
network structure.
3) Asynchronous and Delayed Networks with Deterministic
Updates: Here, we performed simulations considering delays
in the original network G in Fig. 5(a). The updates follow the
same deterministic rule in (17). The communication delays are
present in the edges from agent 1 to its neighbors and are set
as below:
(
(7, 8) if i = 2,
(τi1 [2m], τi1 [2m + 1]) =
(18)
(8, 7) if i = 3, 5, 7
for m ∈ Z+ . Although the underlying graph meets the
necessary condition stated in Proposition 5.3, none of the
normal agents changes its value and their responses look the

Next, we examined Theorem 5.1 by using the 3-robust graph
in Fig. 5(c). This graph was obtained by adding the edges
(3, 6), (4, 3), (5, 4), (6, 5), and (7, 6) to G. In the network,
the updating times (17) and the time delays (18) remain the
same as in the previous simulations. The time responses are
given in Fig. 12, where the normal agents agree upon x∗ = 5
after 19 time steps. Thus, we have verified Theorem 5.1.
4) Asynchronous and Delayed Networks with Randomized
Updates: As the last simulation study, we checked if the
randomization is helpful in the delayed information case. We
set each normal agent i to be updating (i.e., i ∈ U[k]) with
probability pi = 0.4. The delays are defined with the rule (18).
After applying the asynchronous QW-MSR algorithm on the 3robust graph constructed in the previous example, we observe
in Fig. 13 that the normal agents meet at x∗ = 4 but with
a lower speed at k = 32. This corresponds to the result of
Proposition 5.4.
Finally, we employed the randomized update rules over the
original G. We could see that the normal agents form two
groups at 1 and 10 exactly as in Fig. 9, which again verifies
that the sufficient condition in Theorem 5.1 cannot be relaxed
even if the update times are randomized.
As a result of these examples, we see that the malicious
agent tries to hide its jumps (from 1 to 10 and vice versa)
by imposing specific delays in the links to the normal agents.
By this strategy, it successfully deceives the normal agents to
stay at their values. This is independent of update times and
even randomization in update times is not helpful. Thus, the
network must be more robust in order to reach consensus.

VII. C ONCLUSION
In this paper, the problem of quantized consensus in the
presence of malicious agents has been considered. We have
studied several classes of resilient distributed algorithms that
perform under different conditions such as synchronous and
asynchronous schemes with deterministic and probabilistic
updating times, and delayed information. Necessary conditions
and sufficient conditions for reaching consensus among nonfaulty agents have been derived based on the notion of graph
robustness.
In particular, we have made use of randomization in quantization as well as in the update times, which turn out to
be critical in obtaining tight topological conditions on the
underlying graph. On the other hand, in the asynchronous
and/or delayed case, we have observed how malicious agents
can take advantage of the properties in communication to
prevent normal agents from reaching consensus.
In future research, we intend to study convergence rates
of the resilient algorithms (see Remark 3.4 for discussions)
as well as the application of MSR-type algorithms to other
multi-agent problems with malicious information.
ACKNOWLEDGEMENT
The authors would like to thank Paolo Frasca and Shreyas
Sundaram for the helpful discussions.
A PPENDIX : P ROOF

OF

T HEOREM 5.1

We must show that by applying the asynchronous QW-MSR
to an f -total network, the conditions (C1)–(C3) in Lemma 3.2
hold. First, we prove (C1), which is the safety condition.
Define the minimum and maximum values of the normal
agents at time k and the previous τ time steps by
N

N

N

z[k] = min(x [k], x [k − 1], . . . , x [k − τ ]),
z[k] = max(xN [k], xN [k − 1], . . . , xN [k − τ ]).

(19)

In the network, there are at most f malicious agents, and,
at each time step, each normal agent removes the values
of at most f neighbors from the above and below. Hence,
those faulty agents
with unsafe values outside the inter
val z[k], z[k] are all ignored at each time step. In other
words,
each
 normal agent i is affected only by values within

z[k], z[k] . It thus follows that the value of the normal agent
i in the update rule (15) is upper bounded by
m
l X
wτ,ij [k]xj [k − τij [k]]
xi [k + 1] ≤
j∈Ni ∪{i}

≤

l

X

j∈Ni ∪{i}

m



wτ,ij [k]z[k] = z[k] = z[k] (20)

with τii = 0 for i. Also, it is clear that
xi [k] ≤ z[k], xi [k − 1] ≤ z[k], . . . ,
xi [k − (τ − 1)] = xi [k + 1 − τ ] ≤ z[k]
for i ∈ V \ M. Hence, with (20), we have

z[k + 1] = max xN [k + 1], · · · , xN [k + 1 − τ ] ≤ z[k].

This implies that z[k + 1] ≤ z[k], that is, z[k] is a monotonically non-increasing function of time. Likewise, agent i’s
value can be bounded from below as
k
j X
wτ,ij [k]xj [k − τij [k]]
xi [k + 1] ≥
j∈Ni ∪{i}

≥

j

X

j∈Ni ∪{i}

k 

wτ,ij [k]z[k] = z[k] = z[k].

Thus, by similar arguments, we have z[k + 1] ≥ z[k], which
shows that z[k] is a monotonically non-decreasing function of
time. Consequently, we conclude
that
 for the normal agent i,

its state satisfies xi [k] ∈ z[k], z[k] ⊂ Sτ for all k with the
interval Sτ given in (16). Thus, (C1) is established.
Next, we prove (C2) in Lemma 3.2. Since z[k] and z[k] are
contained in Sτ and are monotone, there is a finite time kc
such that they both reach their final values with probability
1. Denote the final values of z[k] and z[k] by z ∗ and z ∗ ,
respectively. Now, to conduct a proof by contradiction, we
assume z ∗ < z ∗ . Then, denote by X1τ [k] the set of all
normal agents at time k ≥ kc with state values equal to z ∗ .
Likewise, denote by X2τ [k] the set of normal agents that have
the minimum state values z ∗ . That is,

X1τ [k] = i ∈ V \ M : xi [k] = z ∗ ,

(21)
X2τ [k] = i ∈ V \ M : xi [k] = z ∗ .
From the convergence of z[k] to z ∗ , we know that the sequence
of X1τ [kc + ℓ], ℓ = 0, . . . , τ , must collectively contain at least
one normal agent that has the value z ∗ , i.e.,
k[
c +τ

X1τ [k] 6= ∅

(22)

k=kc

with probability 1. The same holds for z[k]. We claim that
in fact X1τ [kc ] is nonempty. This is proven by showing that
c +τ
if X1τ [kc ] is empty, then ∪kk=k
X1τ [k] = ∅ with non-zero
c
probability, which is in contradiction with (22). To this end,
it is enough to show that if X1τ [kc + ℓ] is empty, then the
probability of X1τ [kc + ℓ + 1] to be empty is non-zero.
First, we show that none of the normal agents in V \ X1τ [k]
enters X1τ [k+1] at the next time step with positive probability.
Assume that the normal agent i makes an update at time kc +ℓ.
Note that if there is not such an updating agent at time kc + ℓ,
none of them can enter X1τ [kc + ℓ + 1]. However, we know
that each normal agent makes an update at least once in τ̄
time steps. We also know by the assumption on emptiness of
X1τ [kc + ℓ] that agent i is upper bounded by z ∗ − 1. Thus,
xi [kc + ℓ + 1] ≤ Q((1 − β)z ∗ + β(z ∗ − 1)) = Q(z ∗ − β), (23)
where Q(z ∗ − β) = z ∗ − 1 with probability 1 − β. The same
arguments can be employed to prove that X2τ [kc ] is nonempty.
Then, we show that with positive probability, at the next
time step, the agents in X1τ [k] decrease their values, and the
agents in X2τ [k] increase their values. The sets X1τ [kc ] and
X2τ [kc ] are disjoint and nonempty; therefore, we can make use
of (2f + 1)-robustness of the underlying graph G[k]. At least
one of these two sets includes a node with (2f + 1) incoming
links from outside. We show this for the case the normal agent

i is in X1τ [k]; the other case with X2τ [k] can be established
similarly. The value of this agent clearly is xi [k] = z ∗ .
In step 2 of the asynchronous QW-MSR, agent i makes
an update using at least one agent from its neighbors whose
values are smaller than z ∗ . It also neglects all values larger
than z ∗ since there are at most f such values. Thus, by the
update rule (15), we write
xi [k + 1] ≤ Q (1 − β)z ∗ + β(z ∗ − 1)) = Q(z ∗ − β). (24)
Here, by (3), the quantizer output takes the truncated value as
Q(z ∗ − β) = z ∗ − 1 with probability 1 − β. This indicates
that with positive probability, one of the normal agents taking
the maximum value z ∗ decreases its value by at least one.
Similarly, if the normal agent i is in X2τ [k], then with positive
probability, it chooses the ceil quantization, in which case its
value will increase above z ∗ .
From the above discussion, we conclude that at each time
step, some agents in X1τ [k] or X2τ [k] make updates and they
decrease or increase, respectively, their values with positive
probability. Hence, for any k ≥ kc + k̄ · nN , the number of
normal agents in one of the sets X1τ [k] and X2τ [k] is zero with
positive probability because there are only nN such agents and
each makes updates at least once in k̄ time steps. This is a
contradiction and proves (C2).
Finally, we must show (C3) in Lemma 3.2. For this step,
we can follow along similar lines as this part in the proof of
Theorem 3.1. After all normal agents reach consensus at the
value x∗ , when they make updates at time k, other agents j
taking values xj [k] 6= x∗ are ignored. Thus, the third step of
asynchronous QW-MSR with the update rule in (15) results
in xi [k + 1] = x∗ for i ∈ V \ M. Having shown (C3), we
conclude the proof.

R EFERENCES
[1] T. C. Aysal, M. J. Coates, and M. G. Rabbat, “Distributed average
consensus with dithered quantization,” IEEE Trans. Signal Process.,
vol. 56, no. 10, pp. 4905–4918, 2008.
[2] M. H. Azadmanesh and R. M. Kiechafer, “Asynchronous approximate
agreement in partially connected networks,” Int. J. Parallel Distrib.
Networks, vol. 5, no. 1, pp. 26–34, 2002.
[3] M. Ben-Or, “Another advantage of free choice: Completely asynchronous agreement protocols,” Proc. 2nd Annual ACM Symp. on
Principles of Distributed Computing, pp. 27–30, 1983.
[4] K. Cai and H. Ishii, “Quantized consensus and averaging on gossip
digraphs,” IEEE Trans. Autom. Control, vol. 56, no. 9, pp. 2087–2100,
2011.
[5] K. Cai and H. Ishii, “Convergence time analysis of quantized gossip
consensus on digraphs,” Automatica, vol. 48, no. 9, pp. 2344–2351,
2012.
[6] R. Carli, F. Fagnani, P. Frasca, and S. Zampieri, “Gossip consensus
algorithms via quantized communication,” Automatica, vol. 46, no. 1,
pp. 70–80, 2010.
[7] M. E. Chamie, J. Liu, and T. Başar, “Design and analysis of distributed
averaging with quantized communication,” Proc. 53rd IEEE Conference
on Decision and Control, pp. 3860–3865, 2014.
[8] S. M. Dibaji, Resilient Consensus of Multi-Agent Networks in the Presence of Malicious Attacks, Ph.D. thesis, Tokyo Institute of Technology,
2016.
[9] S. M. Dibaji and H. Ishii, “Resilient multi-agent consensus with
asynchrony and delayed information,” Proc. 5th IFAC Workshop on
Distributed Estimation and Control in Networked Systems (NecSys’15),
pp. 28–33, 2015.
[10] 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.

[11] S. M. Dibaji, H. Ishii, and R. Tempo “Resilient randomized quantized
consensus,” Proc. American Control Conference, pp. 5118–5123, 2016.
[12] S. M. Dibaji, H. Ishii, and R. Tempo “Resilient randomized quantized
consensus with delayed information,” Proc. 55th IEEE Conference on
Decision and Control, pp. 3505–3510, 2016.
[13] S. M. Dibaji and H. Ishii, “Resilient consensus of second-order agent
networks: Asynchronous update rules over robust graphs,” Automatica,
vol. 81, pp. 123–132, 2017.
[14] S. R. Etesami and T. Başar, “Convergence time for unbiased quantized
consensus over static and dynamic networks,” IEEE Trans. Autom.
Control, vol. 61, no. 2, pp. 443–455, 2016.
[15] M. J. Fischer, N. A. Lynch, and M. S. Paterson, Impossibility of
distributed consensus with one faulty process, Journal of the ACM,
vol. 32, no. 2, pp. 374–382, 1985.
[16] P. Frasca, R. Carli, F. Fagnani, and S. Zampieri, “Average consensus
on networks with quantized communication,” Int. J. Robust Nonlinear
Control, vol. 19, no. 16, pp. 1787–1816, 2009.
[17] E. Gravelle and S. Martı́nez, “Quantized distributed load balancing with
capacity constraints,” Proc. 53rd IEEE Conference on Decision and
Control, pp. 3866–3871, 2014.
[18] H. Ishii and R. Tempo, “The PageRank problem, multiagent consensus,
and web aggregation: A systems and control viewpoint,” IEEE Control
Syst. Mag., vol. 34, no. 3, pp. 34–53, 2014.
[19] S. Kar and J. M. F. Moura, “Distributed consensus algorithms in sensor
networks: Quantized data and random link failures,” IEEE Trans. Signal
Proc., vol. 58, no. 3, pp. 1383–1400, 2010.
[20] A. Kashyap, T. Başar, and R. Srikant, “Quantized consensus,” Automatica, vol. 43, no. 7, pp. 1192–1203, 2007.
[21] Y. Kikuya, S. M. Dibaji, and H. Ishii, “Fault tolerant clock synchronization over unreliable channels in wireless sensor networks,” IEEE Trans.
Control of Network Syst., to appear, 2017.
[22] J. Lavaei and R. M. Murray, “Quantized consensus by means of gossip
algorithm,” IEEE Trans. Autom. Control, vol. 57, no. 1, pp. 19–32, 2012.
[23] H. J. LeBlanc, Resilient Cooperative Control of Networked Multiagent Systems, Ph.D. Dissertation, Dept. Elect. Eng. and Comp. Sci.,
Vanderbilt Univ., Nashville, TN, 2012.
[24] H. J. LeBlanc, H. Zhang, X. Koutsoukos, and S. Sundaram, “Resilient
asymptotic consensus in robust networks,” IEEE J. Selected Areas in
Communications, vol. 31, no. 4, pp. 766–781, 2013.
[25] T. Li, M. Fu, L. Xie, and J.-F. Zhang, “Distributed consensus with
limited communication data rate,” IEEE Trans. Autom. Control, vol. 56,
no. 2, pp. 279–292, 2011.
[26] N. A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996.
[27] M. Mesbahi and M. Egerstedt, Graph Theoretic Methods in Multiagent
Networks, Princeton University Press, 2010.
[28] R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge
University Press, 1995.
[29] A. Nedic, A. Olshevsky, A. Ozdaglar, and J. N. Tsitsiklis, “On distributed averaging algorithms and quantization effects,” IEEE Trans.
Autom. Control, vol. 54, no. 11, pp. 2506–2517, 2009.
[30] F. Pasqualetti, F. Dorfler, and F. Bullo, “Attack detection and identification in cyber-physical systems,” IEEE Trans. Autom. Control, vol. 58,
no. 11, pp. 2715–2729, 2013.
[31] M. Rabin, “Randomized Byzantine generals,” Proc. 24th Annual IEEE
Symp. on Foundations of Computer Science, pp. 403–409, 1983
[32] C. Ravazzi, P. Frasca, R. Tempo, and H. Ishii, “Ergodic randomized
algorithms and dynamics over networks,” IEEE Trans. Control Netw.
Syst., vol. 2, no. 1, pp. 78–87, 2015.
[33] W. Ren and Y. Cao, Distributed Coordination of Multi-agent Networks,
Springer, 2011.
[34] E. M. Shahrivar, M. Pirani, and S. Sundaram, “Robustness and algebraic connectivity of random interdependent networks,” Proc. 5th IFAC
Workshop on Distributed Estimation and Control in Networked Systems
(NecSys’15), pp. 252–257, 2015.
[35] R. Tempo, G. Calafiore, and F. Dabbene, Randomized Algorithms for
Analysis and Control of Uncertain Systems, with Applications, Second
Edition, Springer, 2013.
[36] R. Tempo and H. Ishii, “Monte Carlo and Las Vegas randomized
algorithms for systems and control,” European J. Control, vol. 13,
pp. 189–203, 2007.
[37] L. Tseng and N. H. Vaidya, “Fault-tolerant consensus in directed
graphs,” Proc. ACM Symp. Principles of Distributed Comput., pp. 451–
460, 2015.
[38] N. Vaidya, L. Tseng, and G. Liang, “Iterative approximate Byzantine
consensus in arbitrary directed graphs,” Proc. ACM Symp. Principles of
Distributed Comput., pp. 365–374, 2012.

[39] R. A. Wannamaker, S. P. Lipshitz, J. Vanderkooy, and J. N. Wright,
“A theory of nonsubtractive dither,” IEEE Trans. Signal Proc., vol. 48,
no. 2, pp. 499–516, 2000.
[40] H. Zhang, E. Fata, and S. Sundaram, “A notion of robustness in complex
networks,” IEEE Trans. Control of Network Syst., vol. 2, no. 3, pp. 310–
320, 2015.
[41] J. Zhao, O. Yagan, and V. Gligor, “On the strengths of connectivity
and robustness in general random intersection graphs,” Proc. 53rd IEEE
Conference on Decision and Control, pp. 3661–3668, 2014.
[42] M. Zhu and S. Martı́nez, “On the convergence time of asynchronous distributed quantized averaging algorithms,” IEEE Trans. Autom. Control,
vol. 56, no. 2, pp. 386–390, 2011.

