Convergence Rates of Distributed Average Consensus with Stochastic Link Failures

TitleConvergence Rates of Distributed Average Consensus with Stochastic Link Failures
Publication TypeJournal Article
Year of Publication2010
AuthorsPatterson, S, Bamieh B, El Abbadi A
JournalIEEE Transactions on Automatic Control
Volume55
Number4
Pagination880-892
Date Published04/2010
Abstract

We consider a distributed average consensus algorithm over a network in which communication links fail with independent probability. In such stochastic networks, convergence is defined in terms of the variance of deviation from average. We first show how the problem can be recast as a linear system with multiplicative random inputs which model link failures. We then use our formulation to derive recursion equations for the second order statistics of the deviation from average in networks with and without additive noise. We give expressions for the convergence behavior in the asymptotic limits of small failure probability and large networks. We also present simulation-free methods for computing the second order statistics in each network model and use these methods to study the behavior of various network examples as a function of link failure probability.