Convergence Time of Quantized Metropolis Consensus Over Time-Varying
Networks

arXiv:1504.01438v2 [] 2 Feb 2016

Tamer Başar,

Seyed Rasoul Etesami,

Abstract— We consider the quantized consensus problem on
undirected time-varying connected graphs with n nodes, and
devise a protocol with fast convergence time to the set of
consensus points. Specifically, we show that when the edges of
each network in a sequence of connected time-varying networks
are activated based on Poisson processes with Metropolis rates,
the expected convergence time to the set of consensus points
is at most O(n2 log2 n), where each node performs a constant
number of updates per unit time.

I. I NTRODUCTION
There has been much recent interest in the design of
control protocols for distributed systems, motivated in part
by the need to develop protocols for networks of autonomous
agents characterized by the lack of centralized information
and time-varying connectivity. A canonical problem within
the field is the so-called average consensus problem, wherein
a group of agents must agree on the average of their initial
values while interacting with neighbors in a (possibly timevarying) network. Protocols for consensus problems must be
distributed, relying only on local information at each node,
and robust to unexpected changes in topology.
It is well understood by now that protocols for the
consensus play an important role in a number of more
sophisticated multi-agent tasks. We mention distributed optimization, coverage control, formation control, cooperative
statistical inference, power control, load balancing, epidemic
routing, as examples of control and coordination problems
with proposed solutions relying crucially on consensus.
Our work is motivated by the observation that often
working with real-valued variables in multi-agent control
is neither necessary nor efficient. Indeed, limited memory
and storage at each agent often forces the variables kept by
each agent to lie in a discrete set. We therefore consider the
quantized consensus problem, a variation on the consensus
problem where the values of each agent are constrained to
be integers lying within a certain range. Previous literature
on this problem includes [1], [2], [3], [4], [5], [6]. As
some of the real-world applications of the problem under
consideration, one can consider information fusion in sensor
networks [7], e. g., when every sensor in a sensor network
has a different measurement of the temperature and each
sensor’s goal is to compute the average temperature, and
load balancing in processor networks which has various
applications in computer science.
The original paper [1] contained upper bounds for a
natural quantized consensus protocol on a variety of common
graphs. A few years later, the work of [3] proposed a

Alex Olshevsky

quantized consensus protocol with upper bound of O(n4 )
on the expected convergence time for any fixed graph. For
dynamic graphs, [3] obtained a convergence time scaling of
O(n8 ). The paper [6] obtained an upper bound of O(n2 ),
but only on complete graphs. Recently, it was shown in
[8] that a certain “unbiased” quantized consensus protocol
has maximum expected convergence time of O(nmD log n)
on static networks where m and D denote the number
of edges and the diameter of the network, and has maximum expected convergence time O(nmmax Dmax log2 n) on
connected time-varying networks, where mmax and Dmax
denote, respectively, the maximum number of edges and
the maximum diameter in the sequence of time-varying
networks. Unbiasedness means that each step of the protocol
was based on choosing a random edge uniformly among all
possible edges in the network.
A faster upper bound on convergence time and only for
static networks was given in the recent paper [9], where
a protocol was provided whose expected convergence time
in general static networks is O(n2 log n) 1 . As of the time
of writing this paper, the upper bounds of O(n2 log n) and
O(nmmax Dmax log2 n), respectively, are the fastest protocols known to us for randomized quantized consensus over
static and dynamic networks [8], [9], respectively. It is worth
noting that the convergence speed of a protocol is measured
by the maximum over all initial inputs of the expected time
that the given protocol will run until reaching consensus,
where each node performs a constant number of updates per
unit time.
In this paper, we analyze a protocol wherein nodes cooperate to perform updates on edges connecting them at socalled Metropolis rates. We are able to show that when each
node performs a constant number of updates per unit time,
convergence time on connected time-varying networks is at
most O(n2 log2 n), giving us the fastest quantized consensus
convergence guarantee over time-varying networks.
The paper is organized as follows. In Section II, we
formulate the quantized consensus problem and discuss some
of its properties. In Section III, we show that quantized
consensus with Metropolis rates has essentially quadratic
convergence time on fixed networks; this result is not better
than the previous convergence time of [9], but we include
it here because our later results rely on it. In Section IV,
we prove our main result, namely that Metropolis quantized
1 The bound given in [9] was O(n3 log n), but this was a count of the
total number of updates; in terms of time, this leads to a quadratic expected
convergence time.

consensus converges in essentially quadratic time on timevarying networks. We conclude the paper by identifying
some future directions of research in Section V.
Notation: We let [n] = {1, 2, . . . , n}. For an undirected
graph G = (V, E) we let N (x) be the set of neighbors of x,
and furthermore, let d(x) denote the degree of x i.e., d(x) =
|N (x)|. For a given vector v, we denote its ith entry by vi and
its transpose by v 0 . We say that a matrix A with nonnegative
entries is stochastic if each row of A sums to 1. We say A
is doubly-stochastic if both A and A0 are stochastic.
II. P ROBLEM F ORMULATION
In this section, we assume that we are given a fixed,
undirected, connected graph G = (V, E) with |V | = n and
without self-loops. The Metropolis Markov chain on this
graph is then defined as follows.
Let M be a square matrix whose ij’th entry is defined as

