of 8
On Quantized Consensus by Means of
Gossip Algorithm – Part II: Convergence Time
Javad Lavaei and Richard M. Murray
Abstract
— This paper deals with the distributed averaging
problem over a connected network of agents, subject to a
quantization constraint. It is assumed that at each time update,
only a pair of agents can update their own numbers in terms
of the quantized data being exchanged. The agents are also
required to communicate with one another in a stochastic
fashion. In the first part of the paper, it was shown that
the quantized consensus is reached by means of a stochastic
gossip algorithm proposed in a recent paper, for any arbitrary
quantization. The current part of the paper considers the
expected value of the time at which the quantized consensus
is reached. This quantity (corresponding to the worst case) is
lower and upper bounded in terms of the topology of the graph,
for uniform quantization. In particular, it is shown that the
upper bound is related to the principal minors of the weighted
Laplacian matrix. A convex optimization is also proposed to
determine the set of probabilities (used to pick a pair of agents)
which leads to the fast convergence of the gossip algorithm.
I. I
NTRODUCTION
During the past few decades, there has been a particular
interest in the area of distributed computations, which aims
to compute some quantity over a network of processors in
a decentralized fashion [1], [2]. The distributed averaging
problem, as a particular case, is concerned with computing
the average of numbers owned by the agents of a group
[3], [4]. This problem has been investigated through the
notion of consensus in several papers, motivated by different
applications [5], [6], [7], [8], [9], [10]. For instance, the
synchronization of coupled oscillators, arising in biophysics,
neurobiology, and systems biology, is studied in [5] and
[6] to explore how to reach a consensus on the oscillation
frequencies of all agents. Moreover, the problem of aligning
the heading angles of a group of mobile agents (e.g. a flock of
birds) is treated in [11]. Given a sensor network comprising
a set of sensors measuring the same quantity in a noisy
environment, the problem of consensus on state estimates
is discussed in [12]. The consensus problem for networks
of dynamic agents with fixed and switching topologies is
tackled in [3], where it is shown that the convergence rate
is related to the algebraic connectivity of the network. The
work [13] elaborates on the relationship between the amount
of information exchanged by the agents and the rate of
convergence to the consensus. A more complete survey on
this topic is given in the recent paper [4].
Consider the distributed average consensus in which the
values owned by the agents are to be averaged in a distributed
This work has been supported by AFOSR and Air Force MURI.
The authors are with the Department of Control and Dynamical
Systems, California Institute of Technology, Pasadena, USA (emails:
lavaei@cds.caltech.edu; murray@cds.caltech.edu).
fashion. Since it may turn out in some applications that all
agents cannot update their numbers synchronously, the gossip
algorithm has been widely exploited by researchers to handle
the averaging problem asynchronously [14], [15]. This type
of algorithm selects a pair of agents at each time instance,
and updates their values based on some averaging policy.
The consensus problem in the context of gossip algorithm has
been thoroughly investigated in the literature [16], [17], [18],
[19]. For instance, the work [16] studies the convergence of a
general randomized gossip algorithm, and derives conditions
under which the algorithm converges. That paper also shows
that the averaging time of a gossip algorithm depends on
the second largest eigenvalue of a doubly stochastic matrix
characterizing the algorithm.
In light of communication constraints, the data being
exchanged between each pair of agents is normally quan-
tized. This has given rise to the emergence of quantized
gossip algorithms. The notion of quantized consensus is
defined in [18] for the case when quantized values (inte-
gers) are to be averaged over a connected network with
digital communication channels. This paper shows that the
quantized gossip algorithm leads to reaching the quantized
consensus. This result is extended in [19] to the case when
the quantization is uniform, and the initial numbers owned
by the agents are reals (as opposed to being integers). The
paper [19] shows that the quantized gossip algorithm works
for a particular choice of the updating parameter, although
it conjunctures that this result is true for a wide range of
updating parameters. A related paper on quantized consensus
gives a synchronous algorithm in order to reach a consensus
with arbitrary precision, at the cost of not preserving the
average of the initial numbers [20].
In this paper, a weighted connected graph is considered
together with a set of scalars sitting on its vertices. The
weight of each edge represents the probability of establishing
a communication between its corresponding vertices through
the updating procedure. It was shown in Part I of this work
that the quantized consensus is reached under the stochastic
gossip algorithm proposed in [19], for a wide range of
updating parameters and any arbitrary quantizer including
uniform and logarithmic ones [21]. The current part of the
paper is concerned with the convergence time of the gossip
algorithm. More precisely, consider the expected value of
the time at which the consensus is reached, and take its
maximum over all possible initial states belonging to a given
hypercube. Lower and upper bounds on the this quantity are
provided for a uniform quantizer, which turn out to be related
to the Laplacian of the weighted graph. The upper bound is
2009 American Control Conference
Hyatt Regency Riverfront, St. Louis, MO, USA
June 10-12, 2009
ThB10.6
978-1-4244-4524-0/09/$25.00 ©2009 AACC
2958
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:01 UTC from IEEE Xplore. Restrictions apply.
then minimized in order to obtain the best weights resulting
in a small convergence time. To do so, a convex optimization
problem is proposed, which can be solved by a semidefinite
program.
This paper is organized as follows. Some preliminaries
are presented in Section II, and the problem is formulated
accordingly. The main results on the convergence time are
provided in Section III. The results are then illustrated
in Section IV with a numerical example. Later on, some
concluding remarks are drawn in Section V. A number of
proofs are finally given in an appendix.
II. P
ROBLEM FORMULATION AND PRELIMINARIES
Consider a connected weighted graph
G
= (
V
,
E
,
P
)
,
where:
•
V
:=
{
v
1
, v
2
, ..., v
ν
}
is the set of vertices of
G
;
•
E
is the set of undirected edges of
G
;
•
P
:=
{
p
ij
}
i,j
is the set of weights assigned to the edges
of
G
.
Assume that:
•
The quantity
∑
p
ij
is equal to 1, where the sum is
taken over all numbers
i, j
∈
ν
:=
{
1
,
2
, ..., ν
}
such
that
i
≤
j
.
•
The number
p
ij
(
i, j
∈
ν
) is equal to zero if
(
i, j
)
6∈E
; otherwise, it is strictly positive. In particular,
p
11
, p
22
, ..., p
νν
are all equal to zero.
The scalar
p
ij
associated with the edge
(
i, j
)
represents the
probability of choosing the edge
(
i, j
)
when an edge of
G
is to be picked at random. Suppose that a real number
x
i
has been assigned to the vertex
v
i
, for all
i
∈
ν
. Let
q
(
x
) :
R
→
R
be a general quantization operator characterized as
follows:
q
(
x
) =
{
L
i
if
x
∈
[
L
i
,
̄
L
i
]
L
i
+1
if
x
∈
(
̄
L
i
, L
i
+1
]
∀
i
∈
Z
(1)
where
{
L
i
}
∞
−∞
is a monotonically increasing sequence of
integers representing the quantization levels, and:
̄
L
i
:=
L
i
+
L
i
+1
2
,
∀
i
∈
Z
(2)
Note that
Z
denotes the set of integers. In what follows, a
quantized stochastic gossip algorithm is presented [19].
Stochastic Gossip (SG) Algorithm:
Step 1
: Given a positive real
ε
, set
k
= 0
. Define
x
i
[0] :=
x
i
,
for any
i
∈
ν
.
Step 2
: Pick an edge of
G
at random.
Step 3
: Suppose that the ending vertices of the edge selected
in Step 2 possess the values
x
i
[
k
]
and
x
j
[
k
]
. Perform the
following updates:
x
i
[
k
+ 1] =
x
i
[
k
] +
ε
×
(
q
(
x
j
[
k
])
−
q
(
x
i
[
k
])
)
,
x
j
[
k
+ 1] =
x
j
[
k
] +
ε
×
(
q
(
x
i
[
k
])
−
q
(
x
j
[
k
])
)
,
x
q
[
k
+ 1] =
x
q
[
k
]
,
∀
q
∈
ν
\{
i, j
}
(3)
Step 4
: Increase
k
by 1 and jump to Step 2.
Let the short-hand notation:
x
[
k
] =
[
x
1
[
k
]
x
2
[
k
]
···
x
ν
[
k
]
]
, k
∈
Z
(4)
be used hereafter. Observe that the SG algorithm is stochastic
in the sense that an edge must be chosen
at random
at
each time update. The deterministic version of this algorithm,
referred to as the deterministic gossip (DG) algorithm, can
be obtained by replacing its step 2 with the following:
Step 2
: Pick an edge of
G
arbitrarily
(at the discretion of
the user).
Throughout this paper, the symbol
G
(
V
,
E
,
P
)
refers to the
weighted graph
G
, whereas the symbol
G
(
V
,
E
)
refers to the
graph
G
with the weights on its edges removed.
Definition 1:
Given a quantization-based protocol
C
act-
ing on
G
(
V
,
E
)
, denote with
x
[
k
]
,
k
∈
N
∪{
0
}
, the vector
of values on the vertices of
G
at time
k
, obtained using this
protocol. It is said that the
quantized consensus
is reached
for the graph
G
under the protocol
C
if for every arbitrary
initial state
x
[0]
∈
R
ν
, there exist a natural number
k
0
and
an integer
μ
such that either of the following sets of relations
holds:
∑
ν
i
=1
x
i
[
k
] =
∑
ν
i
=1
x
i
[0]
x
j
[
k
]
∈
[
L
μ
, L
μ
+1
]
∀
k
≥
k
0
,
∀
j
∈
ν
(5)
or:
∑
ν
i
=1
x
i
[
k
] =
∑
ν
i
=1
x
i
[0]
x
j
[
k
]
∈
(
̄
L
μ
,
̄
L
μ
+1
]
∀
k
≥
k
0
,
∀
j
∈
ν
(6)
In line with the above definition, if the protocol
C
is
stochastic, one would say that the quantized consensus is
reached
almost surely
if there exists a number
k
0
∈
N
,
with probability 1, for which either of the relations (5)
or (6) holds. For simplicity, the short name
consensus
is
used hereafter in order to refer to
quantized consensus
. A few
definitions and notations will be introduced in the sequel.
Definition 2:
Define
S
to be the set of all
ν
-tuple
(
α
1
, α
2
, ..., α
ν
)
such that
α
i
∈
[
x
min
, x
max
]
and, in addition,
α
i
−
x
i
is an integer multiple of
ε
, for all
i
∈
ν
, where:
x
max
:= max
i
∈
ν
d
x
i
e
, x
min
:= min
i
∈
ν
b
x
i
c
(7)
(The notations
d·e
and
b·c
stand for the ceiling and floor
operators, respectively).
Definition 3:
Let
η
1
and
η
2
be:
η
1
= max
i
∈
Z
̄
L
i
s.t.
̄
L
i
≤
x
ave
,
η
2
= min
j
∈
Z
̄
L
j
s.t.
̄
L
j
≥
x
ave
(8)
where
x
ave
:=
x
1
+
x
2
+
···
+
x
ν
ν
.
Definition 4:
Define:
S
o
:=
{
(
α
1
, α
2
, ..., α
ν
)
∈S
∣
∣
α
i
∈
(
η
1
, η
2
]
,
∀
i
∈
ν
}
Furthermore, let
S
o
(
̄
L
i
)
,
i
∈
Z
, be defined as the set of all
ν
-tuple
(
α
1
, α
2
, ..., α
ν
)
∈S
such that:
α
j
∈
(
̄
L
i
−
ε
(
L
i
+1
−
L
i
)
,
̄
L
i
+
ε
(
L
i
+1
−
L
i
)
]
,
∀
j
∈
ν
(9)
2959
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:01 UTC from IEEE Xplore. Restrictions apply.
Definition 5:
Define the distance function
d
ε
(
·
,
S
o
) :
S→
Z
as:
d
ε
(
α
,
S
o
) := min
β
∈S
o
|
α
−
β
|
1
ε
,
∀
α
∈S
(10)
where
|·|
1
denotes the
L
1
norm. Define also the distance
function
d
ε
(
·
,
S
o
(
μ
))
in the same vein.
The next result was proved in Part I of the paper [21].
Theorem 1:
Given
ε
∈
(0
,
0
.
5]
, apply the SG algorithm to
the graph
G
(
V
,
E
,
P
)
with the initial state
x
[0]
. There exists
a positive number
k
1
for which one of the following cases
takes place with probability 1:
i)
x
[
k
]
belongs to the set
S
o
, for every
k
≥
k
1
.
ii)
x
[
k
]
belongs to the set
S
o
(
η
1
)
, for every
k
≥
k
1
.
iii)
x
[
k
]
belongs to the set
S
o
(
η
2
)
, for every
k
≥
k
1
.
It is noteworthy that the above theorem proves reaching the
consensus and, besides, describes the steady-state behavior
of the system. In order to study the convergence time of the
SG algorithm, it is desired to find lower and upper bounds
on the quantity
k
1
introduced in Theorem 1. Throughout the
rest of this paper, assume that
q
(
x
)
is a uniform quantizer,
i.e., it rounds each real number
x
to its nearest integer (by
convention, assume that
q
(
r
+ 0
.
5) =
r
, for all integers
r
).
III. C
ONVERGENCE TIME
Since the SG algorithm is stochastic, the quantity
k
1
introduced in Theorem 1 is a random variable. Define
t
c
(
ε
)
to be equal to
max
E
{
k
1
}
, where the maximum is taken
over all initial states
x
[0]
∈
[
x
min
, x
max
]
ν
that belong to
none of the steady-state sets
S
o
,
S
o
(
η
1
)
and
S
o
(
η
2
)
(note
that
E
{·}
denotes the expectation operator). The term
t
c
(
ε
)
indeed quantifies the expected value of the convergence time
in the worst case. This section aims to characterize
t
c
(
ε
)
in terms of
x
min
, x
max
, ε
, and the topology of the graph
(together with the probabilities assigned to its edges).
Definition 6:
Given an integer
r
, apply the SG (or DS)
algorithm to the graph
G
(
V
,
E
,
P
)
with the initial state
x
[0]
.
The action of choosing an edge at time
k
(
k
∈
N
) in step 2
of the SG (or DS) algorithm is said to be a
positive action
with respect to (w.r.t.)
d
ε
(
·
,
S
o
(
r
+ 0
.
5))
if the inequality:
d
ε
(
x
[
k
]
,
S
o
(
r
+ 0
.
5))
< d
ε
(
x
[
k
−
1]
,
S
o
(
r
+ 0
.
5))
(11)
holds; otherwise, it is called a
trivial action
, meaning the
following (see Lemma 2 in [21]):
d
ε
(
x
[
k
]
,
S
o
(
r
+ 0
.
5)) =
d
ε
(
x
[
k
−
1]
,
S
o
(
r
+ 0
.
5))
(12)
Remark 1:
Regarding Definition 6, one can observe that
there is a reduction in the Lyapunov function
d
ε
(
·
,
S
o
(
r
+
0
.
5))
by at least 1 during each positive action. Moreover,
having assumed that the vertices
v
i
and
v
j
are chosen at
time
k
, where
x
i
[
k
−
1]
> x
j
[
k
−
1]
, it is straightforward to
show that a positive action occurs at this time if and only if
either of the following sets of relations holds:
•
x
i
[
k
−
1]
> r
+ 0
.
5 +
ε
and
x
j
[
k
−
1]
≤
r
+ 0
.
5
; or
•
x
i
[
k
−
1]
> r
+ 0
.
5
and
x
j
[
k
−
1]
≤
r
+ 0
.
5
−
ε
.
Definition 7:
Given
α
∈
R
ν
and
r
∈
Z
, define
T
r,ε
(
α
)
to be the time at which the first positive action is taken w.r.t.
d
ε
(
·
,
S
o
(
r
+ 0
.
5))
, provided the SG algorithm is applied to
the graph
G
(
V
,
E
,
P
)
with the initial state
α
. Notice that
since the SG algorithm is stochastic,
T
r,ε
(
α
)
is a random
variable.
Definition 8:
Given
α
∈
R
ν
, let
H
denote an infinite
sequence whose elements all belong to
E
(i.e.
H
is an infinite
sequence of edges). Define
T
r,ε
(
α
∣
∣
H
)
to be equal to the time
when the first positive action is taken w.r.t.
d
ε
(
·
,
S
o
(
r
+0
.
5))
,
provided that the DG algorithm is applied to the graph
G
(
V
,
E
)
with the initial state
α
, where the edge selected at
time
k
in step 2 of this algorithm is indeed the
k
th
element
of
H
, for all
k
∈
N
.
Definition 9:
For every integer
r
and infinite sequence of
edges
H
, define:
ζ
(
ε, r,
H
) := max
T
r,ε
(
β
∣
∣
H
)
(13)
where the maximum is taken over all
ν
-tuple
β
:=
[
β
1
···
β
ν
]
∈
[
x
min
, x
max
]
ν
with the following prop-
erties:
•
β
6∈S
o
(
r
+ 0
.
5)
;
•
There exist
i, j
∈
ν
such that:
–
β
i
> r
+ 0
.
5 +
ε
and
β
j
≤
r
+ 0
.
5
; or
–
β
i
> r
+ 0
.
5
and
β
j
≤
r
+ 0
.
5
−
ε
.
Theorem 2:
Given an integer
r
and an infinite sequence
of edges
H
, there exists a vector
α
:=
[
α
1
···
α
ν
]
such that:
ζ
(
ε, r,
H
) =
T
0
,
0
.
5
(
α
∣
∣
H
)
,
(14a)
{
α
1
, α
2
, ..., α
ν
}
=
{
0
.
25
,
0
.
75
, ....,
0
.
75
,
1
.
25
}
(14b)
where that the number
0
.
75
appears
ν
−
2
times in the set
given above
Proof:
The proof is based on a series of Lemmas provided
in the appendix.

