The network setting
Consider a consensus algorithm over a network in which links randomly fail at each round.
These link failures can represent either communication failures between nodes and/or packet
losses. We thus have a consensus algorithm over a type of random network. This
setting is caricatured in the sequence of diagrams on the right (red color depicts failing
links).
We are interested in not just whether consensus is asymptotically achieved or not, but
rather more detailed statements about the rate of convergence as a function
of probability of failure and network topology parameters. In our stochastic
setting, this is quantified by the variance of deviation from average.
The system theory reformulation
A nice feature of this problem is that the dynamics of the
standard average consensus algorithm over
a network with link failures can be recast as a linear system with multiplicative
noise. The dynamics look like this
where the deltas are iid bernouli random variables representing the failures of each
of the n links. The B matrices represent the effect of each link's disconnection on
the algorithm's dynamics.
This is now a stochastic system, but a recursion equation for the covariance of the state
can be derived to be
where the sigmas are the variances of each of the deltas. The actual recursion we use
is a little different since one needs to keep track of the covariances of the deviation
from average state, rather than the actual state, but the basic idea is similar. All
second order convergence properties
of the stochastic system (such as rates of convergece of variances) can be deduced from
studying this matrix recursion equation.
The mathematical tools used
Convergence properties of the covariance recursion are determined by the Lyapunov-like
matrix-valued operator
For example, the eigenvalues of this operator determine the convergence rate of variances.
In general, there is no simple relationship between the eigenvalues of this operator
and the spectral properties of the original A and B matrices (e.g. one cannot easily
relate the second smallest graph Laplacian eigenvalue, or the Fiedler vector, to the
eigenvalues of this operator).
Our approach is to use spectral perturbation theory and derive the convergence rates
up to first order in the probability of failure. For certain regular graph structures,
we can obtain explicit expressions for these rates.
Reformulation as a stochastic structured uncertainty problem
Problems with multiplicative uncertainty can be viewed in a unified manner as
structured uncertainty problems as shown here
This is the point of view that originated in the robust control literature in the early
80s. The case of stochastic deltas is a little more recent in the work of Lu & Skelton
and Elia. The necessary and sufficient condition is a bound on the
spectral radius of the matrix of subsystems' H2 norms.
We can recast the link failure problem in this setting. A particularly nice feature is
that the network's structure and topology translates to a special structure in the
nominal system M. Thus, more refined statements about the spectral radius of the matrix
of norms can be made. See the papers below for the details.
Related Publications
-
Stacy Patterson,
Bassam Bamieh,
and Amr El Abbadi.
Convergence Rates of Distributed Average Consensus with Stochastic Link Failures.
Submitted to IEEE Trans. Aut. Cont.,
2009.
-
Stacy Patterson and Bassam Bamieh.
Distributed Consensus with Link Failures as a Structured Stochastic Uncertainty Problem.
In Proc. 46th Allerton Conference,
2008.
|