1
,
if i 6= j, j ∈ N (i)

 max{d(i),d(j)}
P
(1)
Mij = 1 − j∈N (i) Mij , if i = j


0
otherwise,
Note that M is symmetric, nonnegative, and doubly stochastic. We refer to the Markov chain which transitions according
to M as the Metropolis chain. Moreover, given nodes x, y ∈
V , the hitting time H m (x, y) is the expected time until the
Metropolis chain with initial position at node x reaches node
y (quantities associated with the Metropolis chain will generally be denoted with an “m” superscript). For future use and
convenience, we adopt the notation λij = 1/ max(d(i), d(j))
whenever {i, j} ∈ E and λij = 0 otherwise.
A. Quantized Metropolis dynamics
We next introduce a continuous time quantized process
based on Metropolis weights, whose behavior will turn out
to be related to the Metropolis chain. For each link {i, j} ∈ E
of the graph G, we consider a Poisson process of rate λij .
Each node i begins with an integer value xi (0) which lies
in the range [l, L]. Each time the process corresponding to
an edge {i, j} ∈ E registers an arrival, the two nodes i, j
perform the quantized consensus update from [1]:


xi (t) − 1, if xi (t) > xj (t)
+
xi (t ) = xi (t) + 1, if xi (t) < xj (t)
(2)


xi (t),
if xi (t) = xj (t),
and likewise for node j. In other words, each xi (t) is an
integer-valued jump process whose jumps occur whenever
an arrival occurs at any edge incident on i.
Note that the above update rule allows for the possibility
that xi (t+ ) = xi (t). In this case, we will say that the update
at time t was trivial. Furthermore, observe that if |xi (t) −
xj (t)| = 1, then the update of Eq. (2) will cause nodes i
and j to swap values, i.e., xi (t+ ) = xj (t), xj (t+ ) = xi (t).
In this case, we will also say that the update was trivial. If
neither of these two cases has occurred during an update, we
will say that the update was non-trivial. Simply speaking, a
non-trivial update refers to the case where the incident nodes

of an activated edge have integer values which differ by at
least 2.
It has been shown earlier in [1] that such dynamics
based on update rule (2) will converge with probability 1
to consensus set defined by
Pn
n
o
xi
C = x|xi ∈ {bx̄(0)c, bx̄(0)c+1}, i=1
= x̄(0), i =∈ [n] .
n
In the remainder of this paper our goal is to provide an upper
bound on the expected convergence time of the quantized
Metropolis dynamics to the consensus set.
III. C ONVERGENCE T IME OVER S TATIC N ETWORKS
We now begin the analysis of the convergence time of
the quantized Metropolis algorithm over a fixed graph G.
The bounds derived in this section are of the same order of
magnitude as the previous work [9], and the proof follows
similar lines as well; however we are including it here as
our analysis over time-varying networks in the next section
relies on these results.
A key step in our analysis is to bound the expected
time until the first nontrivial update takes place. For this
purpose, we let T be the maximum expected time such that
a nontrivial update takes place over all possible configuration of integers. More precisely, for integers j1 , . . . , jn let
T (j1 , . . . , jn ) be the expected time until a nontrivial update
takes place when node i begins with integer value ji . Then
T =

max

(j1 ,...,jn )∈Zn ,l≤ji ≤L
(j1 ,...,jn )∈C
/

T (j1 , . . . , jn ).