Theorem 2 states that the quantity
ζ
(
ε, r,
H
)
, introduced in
Definition 9, is independent of
r
and
ε
. Instead, it is continent
upon only
H
and
G
.
Define
Φ
as follows:
Φ := max
E
{
T
0
,
0
.
5
(
α
)
}
(15)
where the maximum is taken over all
ν
-tuple
α
=
[
α
1
···
α
ν
]
satisfying the relation
{
α
1
, α
2
, ..., α
ν
}
=
{
0
.
25
,
0
.
75
, ....,
0
.
75
,
1
.
25
}
in which the value
0
.
75
appears
ν
−
2
times. The following theorem presents one of the main
results of this section.
Theorem 3:
Given a real
ε
∈
(0
,
0
.
5]
, the quantity
t
c
(
ε
)
can be lower and upper bounded as follows:
Φ
≤
t
c
(
ε
)
≤
ν
(
x
max
−
x
min
+ 2)Φ
ε
(16)
Proof:
It follows immediately from the definition of
Φ
that
this quantity is a lower bound on
t
c
(
ε
)
. To prove the other
part of the inequality, assume with no loss of generality that:
x
ave
−
x
min
≥
x
max
−
x
ave
(17)
Recall that the proof of Theorem 2 in Part I of the paper
introduces two storage functions
V
1
[
k
]
and
V
2
[
k
]
. It also
suggests minimizing
V
1
[
k
]
until it reaches a constant level,
2960
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:01 UTC from IEEE Xplore. Restrictions apply.
and subsequently minimizing
V
2
[
k
]
(in other words, the edge
being selected in step 2 of the algorithm at each update
is to be chosen in such a way that the storage function is
minimized). It follows from inequality (17) and the relation
|
x
ave
−
η
1
|≤
1
that:
V
1
[0]
≤
ν
∑
i
=1
|
x
i
−
η
1
|
ε
≤
ν
x
ave
−
x
min
+ 1
ε
(18)
At time
k
=
k
0
where the minimum of
V
1
[
k
]
is reached,
two possibilities can occur according to Lemma 3 in Part I
of the paper. The first one is that
x
[
k
0
]
∈S
o
(
η
1
)
, which
implies that the consensus is reached, and there is no need
to minimize
V
2
[
k
]
any longer. The second scenario is that
the relation
x
i
[
k
0
]
> η
1
holds for all
i
∈
ν
. Assume that the
latter one is the case. It is easy to verify that:
V
2
[
k
0
]
≤
ν
∑
i
=1
|
x
i
[
k
0
]
−
η
2
|
ε
≤
ν
x
max
−
x
ave
+ 1
ε
(19)
As a result:
V
1
[0] +
V
2
[
k
0
]
≤
ν
(
x
max
−
x
min
+ 2)
ε
(20)
On the other hand, the aforementioned discussion indicates
that at most
V
1
[0] +
V
2
[
k
0
]
positive actions are required
to reach the consensus. Moreover, it can be inferred from
Theorem 2 that the expected value of the time between two
consecutive positive actions is at most equal to
Φ
(until the
consensus is reached). These facts along with inequality (20)
complete the proof.

