Real-v
alued
av erage
consensus
ov er
noisy
quantized
channels
Andrea
Censi
Richard
M. Murray
Abstract
—
This
paper
concer
ns
the
av erage
consensus
prob-
lem
with
the
constraint
of
quan
tized
communication
between
nodes.
A
broad
class
of
algor
ithms
is
anal
yzed,
in
which
the
transmission
strategy
, which
decides
what
value
to communicate
to
the
neighbours,
can
include
various
kinds
of
rounding,
prob-
abilistic
quantization,
and
bounde
d
noise.
The
arbitrariness
of
the
transmission
strategy
is compensated
by
a feedback
mechanism
which
can
be
inter
preted
as
a self-inhibitory
action.
The
result
is that
the
av erage
of the
nodes
state
is
not
conser
ved
acr
oss
iterations,
and
the
nodes
do
not
con
verge
to
a consensus
;
howe
ver, we
sho
w
that
both
err
ors
can
be
made
as
small
as
desi
red.
Bounds
on
these
quantitie
s involv
e the
spectral
properties
of
the
graph
and
can
be pr
ov ed
by
employing
elementary
techniques
of
LTI
systems
analysis.
I.
INTRODU
CTION
Consider
the following v
ariation
of the a verage
consensus
problem
[1]: each
node
in a graph
knows a number
x
i
(0)
∈
R
, and the goal
is to drive each
node’
s belief
to the initial
average
α
, with
the limitation
that nodes
can communicate
only with
their
neighbours,
and that the channel
is quantized.
At first sight,
this problem
looks
like a false problem,
for
if a node
can send
even only
one bit ov er a channel,
then
it can send
anything
,
by creating
an adequate
coding.
For
example,
if a resolution
of
2
−
8
is needed,
then
one could
consider
8 consecuti
ve bits as a code
word, where
the
i
-th
bit would
represent
the
i
-th bit in the binary
expansion
of
the number
being
transmitted.
With such
coding,
one can
apply
the standard
consensus
algorithms
which
will achie
ve
a precision
of
2
−
8
. If more
precision
is required,
one can use
a 16 bit word, and so on. This
is true,
but the problem
can
be framed
in another
way: given a certain
quantization,
how
precise
can the consensus
be? Previous
work always assumed
that the achie
vable precision
would
have been
in the order
of
the quantization
step;
instead,
we show that consensus
can
be reached
with
a precision
which
is arbitrarily
small,
at the
expense
of slower convergence,
and without
“cheating”
by
changing
the channel
coding.
For example,
it is possible
to
attain
a precision
of
2
−
16
even using
8
bit words.
Also
note
that there
are situations
in which
the channel
carries
only
one bit, and there
is no comple
xity
available
to change
the channel
coding.
Biological
neural
networks
are such
an example.
Neurons
communicate
through
trains
of spikes, which
are a all-or
-none,
partly
probabilistic
phe-
nomenon
[2], [3]; a spike has a self-inhibitory
effect on the
spiking
neuron
and either
a e xcitatory
or inhibitory
effect
The authors
are with
the Control
& Dynamical
Systems
department,
Divi-
sion of Engineering
and Applied
Science,
California
Institute
of Technology
.
Address:
MC 107-81,
1200
E. California
Blvd.,
91125,
Pasadena,
CA.
E-
mail:
{andrea,murray}@cds.caltech.edu
on the other
connected
neurons.
Consider
the cartoonish
representation
of a neural
network in Fig. 1. Assume
some
of the neurons
are sensible
to the same
external
stimulus
(temperature,
light
intensity
, sweetness,
etc.)
and that
we
wish
to obtain
an average
of these
measures,
which
we
think
as real-v
alued
excitation
levels. This
can be cast as an
average
consensus
problem
with
0
−
1
communication
links,
where
{
0
,
1
}
can be mapped
to
{
no spike
,
spike
}
, subject
to
“noisy”
or “probabilistic”
quantization.
More
in general,
we are interested
in the kind
of com-
putation
that can be implemented
by a network of spatially
distrib
uted,
noisy
, slow elements,
with
limited
bandwidth,
such
as neurons.
The evidence
from
biology
suggests
that,
under
these
constraints,
it is possible
to implement
fast,
robust, and adapti
ve control
systems.
Yet we do not have,
in our control-systems
toolbox,
design
methods
that
can
work on this computational
substrate.
In this conte
xt, average
consensus
on a graph
is a good
toy problem
because
it clearly
has the flavor of
“computation”,
and still it can be solved
with
tools
from
linear
system
theory
.
In contrast
with
previous
work (summarized
in the next
section),
we do not consider
the quantization
strate
gy as
part of the design.
Rather
, we take the basic
discrete-time
consensus
algorithm
[1], and we consider
its behavior when
the transmitted
values
are subject
to an arbitrary
, possibly
noisy
, quantization
strate
gy. In this paper
, we consider
any
quantization
strate
gy
ψ
, either
deterministi
c or probabilistic,
with
the condition
that
|
ψ
(
x
)
−
x
|
is bounded.
We show
that the problem
can be solved by adding
a feedback
loop
around
ψ
; this is essentially
an integrator
that compensates
for the error
in time.
When
ψ
is given the interpretation
of
a spiking
function,
the feedback
loop
can be interpreted
as a
self-inhibitory
action.
Using
this method,
the average
of the
nodes
state
is
not
conserv
ed across
iterations,
and the nodes
do
not
converge to a consensus;
however, both
errors
can be
made
as small
as desired,
at the cost of slower convergence.
x
1
(0)
freq
uency
=
α
x
3
(0)
. . .
. . .
. . .
x
2
(0)
x
1
y
i
y
1
x
i
Fig. 1. Cartoonish
representation
of a biological
neural
network. A group
of
neurons
is sensible
to the same
stimulus
(for example,
light);
the activation
value
plays
the same
role as the initial
node
values
x
j
(0)
. The problem
of
averaging
the stimulus
response
can be cast as an average
consensus
problem
with
1-bit
channels
(spike/no
spike). Using
the algorithm
proposed
in this
paper
, the spiking
frequenc
y of the neurons
would
eventually
synchronize
approximately
to a frequenc
y equal
to the average
of the external
stimuli.
2009 American Control Conference
Hyatt Regency Riverfront, St. Louis, MO, USA
June 10-12, 2009
FrA12.5
978-1-4244-4524-0/09/$25.00 ©2009 AACC
4361
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:33 UTC from IEEE Xplore. Restrictions apply.
II . R
EL ATE D WORK
A consensus
algorithm
ov er quantized
channels
is a two-
part strate
gy:
1)
Communication
strategy:
how to decide
the value
y
j
(
k
)
to send
to the neighbors.
2)
Update
strategy:
how to update
one node’
s value
x
i
(
k
)
based
on the
y
j
(
k
)
received from
its neighbors.
We will be consistent
through
the paper
to use the index
j
to
refer
to the communication
strate
gy, and the index
i
to refer
to the update
strate
gy.
Many works
dealt
with
reaching
a quantized
consensus,
in
the sense
that
x
j
(
k
)
∈
Z
, and in the limit
the states
differ at
most
by 1; for the analysis
of this problem
see [4], [5] and
references
therein.
In [6], [7], [8],
[9] the authors
consider
the problem
of
reaching
a consensus
in
R
using
quantized
channels.
They
propose
the following
communication
strate
gy:
y
j
(
k
) =
q
(
x
j
(
k
))
where
q
(
x
)
rounds
x
to the nearest
integer, and the following
is the update
strate
gy:
x
i
(
k
+ 1) =
x
i
(
k
)
−
y
i
(
k
) +
X
j
P
i,j
y
j
(
k
)
where
P
is any doubly
stochastic
matrix
with
positi
ve diag-
onal
and with
the corresponding
graph
strongly
connected.
This
algorithm
is such
that:
•
The average
of the states
is conserv
ed.
•
The
nodes
converge to different
values,
in general
not in
Z
.
•
The disagreement
is in the order
of the discretization
step.
In [10]
the authors
propose
a “probabilistic
quantization”
scheme.
The
probabilistic
quantization
q
p
(
x
)
of
x
is a
random
variable
with
the distrib
ution:
q
p
(
x
) =
(
⌈
x
⌉
with
probability
x
−⌊
x
⌋
⌊
x
⌋
otherwise
(1)
They consider
the following
communication
strate
gy:
y
j
(
k
) =
q
p
(
x
j
(
k
))
with
the following
updating
strate
gy:
x
i
(
k
+ 1) =
X
j
P
i,j
y
j
(
k
)
with
P
doubly
stochastic.
This
algorithm
is such
that:
•
The average
is not conserv
ed.
•
Nodes
converge to a consensus
τ
∈
Z
.
•
The expected
value
of
τ
is
α
.
III . P
ROPOSED STRATE GY
As for the updating
strate
gy, we use the same
update
rule
discussed
as the base
case
in the tutorial
paper
[1], with
the difference
is that
we use
y
j
(
k
)
, the quantized
value
transmitted
by node
j
, instead
of using
the real state
x
j
(
k
)
.
x
i
(
k
+ 1) =
x
i
(
k
) +
η
∆
X
j
a
ij
(
y
j
(
k
)
−
x
i
(
k
))
(2)
Here
a
ij
is an element
of the adjacenc
y matrix
and
∆
is
the maximum
degree
of the graph.
The parameter
η
∈
(0
,
1)
influences
the convergence
speed
(and,
as we will see, the
precision
of the consensus).
The communication
strate
gy relies
on the definition
of an
auxiliary
state
variable
c
j
(
k
)
∈
R
, for which
initially
c
j
(0) =
0
, and a certain
function
ψ
:
R
→
Z
, or random
variable,
such
that
|
ψ
(
y
)
−
y
|≤
β
(3)
for some
β >
0
.
Our proposed
communication
strate
gy is:
(
y
j
(
k
)
=
ψ
(
x
j
(
k
)
−
c
j
(
k
))
c
j
(
k
+ 1) =
c
j
(
k
) + (
y
j
(
k
)
−
x
j
(
k
))
(4)
Note
that the auxiliary
variable
c
j
(
k
)
integrates
the error
in approximating
x
j
with
y
j
. This
error
is then used
as a
negative feedback
for
ψ
. If
ψ
is interpreted
as a spiking
TABLE
I
S
UMM ARY O F CON SIDERED MET HOD
S
Method
Communication
strate
gy
Update
strate
gy
Drift
Disagreement
No quantization
y
(
k
) =
x
(
k
)
x
(
k
+ 1) =
x
(
k
) + (
P
−
I
)
y
(
k
)
d
(
k
) = 0
φ
(
k
)
→
0
Carli
et al.
y
(
k
) =
q
(
x
(
k
))
x
(
k
+ 1) =
x
(
k
) + (
P
−
I
)
y
(
k
)
d
(
k
) = 0
φ
(
k
)
→
c >
0
Aysal
et al.
y
(
k
) =
q
p
(
x
(
k
))
x
(
k
+ 1) =
P
y
(
k
)
d
(
k
)
6
= 0
φ
(
k
)
→
0
Proposed
strate
gy
y
(
k
) =
ψ
(
x
(
k
)
−
c
(
k
))
c
(
k
+ 1) =
c
(
k
) + (
y
(
k
)
−
x
(
k
))
for any
ψ
such
that
|
ψ
(
z
)
−
z
|
≤
β
x
(
k
+1) = (
I
−
η
∆
D
)
x
(
k
)+
η
∆
A
y
(
k
)
for any
η
∈
(0
,
1)
d
(
k
)
≤
ηβ
φ
(
k
)
≤
c
ηβ
λ
n
{
L
}
λ
2
{
L
}
4362
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:33 UTC from IEEE Xplore. Restrictions apply.
function,
the feedback
inhibits
the next spike, similarly
to the
effect of the inhibitory
post-synaptic
potential
in the neuron.
Examples
of allowed
ψ
include:
•
Rounding
function
s: Define
the function
q
:
R
→
Z
such
that
q
(
x
)
is the integer closest
to
x
. Then
one can
choose
ψ
(
x
) =
q
(
x
)
,
β
= 0
.
5
•
Ceiling/floor
functions
:
ψ
(
x
) =
⌈
x
⌉
,
β
= 1
ψ
(
x
) =
⌊
x
⌋
,
β
= 1
•
Threshold-and-fir
e:
Fire
to the next integer if
x
−⌊
x
⌋
is ov er a threshold
t
∈
(0
,
1)
.
ψ
(
x
) =
(
⌈
x
⌉
if
x
−⌊
x
⌋
> t
⌊
x
⌋
otherwise
,
β
= max
{
t,
1
−
t
}
(5)
•
Random
rounding:
Choose
randomly
between
the previ-
ous and the next integer, according
to a fixed probability
p
∈
(0
,
1)
.
ψ
(
x
) =
(
⌈
x
⌉
with
probability
p
⌊
x
⌋
otherwise
,
β
= 1
•
Probabilistic
quantization
: Use the probabilistic
quan-
tization
defined
as in (1):
ψ
(
x
) =
(
⌈
x
⌉
with
probability
x
−⌊
x
⌋
⌊
x
⌋
otherwise
,
β
= 1
In the case
without
quantization
(
y
j
(
k
) =
x
j
(
k
)
), it is
possible
to obtain,
with
very mild
assumptions,
two nice
properties
of the update
strate
gy (2): the mean
is conserv
ed
across
iterations,
and the disagr
eement
tends
to zero.
This
is
not true in our case:
the mean
is not
conserv
ed, and the states
do not
converge to a consensus.
However, we can provide
bounds
that depend
linearly
on the parameter
η
in (2) and
therefore
can be made
as small
as desired,
and, in particular
,
much
smaller
than
the quantization.
To measure
the performance
of the algorithm,
we define
two error
measures.
The first is the drift
from
the mean:
d
(
k
)
,
1
n
X
i
x
i
(
k
)
−
α
The other
is the disagreement
among
the nodes:
X
i,j
a
ij
(
x
i
(
k
)
−
x
j
(
k
))
2
=
x
(
k
)
T
L
x
(
k
)
In this expression
L
is the Laplacian
of the graph
(
L
=
D
−
A
, where
D
is the degree matrix
and
A
is the adjacenc
y
matrix).
Because
we are interest
ed in the performance
as the
number
of nodes
grows, we look
at the average
disagree-
ment
φ
(
k
)
, which
we define
as
φ
(
k
)
,
1
n
∆
X
i,j
a
ij
(
x
i
(
k
)
−
x
j
(
k
))
2
1
/
2
TABLE
II
S
YMBOLS USED IN THIS P APER
n
number
of nodes
A
adjacenc
y matrix
D
degree
matrix
d
j
degree
of node
j
∆
graph
degree
L
Laplacian
matrix;
L
=
D
−
A
P
Perron
matrix;
P
=
I
−
ǫ
L
with
ǫ <
1
/
∆
x
j
(
k
)
node
state
α
target value:
α
=
P
i
x
i
(0)
/n
y
j
(
k
)
value
transmitted
by node
j
to neighbors
at time
k
ψ
generic
(noisy)
quantization
function
d
(
k
)
drift
φ
(
k
)
average
disagreement
q
(
x
)
nearest
integer to
x
q
p
(
x
)
probabilistic
quantization
for
x
r
(
x
)
,
q
(
x
)
−
x
c
j
(
k
)
auxiliary
state
variable
1
n
×
1
vector
of 1s
Note
that we use
n
∆
as an approximation
to the number
of edges;
the square
root
is to obtain
a linear
measure
comparable
with
d
(
k
)
.
In the next section
we prove the following
bounds:
d
(
k
)
≤
ηβ
lim
k
→∞
φ
(
k
)
≤
√
6
ηβ
λ
n
{
L
}
λ
2
{
L
}
(6)
In this
paper
, with
abuse
of notation,
we
write
lim
k
→∞
φ
(
k
)
≤
c
in the sense
that
φ
(
k
)
≤
c
+
f
(
k
)
with
lim
k
→∞
f
(
k
) = 0
; in general,
φ
(
k
)
does
not have a
limit
because
it settles
on an oscillatory
behavior.
Note
in (6) the three
factors
that impact
the accurac
y of
the consensus:
η
∈
(0
,
1)
appears
in the update
strate
gy,
β
depends
on the quantization
strate
gy, and
λ
n
{
L
}
/λ
2
{
L
}
depends
on the topology
of the graph.
The bound
on the drift
depends
only
on
β
and
η
and is independent
of the topology
.
By choosing
a smaller
η
, we can make these
two errors
as
small
as desired;
the trade-of
f is that a smaller
η
produces
slower convergence.
IV. M
AIN RESULT S
We briefly
recalls
the main
spectral
properties
of graphs
that we use in the following;
for the proofs,
see [1] and
references
therein.
See also Table
III for a summary
of the
symbols.
We assume
that the graph
is undirected
and connected.
Let
D
be the degree matrix
and
A
the adjacenc
y matrix.
Then
the
Laplacian
matrix
L
=
D
−
A
is symmetric
positi
ve semidefi-
nite.
The smallest
eigen
value
λ
1
{
L
}
is 0, with
eigen
vector
1
:
1
T
L
=
0
. The second
smallest
eigen
value
λ
2
{
L
}
is different
than
zero.
The largest eigen
value
λ
n
{
L
}
is at least
∆
and at
most
2∆
.
If
ǫ
=
η/
∆
, with
η
∈
(0
,
1)
then
P
=
I
−
ǫ
L
is a doubly
stochastic
matrix.
P
and
L
have the same
eigen
vectors.
If
λ
j
is the
j
-th eigen
value
of
L
, then
the
j
-th eigen
value
for
P
is
j
= 1
−
ǫλ
j
.
1
is an eigen
vector
for the simple
4363
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:33 UTC from IEEE Xplore. Restrictions apply.
eigen
value
1
of
P
:
1
T
P
=
1
. Because
the other
eigen
values
of
P
are strictly
less than
1, and
1
T
L
=
0
, this implies
that
lim
k
→∞
P
k
L
=
0
.
Before
stating
the main
results,
we begin with two lemmas.
The first describes
an invariant
quantity
of the system.
Lemma
1:
Let
d
j
be the degree
of node
j
and
ǫ
=
η/
∆
.
Then
the following
quantity
V
(
k
)
is invariant:
V
(
k
) =
X
i
(
x
i
(
k
)
−
ǫd
j
c
j
(
k
)) =
1
T
(
x
(
k
)
−
ǫ
D
c
(
k
))
Proof:
Notice
that
y
(
k
)
can be written
as:
y
(
k
) =
x
(
k
) + [
c
(
k
+ 1)
−
c
(
k
)]
Hence
the dynamics
can be rewritten
as:
x
(
k
+ 1) =
P
x
(
k
) +
ǫ
A
(
c
(
k
+ 1)
−
c
(
k
))
Now a straight
computation
gives:
V
(
k
+ 1) =
1
T
(
x
(
k
+ 1)
−
ǫ
D
c
(
k
+ 1))
=
1
T
(
P
x
(
k
) +
ǫ
A
(
c
(
k
+ 1)
−
c
(
k
))
−
ǫ
D
c
(
k
+ 1))
=
1
T
(
P
x
(
k
)
−
ǫ
D
c
(
k
) +
ǫ
L
(
c
(
k
+ 1)))
=
1
T
(
x
(
k
)
−
ǫ
D
c
(
k
)) =
V
(
k
)
Lemma
2:
The auxiliary
variable
c
j
(
k
)
used
in the feed-
back
loop
is bounded:
|
c
j
(
k
)
|≤
β
Proof:
|
c
j
(
k
+ 1)
|
=
|
c
j
(
k
) + (
y
j
(
k
)
−
x
j
(
k
))
|
=
|
ψ
(
x
j
(
k
)
−
c
j
(
k
))
−
(
x
j
(
k
)
−
c
j
(
k
))
|
=
|
ψ
(
z
)
−
z
|≤
β
Giv en the previous
lemma,
the bound
on the drift
is an easy
consequence.
Proposition
1:
The drift
is bounded:
d
(
k
)
≤
ηβ
(7)
Proof:
Notice
that
α
=
1
n
V
(0) =
1
n
V
(
k
) =
1
n
1
T
(
x
(
k
)
−
ǫ
D
c
(
k
))
,
and thus
1
n
1
T
x
(
k
)
−
α
=
ǫ
1
n
1
T
D
c
(
k
)
≤
ǫ
1
n
Tr
(
D
)
β
≤
ǫ
1
n
(
n
∆)
β
=
ǫ
∆
β
=
ηβ
Proposition
2:
Eventually
, the disagreement
is bounded
by
ǫ
:
lim
k
→∞
φ
(
k
)
≤
√
6
ηβ
λ
n
{
L
}
λ
2
{
L
}
(8)
Proof:
The dynamics
of the system
can be written
as
x
(
k
+ 1) =
P
x
(
k
) +
ǫ
A
c
(
k
+ 1)
−
ǫ
A
c
(
k
)
,
where
ǫ
=
η/
∆
. In this proof,
we consider
A
c
(
k
)
as a
disturbance
input
to the system
x
(
k
+ 1) =
P
x
(
k
)
. Becaus
e
c
(
k
)
is bounded
(Lemma
2) and
P
, being
doubly
stochas
tic,
has a “mixing”
effect,
the disturbance
is filtered
by the
dynamics,
and
the final
effect
on the consensus
can be
bounded.
Note
that
ǫ
A
c
(
k
)
is added
to the state at
time
x
(
k
)
(with
a plus
sign)
and to
x
(
k
+ 1)
(with
a minus
sign).
The
contrib
ution
to
x
(
k
+1)
is globally
+
P
ǫ
A
x
(
k
)
−
ǫ
A
c
(
k
) =
ǫ
(
P
−
I
)
A
c
(
k
) =
−
ǫ
2
LA
c
(
k
)
. Consequently
, the state
admits
the following
closed
form
expression:
x
(
k
) =
P
k
x
(0)+
ǫ
A
c
(
k
)
−
ǫ
2
k
−
1
X
τ
=1
P
k
−
τ
LA
c
(
τ
)
−
ǫ
P
k
A
c
(0)
We want to compute
the limit
of the disagreement
function
x
(
k
)
T
L
x
(
k
)
as
k
→ ∞
. Note
that it is composed
by 6
terms:
x
(
k
)
T
L
x
(
k
) =
(9)
x
(0)
T
P
k
LP
k
x
(0) +
(10)
ǫ
2
c
(
k
)
T
ALA
c
(
k
) +
(11)
ǫ
4
k
−
1
X
m
=1
k
−
1
X
τ
=1
c
(
τ
)
T
ALP
k
−
m
LP
k
−
τ
LA
c
(
τ
) +
(12)
ǫ
x
(0)
T
P
k
LA
c
(
k
) +
(13)
−
ǫ
2
x
(0)
T
P
k
L
k
−
1
X
τ
=1
P
k
−
τ
LA
c
(
τ
) +
(14)
−
ǫ
3
c
(
k
)
T
A
k
−
1
X
τ
=1
LP
k
−
τ
LA
c
(
τ
)
(15)
Because
P
k
L
→
0
, the terms
(10), (13),
(14) disappear
. The
term
(11)
can be bounded
as follows:
|
ǫ
2
c
(
k
)
T
ALA
c
(
k
)
| ≤
β
2
ǫ
2
max
||
u
||
∞
≤
1
|
u
T
ALA
u
|
≤
β
2
ǫ
2
∆
2
max
||
u
||
∞
≤
1
|
u
T
L
u
|
≤
β
2
ǫ
2
∆
2
nλ
n
{
L
}
The term
(15)
can be bounded
as
|
ǫ
3
c
(
k
)
T
A
k
−
1
X
τ
=1
LP
k
−
τ
LA
c
(
τ
)
| ≤
ǫ
3
k
−
1
X
τ
=1
|
c
(
k
)
T
ALP
k
−
τ
LA
c
(
τ
)
| ≤
β
2
ǫ
2
∆
2
n
k
−
1
X
τ
=1
λ
max
n
LP
k
−
τ
L
o
Recall
that
P
and
L
have the same
eigen
vectors;
hence
the
typical
eigen
value
for the matrix
LP
k
−
τ
L
has the value
λ
i
n
LP
k
−
τ
L
o
=
λ
i
{
L
}
2
(1
−
ǫλ
i
{
L
}
)
k
−
τ
This
expression
can be bounded
by choosing
the largest
eigen
value
λ
n
for the first factor, and the small
est non-zero
eigen
value
λ
2
for the second
factor.
λ
max
n
LP
k
−
τ
L
o
≤
λ
n
{
L
}
2
(1
−
ǫλ
2
{
L
}
)
k
−
τ
4364
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:33 UTC from IEEE Xplore. Restrictions apply.
The sum
of the series
can be computed
as:
k
−
1
X
τ
=1
(1
−
r
)
k
−
τ
=
(1
−
r
)
r
h
1
−
(1
−
r
)
k
−
1
i
Hence
for the sixth
term:
ǫ
3
c
(
k
)
T
A
k
−
1
X
τ
=1
LP
k
−
τ
LA
c
(
τ
)
≤
β
2
ǫ
2
∆
2
n
λ
2
n
{
L
}
λ
2
{
L
}
(1
−
ǫλ
2
{
L
}
)
h
1
−
(1
−
ǫλ
2
{
L
}
)
k
−
1
i
For the same
reasons,
but with
longer
computations,
the
remaining
term
can be bounded
as follows:
ǫ
4
k
−
1
X
m
=1
k
−
1
X
τ
=1
c
(
τ
)
T
ALP
k
−
m
LP
k
−
τ
LA
c
(
τ
)
≤
β
2
ǫ
4
n
∆
2
k
−
1
X
m
=1
k
−
1
X
τ
=1
λ
max
n
LP
k
−
m
LP
k
−
τ
L
o
We find again that
λ
max
n
LP
k
−
m
LP
k
−
τ
L
o
≤
λ
3
n
{
L
}
(1
−
ǫλ
2
{
L
}
)
(
k
−
m
)+(
k
−
τ
)
and for the series:
k
−
1
X
m
=1
k
−
1
X
τ
=1
(1
−
ǫλ
2
{
L
}
)
(
k
−
m
)+(
k
−
τ
)
=
(1
−
ǫλ
2
{
L
}
)
2
ǫ
2
λ
2
{
L
}
2
h
1
−
(1
−
ǫλ
2
{
L
}
)
k
−
1
i
2
And
hence
the bound
for the sixth
term
is
ǫ
4
k
−
1
X
m
=1
k
−
1
X
τ
=1
c
(
τ
)
T
ALP
k
−
m
LP
k
−
τ
LA
c
(
τ
)
≤
β
2
ǫ
2
n
∆
2
λ
3
n
{
L
}
λ
2
2
{
L
}
(1
−
ǫλ
2
{
L
}
)
2
h
1
−
(1
−
ǫλ
2
{
L
}
)
k
−
1
i
2
Finally
, the limit
for the disagreement
function
is
lim
k
→∞
x
(
k
)
T
L
x
(
k
)
≤
β
2
ǫ
2
n
∆
2
λ
n
{
L
}
1 +
λ
n
{
L
}
λ
2
{
L
}
+
λ
2
n
{
L
}
λ
2
2
{
L
}
Note
that
λ
n
/λ
2
≥
1
; a good
approximation
is
1 +
λ
n
{
L
}
λ
2
{
L
}
+
λ
2
n
{
L
}
λ
2
2
{
L
}
≤
3
λ
2
n
{
L
}
λ
2
2
{
L
}
At this point,
use the fact that
λ
n
{
L
}≤
2∆
:
lim
k
→∞
x
(
k
)
T
L
x
(
k
)
≤
6
β
2
ǫ
2
n
∆
3
λ
2
n
{
L
}
λ
2
2
{
L
}
Hence
for the average
disagreement:
lim
k
→∞
φ
(
k
)
≤
√
6
ηβ
λ
n
{
L
}
λ
2
{
L
}
V. S
IMULATION S
Fig. 2 shows an example
run of our algorithm,
with
ψ
=
q
,
on a circular
graph
composed
of
n
= 10
nodes,
for
η
= 0
.
01
and
η
= 0
.
05
. The states
eventually
seem
to converge to a
periodic
function
(but note that we did not
prove such
result).
These
results
are quantitati
vely similar
for other
choices
of
deterministic
ψ
; while,
of course,
probabilistic
quantizations
do not settle
on a periodic
behavior.
Table
VI shows the result
of comparing
our algorithm
to the one proposed
by Carli
et al.
on a set of canonical
graphs
(star-shaped,
ring,
path,
complete),
for two sizes
of
the graphs
(
n
= 10
,
30
). We set the initial
value
of node
i
to be
x
i
(0) =
πi
; the asymptotic
results
are qualitati
vely un-
changed
if one chooses
random
initial
values.
The simulation
is run for 10,000
time
steps,
which
is enough
for the methods
to reach
the stationary
behavior. Because
an equilibrium
is
not reached,
we report
in the table
the worst values
of the
drift
and the disagreement
as recorded
in the last 100 steps.
The results
of our algori
thm appear
substantially
better
than
the algorithm
of Carli
et al.
However, we observ
e that the
bounds
we found
are very loose,
especially
the bound
on the
disagreement
given by Proposition
2.
VI. C
ON CLUSION S AND
FUTURE WORK
This
paper
showed
how real-v
alued
consensus
can be
reached
(up to an arbitrary
accurac
y) even in the case
that
the channels
are quantized,
and the quantization
function
is
noisy
. The method
consists
in wrapping
a negative feedback
loop
around
the quantization
function;
this
has a loose
similarity
to the self-inhibitory
action
of spiking
neurons.
The algorithm
presented
in this paper
seems
to be effec-
tive, but the bounds
derived, while
they show qualitati
vely
that the errors
can be made
as small
as desired
by v arying
the parameter
η
, are not quantitati
vely satisf
actory
, because
they greatly
ov erestimate
the errors.
The
reason
is that in
the derivation
of Proposition
2 we treated
the quantization
function
essentially
as an arbitrary
bounded
disturbance.
The
analysis
is particularly
pessimisti
c for the ring
and
path
graphs,
because
λ
n
/λ
2
∼
n
2
, while,
in practice,
we ob-
served that the asymptotic
disagreement
seems
to be largely
independent
of the number
of nodes.
These
results
can be
impro
ved by either
focusing
on one particular
quantization
function
instead
of the broad
class
we considered,
or on one
particular
class
of graphs.
The speed
of convergence
must
be investigated
further
. Far from
convergence,
before
the
quantization
error
becomes
relevant, the convergence
appears
to be exponential,
and this should
be easily
proved. When
the quantization
error
is dominant,
the analysis
complicates
because
of the nonlinearity
and stochasticity
of
ψ
; in the case
of deterministic
quantizations,
the system
seems
to tend
to a
periodic
orbit,
but we do not have a proof
of this yet.
Ackno
wledgements.
Thanks
to Li Na (
*+
,-
) for dispro
v-
ing a conjecture
of ours,
and to the anonymous
reviewers
for
the thorough
remarks.
4365
Authorized licensed use limited to: CALIFORNIA INSTITUTE OF TECHNOLOGY. Downloaded on April 12,2010 at 17:59:33 UTC from IEEE Xplore. Restrictions apply.