Definition 3.1: Consider two random walkers moving
based on whether the activated edge in the quantized
Metropolis dynamics is incident to them. That is, if one of
the walkers is at node x, and if the next edge to register an
arrival is incident to x, i.e., if it is {x, y} for some y ∈ N (x),
then the random walker moves from x to y. We refer to such
a process as the original process. We denote by M o (x, y) the
expected “meeting time” of this process, defined to be the
expected time until an edge incident to both walkers registers
an arrival provided the two walkers started at nodes x, y with
x 6= y (in general, we will denote quantities associated with
this process with an “o” superscript). By convention, we set
M o (x, x) = 0 for all x ∈ V .
Proposition 3.2: T = maxx,y∈V M o (x, y).
Proof: The proof is immediate and is not included due
to space limitation.
Based on the above proposition, our next step is to bound
maxx,y∈V M o (x, y). We will actually find it easier to instead
bound a meeting time associated with a slightly different
process, which we call the virtual process, defined next.
Definition 3.3: The virtual process is identical to the original process until the two walkers x, y become each other’s
neighbors in G. At that time, the edge connecting them
registers arrivals according to a Poisson process of rate 2λxy .
We denote the expected meeting time function of the virtual
process by M v (x, y) (in general, we will denote quantities

associated with this process with a “v” superscript). By
convention we set M v (x, x) = 0 for all x ∈ V .
Definition 3.4: A function h : Ω → R is called harmonic
at a vertex x ∈ Ω for a Markov
chain with transition
P
probability matrix P if h(x) = y∈Ω P (x, y)h(y).
Remark 3.5: Given a nonempty subset B ⊂ Ω and a
Markov chain with an irreducible transition matrix P , every
harmonic function h(·) : Ω → R over Ω \ B which satisfies
h(x) ≥ 0, ∀x ∈ B, must be nonnegative over the entire Ω (see
Proposition 9.1 of [10]).
Definition 3.6: A vertex θ is called a hidden vertex of the
Metropolis chain M if H m (θ, x) ≤ H m (x, θ), ∀x ∈ V .
Remark 3.7: It is known that the hitting times of a reversible Markov chain satisfy transitivity property, i.e.,
H m (x, y)+H m (y, z)+H m (z, x) = H m (x, z)+H m (z, y)+H m (y, x),

see [11] for a proof. As a consequence every reversible
Markov chain has at least one hidden vertex [12].
In the following lemma we bound the expected meeting
time of the virtual process by showing that the expected
meeting time function of the virtual process M v (x, y) satisfies essentially the same recursion as the function Φm (·, ·) :
V × V → R defined by
Φm (x, y) = H m (x, y) + H m (y, θ) − H m (θ, y),

(3)

where θ is a fixed hidden vertex of the Metropolis chain.
Lemma 3.8: For all x, y ∈ V , we have M v (x, y) ≤ 6n2 .
Proof: Fix nodes x and y such that x 6= y, and define
X
X
Λx =
λxxi , Λy =
λyyi , Λxy = Λx + Λy .
xi ∈N (x)

yi ∈N (y)

An immediate consequence of Remark 3.7 is the symmetry
of Φm (·, ·), i.e., Φm (u, v) = Φm (v, u), ∀u, v ∈ V. Therefore
we can argue that

N (x), we obtain
X λxx
i
Φm (xi , y) =
Λxy
xi ∈N (x)

+

X
xi ∈N (x)

λxxi m
H (xi , y)
Λxy


Λx  m
H (y, θ) − H m (θ, y) . (5)
Λxy

By symmetry of Φm and using the same argument we get
X λyy
X λyy
i
i
Φm (x, yi ) =
H m (yi , x)
Λxy
Λxy
yi ∈N (y)

yi ∈N (y)

+


Λy  m
H (x, θ) − H m (θ, x) . (6)
Λxy

Substituting (6) and (5) in (4) yields
Φm (x, y) =

X λxx m
X λyy m
2
i
i
+
Φ (xi , y)+
Φ (x, yi ).
Λxy
Λxy
Λxy
xi ∈N (x)

yi ∈N (y)

(7)

On the other hand, we note that the meeting time of the
virtual process can be expanded as
M v (x, y) =

X λxx
X λyy
1
i
i
+
M v (xi , y)+
M v (x, yi ).
Λxy
Λxy
Λxy
xi ∈N (x)
yi ∈N (y)
(8)

We therefore see that 12 Φm (x, y) and M v (x, y) follow
the same recursion formula when x 6= y. Thus defining
f (x, y) = 21 Φm (x, y) − M v (x, y) we have ∀x 6= y ∈ V
X λxx
X λyy
i
i
f (x, y) =
f (xi , y) +
f (x, yi ).
Λxy
Λxy
xi ∈N (x)

yi ∈N (y)

Defining the stochastic irreducible matrix Q as
λ
, if s = y, r ∈ N (x)
 xr
xy
 Λ
λyw
Q (x, y), (r, s) = Λxy , if r = x, w ∈ N (y)


0,
Else,

one can see that f (x, y) is harmonic for the matrix Q over
V × V \ {(x, x) | x ∈ V } and, since θ is a hidden vertex,
Λy m
Λx m
m
we have that for all x ∈ V , f (x, x) = 21 (H m (x, θ) −
Φ (x, y) =
Φ (x, y) +
Φ (y, x)
Λxy
Λxy
H m (θ, x)) ≥ 0. Therefore, using Remark 3.5, we imme

X λxx m
 diately get f (x, y) ≥ 0 for all x, y ∈ V , and therefore
Λx  1
Λx  m
i
=
+
H (xi , y)+
H (y, θ)−H m (θ, y)
M v (x, y) ≤ 21 Φm (x, y). Finally, it was shown in [13] that
Λxy Λx
Λx
Λxy
xi ∈N (x)
H m (x, y) ≤ 6n2 for all x, y ∈ V , which now immediately


X λyy m
 implies the current lemma.