Theorem 3 implies that
t
c
(
ε
)
can be upper bounded by a
term which is proportional to the inverse of
ε
. The question
arises: how to compute
Φ
systematically? This is addressed
in the sequel. The following definitions/notations will be
convenient to proceed with the development of the paper.
•
Let
P
be the Laplacian of the weighted graph
G
. In other
words,
P
is a
ν
×
ν
matrix whose
(
i, j
)
off-diagonal
entry,
i, j
∈
ν
, i
6
=
j
, is equal to
−
p
ij
and its
(
i, i
)
diagonal entry,
i
∈
ν
, is equal to
∑
ν
k
=1
p
ki
.
•
For every
i
∈
ν
and
M
∈
R
ν
×
ν
, define
M
∼
i
to be the
matrix obtained from
M
by removing its
i
th
row and
i
th
column.
Theorem 4:
The quantity
Φ
can be obtained as follows:
Φ = max
i
∈
ν
∣
∣
(
P
∼
i
)
−
1
E
∣
∣
∞
(21)
where
|·|
∞
stands for the infinity norm, and
E
∈
R
ν
−
1
is
a vector of 1’s.
Proof:
For every
i, j
∈
ν
, i
6
=
j
, let
β
ij
denote a
ν
-
dimensional vector whose elements are all equal to
0
.
75
,
except for the
i
th
and
j
th
entries which are
0
.
25
and
1
.
25
,
respectively. In addition, denote the quantity
E
{
T
0
,
0
.
5
(
β
ij
)
}
with
̄
t
c
(
i, j
)
for simplicity. The goal is to contrive a recursive
equation characterizing
̄
t
c
(
i, j
)
. To this end, consider the
graph
G
with the initial state
β
ij
. The expected value of
the time at which the first positive action is taken (under the
SG algorithm) is, by definition, equal to
̄
t
c
(
i, j
)
. To count
this number in another way, run the algorithm one iteration.
Assume that the edge
e
μ
is chosen in this iteration, which
leads to the following possibilities:
•
e
μ
is equal to the edge
(
i, k
)
, for some
k
∈
ν
\{
j
}
:
In
this case, due to the equality
x
[0] =
β
ij
, the vector
x
[1]
is obtained as
β
kj
. Hence, it is expected to take the first
positive action after
̄
t
c
(
k, j
)
time updates (in addition
to the first time update taken at the beginning).
•
e
μ
is equal to the edge
(
i, j
)
:
This means that a positive
action is already taken at the first time update.
•
e
μ
is equal to the edge
(
k, l
)
, for some
k, l
∈
ν
\{
i
}
:
In this case, it is easy to show that
x
[1] =
x
[0] =
β
ij
.
This implies that it is expected to take the first positive
action after
̄
t
c
(
i, j
)
time updates (other than the first one
already taken).
The above reasoning yields the recursive equation:
̄
t
c
(
i, j
) = 1 +
∑
k
∈
ν
\{
j
}
p
ik
̄
t
c
(
k, j
)
+
(
1
−
ν
∑
k
=1
p
ik
)
̄
t
c
(
i, j
)
,
∀
i
∈
ν
\{
j
}
(22)
Stack the scalars
̄
t
c
(1
, j
)
, ...,
̄
t
c
(
j
−
1
, j
)
,
̄
t
c
(
j
+ 1
, j
)
,
...,
̄
t
c
(
ν, j
)
in a column and denote the resulting vector with
̄
t
c
(
j
)
∈
R
ν
−
1
. Equation (22) can be re-arranged as:
P
∼
j
̄
t
c
(
j
) =
E,
∀
j
∈
ν
(23)
Therefore:
Φ = max
i,j
∈
ν
, i
6
=
j
̄
t
c
(
i, j
) = max
j
∈
ν
|
̄
t
c
(
j
)
|
∞
= max
j
∈
ν
|
(
P
∼
j
)
−
1
E
|
∞
(24)
This completes the proof.

