Distributed Average Consensus with Stochastic Communication Failures

TitleDistributed Average Consensus with Stochastic Communication Failures
Publication TypeConference Paper
Year of Publication2007
AuthorsPatterson, S, Bamieh B, El Abbadi A
Conference NameProceedings of the 46th IEEE Conference on Decision and Control
Date PublishedDecember

We consider a distributed average consensus algorithm over a network in which communication links fail with independent probability. Convergence in such stochastic networks is defined in terms of the variance of deviation from average. We characterize the decay factor of the variance in terms of the eigenvalues of a Lyapunov-like matrix recursion. We give expressions for the decay factors in the asymptotic limits of small failure probability and large networks. We also present a simulation-free method for computing the decay factor for any particular graph instance and use this method to study the behavior of various network examples as a function of link failure probability.