Λy  1
Λy  m
i
+
H (yi , x)+
H (x, θ)−H m (θ, x) ,
+
Our next lemma shows that maxx,y M o (x, y) is essentially
Λxy Λy
Λy
Λxy
yi ∈N (y)
of the same order as maxx,y M v (x, y).
Lemma 3.9: maxx,y M o (x, y) ≤ 12n2 .
where in the second equality we expanded H m (x, y) and
m
Proof: Fix x 6= y and initialize both the original
H (y, x). Simplifying the last relation, we obtain
process and the virtual process with initial positions of the
X λxx
X λyy
2
i
i
walkers being x and y. Furthermore, let us couple these
Φm (x, y) =
+
H m (xi , y) +
H m (yi , x)
Λxy
Λxy
Λxy
processes to move identically until the first time when the
xi ∈N (x)
yi ∈N (y)


walkers are each other’s neighbors. At this time assuming
Λx
Λ
y
H m (y, θ)−H m (θ, y) +
H m (x, θ)−H m (θ, x) ,
+
Λxy
Λxy
that the walkers are at nodes u and w, let us split the edge
connecting them of rate 2λuw in the virtual process into
(4)
two distinct edges of rate λuw (Figure 1). We will make
Using the definition of Φm (·, ·), for each xi ∈ N (x) the first of these (the bottom black edge in the right side
we have, Φm (xi , y) = H m (xi , y) + H m (y, θ) − H m (θ, y). of Figure 1), as well as the edges going from u and w to
λ i
Multiplying this relation by Λxx
and summing over xi ∈ their neighbors, register arrivals in the virtual process exactly
xy

when the corresponding edges in the original process register
arrivals. Now, for these coupled processes, let us denote by