The results of Theorems 3 and 4 can be combined to
explicitly bound the quantity
t
c
(
ε
)
as follows:
max
j
∈
ν
|
(
P
∼
j
)
−
1
E
|
∞
≤
t
c
(
ε
)
(25)
and
t
c
(
ε
)
≤
ν
(
x
max
−
x
min
+ 2)
ε
max
j
∈
ν
|
(
P
∼
j
)
−
1
E
|
∞
(26)
The next theorem directly relates the upper bound on
t
c
(
ε
)
to the spectral of the principal submatrices of the Laplacian.
Theorem 5:
The scalar
t
c
(
ε
)
satisfies the following in-
equality:
t
c
(
ε
)
≤
ν
√
ν
−
1(
x
max
−
x
min
+ 2)
ε
(
max
i
∈
ν
1
λ
min
{
P
∼
i
}
)
(27)
where
λ
min
(
·
)
represents the smallest eigenvalue of a matrix.
Proof:
One can write:
|
(
P
∼
j
)
−
1
E
|
∞
≤|
(
P
∼
j
)
−
1
|
∞
|
E
|
∞
=
|
(
P
∼
j
)
−
1
|
∞
≤
√
ν
−
1
|
(
P
∼
j
)
−
1
|
2
(28)
where
|·|
2
stands for the 2-norm. Since the weighted Lapla-
cian matrix
P
is positive semi-definite (PSD), its principal
submatrix
P
∼
j
is PSD too. As a result, it can be deduced
from the above inequality that:
|
(
P
∼
j
)
−
1
E
|
∞
≤
√
ν
−
1
1
λ
min
{
P
∼
j
}
(29)
2961
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:01 UTC from IEEE Xplore. Restrictions apply.
The proof is completed by combining inequalities (26)
and (29).

Remark 2:
Theorem 5 states that the convergence time
t
c
(
ε
)
is related to the
(
ν
−
1)
th
order submatrices of the
Laplacian of the graph (i.e.
P
∼
i
,
i
∈
ν
), rather than
the Laplacian itself. Let
λ
2
(
P
)
denote the second smallest
eigenvalue of
P
. Since the graph
G
is connected,
λ
2
(
P
)
is strictly positive. Now, the interlacing theorem can be
exploited to argue that:
0
< λ
min
{
P
∼
j
}≤
λ
2
(
P
)
(30)
This means that unlike the unquantized consensus whose
convergence mainly depends on
λ
2
(
P
)
, a more subtle de-
pendency on
λ
2
(
P
)
is governed for the quantized case (in
fact,
Φ
is not directly related to
λ
2
(
P
)
).
Remark 3:
The quantity
Φ
introduced in this section is
an important parameter, which characterizes the expected
value of the maximum number of iterations that must be
followed until a positive action is taken. The derived lower
and upper bounds on
t
c
(
ε
)
have been related to this quantity
corresponding to the worst case. Since the graph system is
stochastic, it is unlikely in practice that the system operates
in the worst case, which implies that the actual convergence
time of a random system may be much better than the bounds
obtained here. Nevertheless, these bounds are instrumental in
understating the worst-case behavior of the system and how
the convergence time is related to the topology of the graph.
A. Special graphs
This subsection aims to obtain lower and upper bounds on
the quantity
t
c
(
ε
)
for both complete and path graphs in the
case when all edges have the same weight. In this regard,
assume that each edge is associated with the same weight
p
.
Corollary 1:
For a complete graph
G
with equally
weighted edges, the following inequality holds:
ν
(
ν
−
1)
2
≤
t
c
(
ε
)
≤
ν
2
(
ν
−
1)(
x
max
−
x
min
+ 2)
2
ε
(31)
Proof:
The weight
p
for this graph is equal to
2
ν
(
ν
−
1)
.
Using this fact and by means of Theorems 3 and 4, it is
straightforward to show the validity of inequality (31). The
details are omitted here.

Corollary 2:
Let
G
be a path graph with equally weighted
edges so that
v
i
is connected to
v
i
+1
, for all
i
∈{
1
,
2
, ..., ν
−
1
}
(these are the only edges of the graph). The inequality
given below holds:
ν
(
ν
−
1)
2
2
≤
t
c
(
ε
)
≤
ν
2
(
ν
−
1)
2
(
x
max
−
x
min
+ 2)
2
ε
(32)
Proof:
Since the graph
G
has
ν
−
1
edges, the weight
p
is
equal to
1
ν
−
1
. On the other hand, it is easy to show that
Φ =
̄
t
c
(1
, ν
)
. This leads to the following recursive equations
(in light of (22)):
p
̄
t
c
(1
, ν
)
−
p
̄
t
c
(2
, ν
) = 1
(33a)
−
p
̄
t
c
(
i
−
1
, ν
) + 2
p
̄
t
c
(
i, ν
)
−
p
̄
t
c
(
i
+ 1
, ν
) = 1
(33b)
−
p
̄
t
c
(
ν
−
2
, ν
) + 2
p
̄
t
c
(
ν
−
1
, ν
) = 1
(33c)
where the argument
i
in equation (33b) belongs to the set
{
2
,
3
, ..., ν
−
2
}
. Adding up these equalities results in the
relation:
p
̄
t
c
(
ν
−
1
, ν
) =
ν
−
1
(34)
The (backward) recursive equation (33b) can be solved using
conventional techniques to conclude that there exist two
constants
a
and
b
such that:
p
̄
t
c
(
i, ν
) =
a
+
bi
−
i
2
2
, i
=
ν
−
1
, ν
−
2
, ...,
1
(35)
One can employ the final conditions given by (33c) and (34)
to arrive at:
a
=
ν
2
−
ν
2
, b
=
1
2
(36)
This implies that:
Φ =
̄
t
c
(1
, ν
) =
ν
2
−
ν
2
p
=
ν
(
ν
−
1)
2
2
(37)
The proof follows immediately from the above equation and
Theorem 3.

B. Optimal edge weights
In this subsection, it is desired to find out what probabil-
ities the edges of
G
should possess so that the consensus is
reached quickly. For this purpose, observe that the quantity
t
c
(
ε
)
has been related to the spectral of the submatrices of
the Laplacian in (27). Having fixed
x
min
,
x
max
and
ε
, the
provided upper bound on
t
c
(
ε
)
is a multiple of the term:
max
i
∈
ν
1
λ
min
{
P
∼
i
}
(38)
Therefore, it is desired to minimize the function (38) over all
possible (discrete) probability distributions captured by
P
for
the sake of finding a sub-optimal edge-selection probability
distribution. This is accomplished in the sequel.
Problem 1:
Minimize the scalar variable
−
μ
subject to the
constraints:
λ
min
{
P
∼
i
}≥
μ, i
= 1
,
2
, ..., ν
(39)
where
P
is a matrix variable representing the Laplacian of
the weighted graph
G
. Denote the global minimizer of this
optimization with
(
μ
∗
, P
∗
)
(note that there are some implicit
constraints stating that the weights on the edges are positive
and sum up to 1).
Since the operator
λ
min
(
·
)
is concave w.r.t. its symmetric
argument, it is easy to show that Problem 1 is convex. More
precisely, the constraint
λ
min
{
P
∼
i
}≥
μ
can be expressed
as
P
∼
i