Smin (t). Therefore, the probability that V (t0 ) = V (t) for
t0 > t is upper bounded by the probability that there exist
some i ∈ Smax (t), j ∈ Smin (t) such that two random walkers
in the original process starting from nodes i and j have not
yet met. Thus letting C being the time elapsed until V (t)
shrinks by 1, we have that
)
Z ∞ ( X
Z ∞
P(τ o (x, y) > t) dt
P(C > t)dt ≤ min 1,
E(C) =

Fig. 1. Interpretation of the virtual process using the original process and
an extra edge.

τ v (x, y) a random variable denoting the first time when the
random walkers in the virtual processes meet and τ o (x, y)
the first time when the random walkers in the original process
meet, given that the processes have been initialized from x
and y. We have that τ o (x, y) = τ v (x, y) if the first edge
of rate λuw registers an arrival before the second edge of
rate λuw . This happens with probability 21 . If this does not
happen, τ o (x, y) is τ v (x, y) plus another random variable
which is a meeting time in the original process starting from
u and w, i.e., τ o (u, w). In other words,
(
τ v (x, y),
w.p. 21 (black edge ticks)
o
τ (x, y) =
v
o
τ (x, y) + τ (u, w) w.p. 12 (red edge ticks).
Taking expectation of the above relation, we obtain
M o (x, y) ≤

1 v
1
M (x, y) + (M v (x, y) + max M o (u, w))
u,w
2
2

which implies that maxx,y M o (x, y) ≤ 2 maxx,y M v (x, y)
which by Lemma 3.8 is at most 12n2 .
Remark 3.10: In view of the previous lemma, we have
t

P(τ o (x, y) > t) ≤ e−b 12en2 c .

(9)

This can be seen by the same argument as in Chapter 2.4.3
of [11] whose argument applies verbatim here.
Theorem 3.11: The expected time until the quantized
Metropolis dynamics reaches a consensus set is O(n2 log n).
Proof: Consider the time it takes for the Lyapunov
function V (t) = maxi xi (t)−mini xi (t) to shrink by at least
1 starting from any non-consensus configuration. We show
that this time is O(n2 log n), which proves the theorem.
Indeed, let Smax (t) = arg maxi xi (t), Smin (t) =
arg mini xi (t). Now let us consider the event that V (t0 ) =
V (t) for t0 > t. We claim that there must exist i ∈
Smax (t), j ∈ Smin (t) such that two random walkers in
the original process starting from nodes i and j have not
yet met during the time interval [t, t0 ]. To see this, we
note that during the executions of the quantized Metropolis
dynamics no new values maxi xi (t) and mini xi (t) will
be created; these values only travel from one node to the
other over the network. Now given that at time t0 we have
V (t0 ) = V (t), there must exist two nodes i0 , j 0 such that
xi0 (t0 ) = maxi xi (t) and xj 0 (t0 ) = mini xi (t). By tracking
back the origin of the random walks which bring the values
maxi xi (t) and mini xi (t) at time t to the nodes i0 and j 0 at
time t0 , one can see that these walks have never meet, and
they must have originated from some nodes i ∈ Smax (t), j ∈

0

0

Z
≤

∞

x,y

n
o

t
min 1, n2 e(1− 12en2 ) dt = O n2 log n ,

0

where the second inequality
R ∞ is due to Eq. (9) and the last
A
,
equality follows from 0 min {1, Ae−at } dt = 1+log
a
which holds when A ≥ 1, and is from [11], Ch. 5.3.2.
IV. C ONVERGENCE T IME OVER DYNAMIC N ETWORKS
In this section we analyze the expected convergence time
of the quantized Metropolis dynamics over time-varying
networks and prove our main result, namely that this convergence time is essentially quadratic in the number of nodes.
Toward this aim, let us consider a sequence of connected
undirected networks G(t) = (V, E(t)), t ≥ 0, over the
same set of vertices V which may change at discrete time
instances, i.e., G(t) = G(btc), ∀t ≥ 0. Thus our notation
for the set of neighbors of x will now be Nx (t), which
depends on t. In contrast to the previous section, we will
now assume that each node always possesses a self-loop,
i.e., x ∈ Nx (t) for all x ∈ V, t ≥ 0. We thus introduce the
notation Nx0 (t) to denote the neighbors of node x excluding
itself: Nx0 (t) = Nx (t)\{x}. The degree of a node x, denoted
by dx (t), will be referred to as the cardinality of Nx0 (t).
A. Quantized Metropolis Model over Time-Varying Networks
Given a network G(t) at time t ≥ 0, we associate a
Poisson process with each edge {i, j} of G(t) with a rate
of λij (t) = 1/ max(di (t), dj (t)), i.e., the Metropolis weight
corresponding to that edge at time t. When an edge {i, j} ∈
E(t) registers an arrival, we let the incident nodes update
their values based on (2). Moreover, for each node x and
time t, the self-loop (x, x) registers arrivals according to a
Poisson process with rate of
1 X
λxx (t) = 1 −
λxxi (t).
(10)
2
0
xi ∈Nx (t)

Note that λxx (t) ≥ 0 for all x ∈ V, t ≥ 0, and the sum of
the rates of the edges of G(t) is always equal to |V | = n.
When a self-loop registers an arrival, no update is made.
B. Preliminary Definitions and Relevant Results
We next introduce the notions of the “original” and “virtual” processes over the time-varying graph sequence {G(t)}.
Definition 4.1: Consider two random walkers moving
based on whether the activated edge in the quantized
Metropolis location is incident to them or not. That is, if
a random walker is at node i at time t when the edge
{i, j} ∈ G(t) registers an arrival, the walker moves to node

j. As before, we will refer to this as the original process,
but note that the graph sequence is now time-varying. The
meeting time Mto (x, y) for x 6= y is the expected time until
two random walkers, starting at locations x and y at time t,
are both incident on an edge which registers an arrival. By
convention we set Mto (x, x) = 0 for all x ∈ V, t ≥ 0.
Definition 4.2: We define the virtual process to be identical to the original process except when the two walkers
in the original process are each other’s neighbors at nodes
u and w for some t ≥ 0, i.e., u ∈ Nw (t). At this time in
the virtual process we let the edges {r, s} ∈ E(t) register
arrivals at rates µrs (t) defined as follows.

2λuw (t),
if {r, s} = {u, w}



λ (t) − λuw (t) , if {r, s} = {u, u}
uu
2
(11)
µrs (t) =
λuw (t)

, if {r, s} = {w, w}
λ
(t)
−
ww

2


λrs (t),
if else.
Note that µrs (t) ≥ 0 for all r, s ∈ V, t ≥ 0. We refer to
the meeting time of the virtual process starting from x and
y at time t as τtv (x, y) and its expectation Mtv (x, y). By
convention, we set Mtv (x, x) = 0 for all x ∈ V, t ≥ 0.
In words, the rate of the edge {u, w} is doubled, while
the rate of the self-loops is decreased to make sure that all
rates still sum up to n.
C. Convergence Rate over Time-Varying Networks
In this part, we state our main results for the quantized
Metropolis dynamics over time-varying networks. Define
Λxy (t) to be
X
X
Λxy (t) =
λxxi (t) +
λyyi (t) = 2 (2−λxx (t)−λyy (t)) .
xi ∈Nx0 (t)

yi ∈Ny0 (t)

(12)
Fix t and let T1 be the first time after t that an edge registers
an arrival in the virtual process. We then have


Λxy (T1 )
E [τtv (x, y)|T1 ] = (T1 − t) + 1 −
MTv1 (x, y)
n
X λxx (T1 ) v
X λyy (T1 ) v
i
i
+
MT1 (xi , y) +
MT1 (x, yi ). (13)
n
n
0
0
xi ∈Nx (T1 )

yi ∈Ny (T1 )

Note that this equation holds regardless of whether x and y
are neighbors, and this fact is the reason why we introduced
the virtual process in the first place. Next the following
lemma shows that T1 follows an exponential distribution with
parameter n.
Lemma 4.3: Let us consider a process obtained by restarting a Poisson process of rate n at every discrete time instant
k = 0, 1, 2, ..... The first time arrival T1 of the new process
thus generated will follow an exponential distribution with
parameter n.
Proof: The proof follows by computing the cumulative
function of T1 and showing that P(T1 ≤ t) = 1 − e−nt , ∀t.

Continuing with (13) and since T1 is exponential with
parameter n, we further have that
∞

Z

ne−n(t1 −t) E [τtv (x, y)|T1 = t1 ] dt1


Z ∞
Λxy (t1 )
1
= + ne−n(t1 −t) 1 −
Mtv1 (x, y)dt1
n
n
t
Z ∞ X
λxxi (t1 ) v
Mt1 (xi , y)dt1
+
ne−n(t1 −t)
n
t x ∈N 0 (t )
1
i
x
Z ∞X
λyyi (t1 ) v
+
ne−n(t1 −t)
Mt1 (x, yi )dt1 . (14)
n
t
0

Mtv (x, y) =

t

yi ∈Ny (t1 )

Now let us define v(t) to be a column vector of length
n(n − 1) whose entries are the variables Mtv (x, y), ∀x 6= y
in any order. It follows that we can write the above recursion
for Mtv (x, y) in matrix form as
v(t) =

1
1+
n

Z

∞

ne−n(t1 −t) D (t1 ) v (t1 ) dt1 ,

(15)

t

where D(t) ∈ Rn(n−1)×n(n−1) is a matrix whose rows and
columns we will index by (x, y), x 6= y as
 λrx (t)

 n ,

 λsy (t) ,

if s = y, r ∈ Nx (t) \ {x, y}
if
r = x, s ∈ Ny (t) \ {x, y}
n
D(x,y)(r,s) (t) =
Λxy (t)

1 − n , if (r, s) = (x, y)



0,
Else.
(16)
We change variables in (15) from t1 to z = −e−n(t1 −t)
and obtain

v(t) =

1
1+
n

0


 

ln(−z)
ln(−z)
D t−
v t−
dz. (17)
n
n
−1

Z

We justify this change of variables by appealing to Theorem 263I in [14]. Indeed, the equivalence
of REq. (17) and Eq.
R
(15) is an instance of the equality I 0 g = I g(φ(z))φ0 (z).
Here φ(z) = −e−n(z−t) while g(z) = D(t−ln(−z)/n)v(t−
ln(−z)/n). Theorem 263I in [14] allows us to assert this
equality subject to (i) g(·) being Lebesgue measurable (ii);
and φ(z) being absolutely continuous on any closed bounded
subinterval of I. Item (ii) is clearly satisfied here. Item (i)
follows because D(·) is a piecewise continuous function by
definition, and v(·) is a continuous function (indeed, taking
tn → t and conditioning on no transitions in [tn , t] as well as
no meeting occurring in the same interval, we immediately
obtain the continuity of v(t) as a function of t.
Next, we note that it is immediate from Eq. (16) that D(t)
is a symmetric matrix. Furthermore, it is easy to see that
D(t) is sub-stochastic, implying that its eigenvalues are all
real and less than 1 in modulus. Our next step is to upper
bound both the largest and smallest eigenvalues of D(t).

The first step is to extend D(t) to a stochastic matrix
2
2
P ∈ Rn ×n as follows:


1,
if x = y = r = s



λrx (t)


,
if x 6= y, s = y, r ∈ Nx (t)\{x}
 n
λsy (t)
P(x,y)(r,s) (t) =
if x 6= y, r = x, s ∈ Ny (t)\{y}
n ,


Λxy (t)


1− n , if x 6= y, (r, s) = (x, y),

0,
if else.
(18)
Note that since P (t) is stochastic, it can be interpreted as
the transition matrix of a Markov chain with absorbing states
S = {(x, x) : x ∈ V }. When we adopt the convention that
states in S correspond to the first n rows of P (t), we have
that the matrix P (t) can be represented as

P (t) =

In×n
C(t)

0
D(t)


,

(19)

where C(t) and D(t) are, respectively, matrices of sizes
(n2 − n) × n and (n2 − n) × (n2 − n).
Lemma4.4: Consider
 a Markov chain with transition maIk×k 0
trix Q =
, which has the additional property
C
D
that there is a path starting from any node and ending in the
first k nodes. Furthermore, let us assume that D is symmetric
and let us denote its largest eigenvalue by λmax (D). Let
Hi denote the expected time until the chain is absorbed in
{1, . . . , k} starting at node i and H = maxi Hi . Then
1
λmax (D) ≤ 1 − .
H
Proof: Indeed, 1/(1 − λmax (D)) is a positive number
which is an eigenvalue of (I − D)−1 and is consequently
upper bounded by ||(I − D)−1 ||∞ . But by [15], Theorem
4.5, we have that the sum of the entries in the i’th row of
(I − D)−1 is Hi .
Lemma 4.5: For all t ≥ 0, λmax (D(t)) ≤ 1 − 6n1 3 .
Proof: Fix t and let H P(t) ({x, y}) denote the hitting
time to S = {{i, i} | i ∈ V } in P (t) starting from {x, y}. It
is immediate that when x 6= y,
H P(t) ({x, y}) =

n
+
Λxy (t)
+

X
xi ∈Nx0 (t)

X
yi ∈Ny0 (t)

λxxi (t) P(t)
H
({xi , y})
Λxy (t)

λyyi (t) P(t)
H
({x, yi }).
Λxy (t)

Comparing this to Eq. (8) and noting that H P (t) ({i, i}) = 0
for all i ∈ V , we obtain that H P (t) ({x, y})/n equals the
expected meeting time in the virtual process on the graph
G(t) starting from x and y. Appealing to Lemma 3.8, we
can conclude that expected hitting time in P (t) to the first
n states is at most 6n3 . Appealing to Lemma 4.4 then
completes the proof.
Observe that the lower bound
λmin (D(t)) ≥ 1 −

4
n

(20)

follows immediately by Gershgorin circles due to the observation that Λxy (t) ≤ 2 for all x, y ∈ V, t ≥ 0. We are now in
a position to state and prove the main result of this section.
Theorem 4.6: The expected time until the quantized
Metropolis dynamics over time-varying connected networks
reaches the consensus set is O(n2 log2 (n)).
Proof: Note that we may iterate the recursion of Eq.
(17) to obtain


Z 0
ln(−z)
1
1
1+
D t−
1
n
n
n
−1




Z 0 
ln(−z) ln(−z 0 )
ln(−z) ln(−z 0 )
+
D t−
−
·v t−
−
dz 0 dz
n
n
n
n
−1

 

Z 0 Z 0
ln(−z)
2
ln(−z)
ln(−z 0 )
D t−
≤ 1+
D t−
−
n
n
n
n
−1 −1


ln(−z)
ln(−z 0 )
·v t−
−
dz 0 dz,
n
n

v(t) =

where the last step used the sub-stochasticity of D(·).
Iterating this k times, we obtain
Z "k  j
#  k

Q
P ln(−zi )
P ln(−zi )
k
D t−
v
v(t) ≤ 1+
t−
dzk . . .dz1 .
n
n
n
j=1
i=1
i=1
[−1,0]k

(21)
Now let us use introduce the notation M = supt≥0 kv(t)k∞ .
Elementary arguments suffice to establish that M < ∞;
recall that v(t) stacks up expected meeting times in the
virtual process starting at time t, and the finiteness of M
can follow from the observation that the probability of
intersection in any positive length interval [t, t+a] is positive
and bounded away from zero independently of t. Thus for
every  > 0 there exists t∗ such that M −  ≤ kv(t∗ )k∞ .
Since the entries of D(·) and v(·) are always nonnegative,
we can take the infinity-norm from both sides of (21) and
use triangle inequality to obtain
k
M −  ≤ kv(t∗ )k∞ ≤
n
ZZ Z


j
k
Q
P
i)
D t∗ − ln(−z
+ ...
n
j=1

i=1



k
P
i)
v t∗ − ln(−z
dzk . . .dz1
n
∞

i=1

∞



ZZ Z
j
k
Q
P
k
i)
≤ + M ...
dzk . . .dz1
D t∗ − ln(−z
n
n
j=1
i=1
∞


ZZ Z
j
k
p
Q
P
k
ln(−zi )
∗
dzk . . .dz1
≤ + M . . . n(n − 1)
D t −
n
n
j=1
i=1
2


ZZ Z
j
k
p
Q
P
k
i)
≤ + M . . . n(n − 1)
D t∗ − ln(−z
dzk . . .dz1
n
n
j=1
i=1
2

k
p
k
≤ + M n(n − 1) sup {|λmax (D(t))|, |λmin (D(t))|}
n
t≥0

k
p
k
1
≤ + M n(n − 1) 1 − 3
,
(22)
n
6n
where in the fourth inequality we have used the fact that
the infinity-norm of a matrix is always upper bounded by
its induced 2-normp
times the square root of its dimension,
i.e., kD(·)k∞ ≤
n(n − 1)kD(·)k2 . Moreover, the last
inequality is valid due to Lemma 4.5 and Eq. (20).

p
k ∗
≤ 21 .
Let us choose k ∗ so that n(n − 1) 1 − 6n1 3
x
−1
Appealing to the inequality (1 − 1/x) ≤ e , we obtain
that we may choose k ∗ = O(n3 log n) to accomplish this.
Plugging this into the last line of Eq. (22), we immediately
∗
obtain M −  ≤ kn + M
2 . Since this holds for any  > 0, it
implies that M ≤ 2k ∗ /n = O(n2 log n).
We have thus obtained an upper bound of O(n2 log n)
on the expected meeting time in the virtual process starting
from any pair of nonidentical nodes and any time t. The
rest of the proof directly parallels the arguments we have
made in the fixed graph case, and we only sketch it rather
than repeat the relevant parts verbatim. The first step is to
argue that 2M is an upper bound on the meeting time of the
original process. The proof proceeds exactly as in the case of
Lemma 3.9 by coupling the two processes and conditioning
on the transition at the last step in the meeting time of the
virtual process. The next (and final) step is to argue that the
time it takes V (t) = maxi xi (t) − mini xi (t) to shrink by
1 is upper bounded by O(n2 log2 n). This follows exactly
as in the proof of Theorem 3.11. Indeed, we can argue that
if V (t0 ) = V (t) at some time t0 > t, this means that a
pair of nodes performing a random walk according to the
original process have not met between times t and t0 . Upper
bounding the latter using the union bound, we once again
obtain that the expected time it takes for V (t) to shrink by
1 is the expected meeting time in the virtual process times
a multiplicative factor of O(log n).
V. C ONCLUSION
We have studied the quantized consensus problem on
undirected connected networks in both static and timevarying settings. In particular, we have proved an upper
bound of O(n2 log2 n) for the convergence time of quantized
Metropolis over time-varying connected networks.
A future direction of research would be to improve convergence times further. For example, [16] attained a linear
convergence time for consensus on any fixed graph, and it is
an open question to obtain a quantized consensus protocol
which replicates this. Moreover, an interesting problem is to
see to what extent the results here can be carried over to
protocols with nonlinear transmission [17].
R EFERENCES
[1] A. Kashyap, T. Başar, and R. Srikant, “Quantized consensus,” Automatica, pp. 1192–1203, 2007.
[2] T. Başar, S. R. Etesami, and A. Olshevsky, “Fast convergence of
quantized consensus using Metropolis weights,” proc. 53rd IEEE
Conference on Decision and Control (CDC’14, Dec 15-17, 2014; Los
Angeles, CA).
[3] M. Zhu and S. Martı́nez, “On the convergence time of asynchronous
distributed quantized averaging algorithms,” Automatic Control, IEEE
Transactions on, vol. 56, no. 2, pp. 386–390, 2011.
[4] R. Carli, F. Fagnani, P. Frasca, and S. Zampieri, “Gossip consensus
algorithms via quantized communication,” Automatica, vol. 46, no. 1,
pp. 70–80, 2010.
[5] F. Bénézit, P. Thiran, and M. Vetterli, “Interval consensus: from quantized gossip to voting,” in Acoustics, Speech and Signal Processing,
2009. ICASSP 2009. IEEE International Conference on. IEEE, 2009,
pp. 3661–3664.
[6] K. Cai and H. Ishii, “Convergence time analysis of quantized gossip
consensus on digraphs,” Automatica, vol. 48, pp. 2344–2351, 2012.

[7] L. Xiao, S. Boyd, and S.-J. Kim, “Distributed average consensus
with least-mean-square deviation,” Journal of Parallel and Distributed
Computing, vol. 67, no. 1, pp. 33–46, 2007.
[8] S. R. Etesami and T. Başar, “Convergence time for unbiased quantized
consensus over static and dynamic networks,” IEEE Transactions on
Automatic Control, vol. 61(4), April 2016 (to appear).
[9] S. Shang, P. Cuff, P. Hui, and S. Kulkarni, “An upper bound on
the convergence time for quantized consensus,” in INFOCOM, 2013
Proceedings IEEE. IEEE, 2013, pp. 600–604.
[10] D. A. Levin, Y. Peres, and E. L. Wilmer, Markov Chains and Mixing
Times. American Mathematical Society, 2009.
[11] D. Aldous and J. Fill, Reversible Markov Chains and Random Walks
on Graphs. Berkeley, 2002.
[12] D. Coppersmith, P. Tetali, and P. Winkler, “Collisions among random
walks on a graph,” SIAM J. on Discrete Mathematics, vol. 6, pp. 363–
374, 1993.
[13] Y. Nonaka, H. Ono, K. Sadakane, and M. Yamashita, “The hitting and
cover times of Metropolis walks,” Theoretical Computer Science, vol.
411, no. 16, pp. 1889–1894, 2010.
[14] D. Fremlin, “Measure Theory,” vol. 2, ISBN 978-0-9538129-7-4.
[15] E. Seneta, Non-negative Matrices and Markov Chains. Springer,
2006.
[16] A. Olshevsky. (2014) Linear time average consensus on fixed graphs
and implications for decentralized optimization and multi-agent
control. [Online]. Available: http://arxiv.org/abs/1411.4186
[17] Y. Chen, J. Lü, and Z. Lin, “Consensus of discrete-time multi-agent
systems with transmission nonlinearity,” Automatica, vol. 49, no. 6,
pp. 1768–1775, 2013.