μI
, which is a semidefinite constraint. Hence, the
solution
P
∗
can be found efficiently. On the other hand, one
can verify that:
μ
∗
= max
P
min
i
λ
min
{
P
∼
i
}
(40)
or equivalently:
1
μ
∗
= min
P
max
i
1
λ
min
{
P
∼
i
}
(41)
2962
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:01 UTC from IEEE Xplore. Restrictions apply.
This implies that the solution
P
∗
gives a sub-optimal edge-
selection probability distribution (resulting in the fast con-
vergence of the SG algorithm), because of minimizing the
term given in (38).
IV. N
UMERICAL EXAMPLE
Consider the graph
G
drawn in Figure 1. The objective
is to find out what probabilities should be assigned to the
edges of
G
so that the consensus is reached quickly under
the SG algorithm. To this end, let the convex optimization
provided in Problem 1 be solved. This yields the following
probability distribution:
p
12
=
p
15
= 0
.
2087
,
p
23
=
p
24
=
p
45
=
p
35
= 0
.
1146
,
p
34
= 0
.
1241
(42)
The quantity
Φ
corresponding to this set of edge-selection
Fig. 1. The graph
G
rendered in the numerical example
probabilities turns out to be equal to
14
.
1770
. One can make
a comparison with two heuristic methods for designing the
probability set
P
, which are spelled out below:
•
The most naive approach is to assume that the edges
of the graph are equally weighted. This leads to the
probability
p
=
1
7
on each edge. The associated quantity
Φ
is obtained as
17
.
5
.
•
Another technique is to devise the probability distribu-
tion
P
in such a way that all vertices have the same
probability of being chosen at each time update, i.e.:
p
12
+
p
15
=
p
21
+
p
23
+
p
24
=
p
32
+
p
34
+
p
35
=
p
42
+
p
43
+
p
45
=
p
51
+
p
53
+
p
54
(43)
Note that
p
ij
=
p
ji
,
∀
i, j
∈
ν
. The above set of
equations has a unique symmetric solution (complying
with the symmetry of the graph
G
) as follows:
p
12
=
p
15
= 0
.
2
,
p
23
=
p
24
=
p
45
=
p
35
= 0
.
1
,
p
34
= 0
.
2
(44)
The corresponding
Φ
is equal to
15
.
Hence, the value of
Φ
corresponding to the sub-optimal
solution is better from the ones obtained using these two
rudimentary techniques.
An interesting fact about the edge selection can be seen
in this example. Assume that the graph
G
does not have the
edge
(1
,
5)
(i.e. remove this edge). In this case, Problem 1
leads to the following solution:
p
12
= 0
.
3781
, p
23
=
p
24
= 0
.
1757
,
p
34
= 0
, p
53
=
p
54
= 0
.
1352
(45)
associated with
Φ = 23
.
1292
. Notice that
p
34
= 0
, which
signifies that although a complete graph has the best con-
vergence, if some edges do not exist (e.g. the edge
(1
,
5)
),
it might be better to ignore some other edges too (e.g. the
edge
(3
,
4)
). This is interesting as it reveals the fact that some
communications are redundant.
To compare the value obtained for
Φ
with other possible
values, consider the case when all edges have the same
weight. This results in the equality
Φ = 36
. Therefore, there
is a noticeable improvement in the value of
Φ
via the solution
of Problem 1.
For the purpose of simulation, the following points have
been randomly generated in the interval
[0
,
100]
:
x
1
[0] = 20
.
1185
, x
2
[0] = 13
.
6221
, x
3
[0] = 97
.
8356
,
x
4
[0] = 45
.
5033
, x
5
[0] = 45
.
9224
(46)
The stochastic gossip algorithm was run 1000 times and the
average of the scalar
k
1
was calculated accordingly (note
that
k
1
is a random variable). This value for the probability
distribution (45) was obtained as 48.5710, while that for
the identical probability distribution (equal edge weights)
turned out to be 65.3580. This demonstrates that one could
significantly save in the convergence time if the solution of
Problem 1 is employed, which also obviates the usage of the
edge
(3
,
4)
.
V. C
ONCLUSIONS
This paper tackles the average consensus problem over
a connected weighted graph subject to a quantization con-
straint. It is assumed that each pair of vertices can be chosen
with a certain probability in order to update their numbers
in term of the quantized data being exchanged. In the first
part of the paper, it was shown that the quantized consensus
is reached under the stochastic gossip algorithm given in a
recent paper. This part of the paper deals with the time at
which the consensus is reached. Lower and upper bounds
on the expected value of this quantity in the worst case
are provided, which depend on the principal minors of the
Laplacian matrix of the weighted graph. These bounds are
explicitly computed for equally weighted complete and path
graphs. Finally, a convex optimization is provided to obtain
a set of weights on the edges of the graph that results in the
fast convergence of the gossip algorithm.
R
EFERENCES
[1] G. Tel, “Introduction to distributed algorithms,” Cambridge University
Press, 2000.
[2] N. A. Lynch, “Distributed algorithms,” Morgan Kaufmann Publishers,
Inc., San Francisco, CA, 1996.
2963
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:01 UTC from IEEE Xplore. Restrictions apply.
[3] R. Olfati-Saber and R. M. Murray, “Consensus problems in networks
of agents with switching topology and time-delays,”
IEEE Transac-
tions on Automatic Control
, vol. 49, no. 9, pp. 1520-1533, 2004.
[4] R. Olfati-Saber, J. A. Fax and R. M. Murray, “Consensus and coop-
eration in networked multi-agent systems,”
Proceedings of the IEEE
,
vol. 95, no. 1, pp. 215-233, 2007.
[5] Y. Kuramoto, “Chemical oscillators, waves, and turbulance,” Springer-
Verlag, Berlin, 1984.
[6] S. H. Strogatz, “Exploring complex networks,”
Nature
, vol. 410, pp.
268-276, 2001.
[7] D. P. Bertsekas and J. N. Tsitsiklis, “Parallel and distributed compu-
tation: Numerical methods,” Belmont, MA: Athena Scientific, 1997.
[8] Y. Rabani, A. Sinclair and R. Wanka,“Local divergence of Markov
chains and the analysis of iterative load-balancing schemes,” in
Pro-
ceedings of IEEE Conference on Foundations of Computer Science
,
1998.
[9] A. V. Savkin, “Coordinated collective motion of groups of autonomous
mobile robots: Analysis of Vicsek
́
s model,”
IEEE Transactions on
Automatic Control
, vol. 49, no. 6, pp. 981982, 2004.
[10] R. Olfati-Saber, “Flocking for multi-agent dynamic systems: Algo-
rithms and theory,”
IEEE Transactions on Automatic Control
, vol. 51,
no. 3, pp. 401420, 2006.
[11] A. Jadbabaie, J. Lin, and A. S. Morse, “Coordination of groups
of mobile autonomous agents using nearest neighbor rules,”
IEEE
Transactions on Automatic Control
, vol. 48, no. 6, pp. 9881001, 2003.
[12] A. Speranzon, C. Fischione and K.H. Johansson, “Distributed and col-
laborative estimation over wireless sensor networks,” in
Proceedings
of the 45th IEEE Conference on Decision and Control
, 2006.
[13] R. Carli, F. Fagnani, A. Speranzon and S. Zampieri, “Communication
constraints in the average consensus problem,”
Automatica
, vol. 44,
no. 3, pp. 671-684, 2008.
[14] J. Tsitsiklis, “Problems in decentralized decision making and com-
putation,” PhD thesis, Dept. of Electrical Engineering and Computer
Science, M.I.T., Boston, MA, 1984.
[15] S. Boyd, A. Ghosh, B. Prabhakar and D. Shah , “Analysis and
optimization of randomized gossip algorithms,” in
Proceedings of the
43rd IEEE Conference on Decision and Control
, 2004.
[16] S. Boyd, A. Ghosh, B. Prabhakar and D. Shah , “Randomized gossip
algorithms,”
IEEE Transactions on Information Theory
, vol. 52, no.
6, pp. 2508-2530, 2006.
[17] F. Benezit, A. G. Dimakis, P. Thiran and M. Vetterli, “Gossip along the
way: Order-optimal consensus through randomized path averaging,” in
Proceedings of the Allerton Conference on Communication, Control,
and Computing
, 2007.
[18] A. Kashyap, T. Basara and R. Srikanta, “Quantized consensus,”
Automatica
, vol. 43, no. 7, pp. 1192-1203, 2007.
[19] P. Frasca, R. Carli, F. Fagnani and S. Zampieri, “Average consensus
by gossip algorithms with quantized communication,” in
Proceedings
of the 47th IEEE Conference on Decision and Control
, 2008.
[20] A. Censi and R. M. Murray, “A biologically inspired approach to
real-valued average consensus over quantized channels with arbitrary
deterministic accuracy,” in
Proceedings of the 2009 American Control
Conference
, 2009.
[21] J. Lavaei and R. M. Murray, “On quantized consensus by means of
gossip algorithm – Part II: convergence time,” in
Proceedings of the
2009 American Control Conference
, 2009.
A
PPENDIX
This appendix derives a number of results in order to prove
Theorem 2.
Lemma 1:
Given
r
∈
Z
and
α
:=
[
α
1
···
α
ν
]
T
6∈
S
o
(
r
+ 0
.
5)
, the following hold for every infinite sequence
of edges
H
:
i) If
α
1
> r
+ 0
.
5 +
ε
, then:
T
r,ε
(
α
∣
∣
H
)
≤
T
r,ε
(
α
1
−
ε, α
2
, ..., α
ν
∣
∣
H
)
(47)
ii) If
α
1
≤
r
+ 0
.
5
−
ε
, then:
T
r,ε
(
α
∣
∣
H
)
≤
T
r,ε
(
α
1
+
ε, α
2
, ..., α
ν
∣
∣
H
)
(48)
Proof:
Let case (i) be proved here, as the other case is
analogous. Apply the DG algorithm to the graph
G
(
V
,
E
)
so
that its step 2 selects edges from the sequence
H
in order.
For the initial states
(
α
1
, α
2
, ..., α
ν
)
and
(
α
1
−
ε, α
2
, ..., α
ν
)
,
denote the resulting numbers on the vertices of
G
at time
k
with
w
[
k
] := (
w
1
[
k
]
, w
2
[
k
]
, ..., w
ν
[
k
])
and
̄
w
[
k
] :=
( ̄
w
1
[
k
]
,
̄
w
2
[
k
]
, ...,
̄
w
ν
[
k
])
, respectively, for all
k
∈
N
∪{
0
}
.
Furthermore, for notational simplicity, define:
m
:=
T
r,ε
(
α
1
−
ε, α
2
, ..., α
ν
∣
∣
H
)
(49)
In order to proceed with the proof by contradiction, assume
that there is no positive action w.r.t.
d
ε
(
·
,
S
o
(
r
+ 0
.
5))
at
time instants
1
,
2
, ..., m
, by starting from the initial state
α
.
In other words:
d
ε
(
w
[0]
,
S
o
(
r
+ 0
.
5)) =
d
ε
(
w
[
k
]
,
S
o
(
r
+ 0
.
5))
(50)
for any
k
∈{
0
,
1
,
2
, ..., m
}
. Now, one can draw a number of
conclusions as follows:
i)
w
1
[
k
]
is always greater than or equal to
̄
w
1
[
k
]
for every
k
satisfying the inequality
1
≤
k
≤
m
.
ii) It is a consequence of property (i) that
w
i
[
k
]
≥
̄
w
i
[
k
]
for every
i
∈
ν
and
k
∈{
1
, ..., m
}
.
iii) The relation
w
i
[
k
] = ̄
w
i
[
k
]
holds if
w
i
[
k
]
≤
r
+ 0
.
5
or
̄
w
i
[
k
]
≤
r
+ 0
.
5
, for every
i
∈
ν
and
k
∈
{
0
,
1
, ..., m
−
1
}
. This result can be easily proven by
induction on
k
, taking property (ii) into account, and
using the equality (50).
Assume that the
m
th
element of
H
is the edge
(
i, j
)
. With
no loss of generality, suppose that
̄
w
i
[
m
−
1]
≥
̄
w
j
[
m
−
1]
.
Since a positive action occurs at time
m
w.r.t.
d
ε
(
·
,
S
o
(
r
+
0
.
5))
by starting from the initial state
̄
w
[0]
, it follows from
Remark 1 that either of the cases pointed out below occurs:
a)
̄
w
i
[
m
−
1]
> r
+ 0
.
5 +
ε
and
̄
w
j
[
m
−
1]
≤
r
+ 0
.
5
; or
b)
̄
w
i
[
m
−
1]
> r
+ 0
.
5
and
̄
w
j
[
m
−
1]
≤
r
+ 0
.
5
−
ε
.
Assume that case (a) happens (the other case is similar).
Properties (ii) and (iii) mentioned above yield that:
w
i
[
m
−
1]
≥
̄
w
i
[
m
−
1]
> r
+ 0
.
5 +
ε,
w
j
[
m
−
1] = ̄
w
j
[
m
−
1]
≤
r
+ 0
.
5
(51)
Since the edge
(
i, j
)
is chosen at time
m
in step 2 of the
DG algorithm, the above inequalities and Remark 1 signify
that a positive action occurs at time
m
for the graph
G
(
V
,
E
)
with the initial state
α
=
w
[0]
. In other words,
T
r,ε
(
α
∣
∣
H
)
must be equal to
m
, while it has been already assumed that
this quantity is greater than
m
. This contradiction completes
the proof.

Proposition 1:
Given an integer
r
and an infinite sequence
of edges
H
, there exist an integer
κ
∈
ν
and a vector
α
=
[
α
1
···
α
ν
]
subject to:
ζ
(
ε, r,
H
) =
T
r,ε
(
α
∣
∣
H
)
,
(52a)
r
+ 0
.
5
−
ε <α
i
≤
r
+ 0
.
5 +
ε,
∀
i
∈
ν
\{
κ
}
(52b)
In addition,
α
κ
satisfies one of the following relations:
r
+ 0
.
5 +
ε < α
κ
≤
r
+ 0
.
5 + 2
ε
(53)
or:
r
+ 0
.
5
−
2
ε < α
κ
≤
r
+ 0
.
5
−
ε
(54)
2964
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:01 UTC from IEEE Xplore. Restrictions apply.
Proof:
The proof follows from Lemma 1. The details
are omitted here for brevity. Note that the reason why
inequality (52) is not satisfied for every
i
in
ν
(i.e. there
is a
κ
for which this inequality does not hold) is that
α
should not belong to
S
o
(
r
+ 0
.
5)
, in light of Definition 9.

Lemma 2:
Consider a vector
α
=
[
α
1
···
α
ν
]
and
an integer
r
∈
Z
satisfying the relations:
r
+ 0
.
5 +
ε < α
1
≤
r
+ 0
.
5 + 2
ε,
r
+ 0
.
5
−
ε < α
2
≤
r
+ 0
.
5
,
r
+ 0
.
5
−
ε < α
i
≤
r
+ 0
.
5 +
ε,
∀
i
∈
ν
\{
1
,
2
}
(55)
For every infinite sequence of edges
H
, the inequality given
below holds:
T
r,ε
(
α
∣
∣
H
)
≤
T
r,ε
(
α
1
, α
2
+
ε, ..., α
ν
∣
∣
H
)
(56)
Proof:
Apply the DG algorithm to the graph
G
(
V
,
E
)
and
select edges in its step 2 from the sequence
H
succes-
sively. For the initial states
(
α
1
, α
2
, ..., α
ν
)
and
(
α
1
, α
2
+
ε, ..., α
ν
)
, denote the resulting numbers on the vertices of
G
at time
k
with
u
[
k
] := (
u
1
[
k
]
, u
2
[
k
]
, ..., u
ν
[
k
])
and
̄
u
[
k
] :=
( ̄
u
1
[
k
]
,
̄
u
2
[
k
]
, ...,
̄
u
ν
[
k
])
, respectively, for all
k
∈
N
∪{
0
}
.
Define also:
g
:=
T
r,ε
(
α
1
, α
2
+
ε, ..., α
ν
∣
∣
H
)
(57)
For a proof by contradiction, assume that
T
r,ε
(
α
∣
∣
H
)
> g
.
Observe that:
i) Since
q
(
γ
) =
r
+ 1
, for all
γ
∈
(
r
+ 0
.
5
, r
+ 0
.
5 + 2
ε
]
,
it can be verified that:
u
1
[
k
] = ̄
u
1
[
k
] =
α
1
,
u
i
[
k
]
,
̄
u
i
[
k
]
∈
(
r
+ 0
.
5
−
ε, r
+ 0
.
5 +
ε
]
(58)
for all
k
∈{
0
,
1
, ..., g
−
1
}
and
i
∈
ν
\{
1
}
.
ii) Using property (i) and by means of induction on
k
, one
can show that if
̄
u
j
[
k
]
≤
r
+ 0
.
5
for some
j
∈
ν
and
k
∈{
0
,
1
, ..., g
−
1
}
, then
u
j
[
k
] = ̄
u
j
[
k
]
.
Let the
g
th
element of
H
be the edge
(
i, j
)
, where
i < j
.
It results from the definition of
g
and property (i) that
i
= 1
and
̄
u
j
[
g
−
1]
≤
r
+ 0
.
5
(this is the only way to generate
a positive action). Therefore, by properties (i) and (ii), one
can write:
u
j
[
g
−
1] = ̄
u
j
[
g
−
1]
≤
r
+ 0
.
5
,
u
1
[
g
−
1]
> r
+ 0
.
5 +
ε
(59)
As a result, Remark 1 leads to the conclusion that selecting
the edge
(
i, j
)
at time
g
results in a positive action for the
graph
G
(
V
,
E
)
with the initial state
α
; i.e.
T
r,ε
(
α
∣
∣
H
) =
g
.
This contradicts the aforementioned assumption.

Proposition 2:
Consider the objects
r
,
H
and
ζ
(
ε, r,
H
)
introduced in Proposition 1 and Definition 9. There exists a
vector
α
:=
[
α
1
···
α
ν
]
such that:
ζ
(
ε, r,
H
) =
T
r,ε
(
α
∣
∣
H
)
,
(60a)
{
α
1
, α
2
, ..., α
ν
}
=
{
r
+ 0
.
5
−
ε
2
, r
+ 0
.
5 +
ε
2
, ....,
r
+ 0
.
5 +
ε
2
, r
+ 0
.
5 + 3
ε
2
}
(60b)
(note that the term
r
+ 0
.
5 +
ε
2
appears
ν
−
2
times in the
above set).
Proof:
It follows from Proposition 1 and Lemma 2 that
there exist a vector
α
=
[
α
1
···
α
ν
]
and integers
μ
1
, μ
2
∈
ν
with the properties:
•
ζ
(
ε, r,
H
) =
T
r,ε
(
α
∣
∣
H
)
•
The set of inequalities:
r
+ 0
.
5 +
ε < α
μ
1
≤
r
+ 0
.
5 + 2
ε,
r
+ 0
.
5
−
ε < α
μ
2
≤
r
+ 0
.
5
,
r
+ 0
.
5
< α
i
≤
r
+ 0
.
5 +
ε,
∀
i
∈
ν
\{
μ
1
, μ
2
}
(61)
or:
r
+ 0
.
5
−
2
ε < α
μ
1
≤
r
+ 0
.
5
−
ε,
r
+ 0
.
5
< α
μ
2
≤
r
+ 0
.
5 +
ε,
r
+ 0
.
5
−
ε < α
i
≤
r
+ 0
.
5
,
∀
i
∈
ν
\{
μ
1
, μ
2
}
(62)
holds.
Due to the symmetry, one can assume with no loss of
generality that the set of inequalities given in (61) holds.
It is straightforward to show (using the above properties)
that
T
r,ε
(
α
∣
∣
H
)
is unchanged if the following replacements
are made:
•
α
μ
1
with
r
+ 0
.
5 +
3
ε
2
;
•
α
μ
2
with
r
+ 0
.
5
−
ε
2
;
•
α
i
with
r
+ 0
.
5 +
ε
2
, for any
i
∈
ν
\{
μ
1
, μ
2
}
.
This completes the proof.

The proof of Theorem 2 is a direct consequence of
Proposition 2 given above.
2965
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:01 UTC from IEEE Xplore. Restrictions apply.