Files in this item



application/pdfB59-CRHC_11_06.pdf (14MB)
(no description provided)PDF


Title:Distributed Algorithms for Consensus and Coordination in the Presence of Packet-Dropping Communication Links: Part II: Coefficients of Ergodicity Analysis Approach
Author(s):Vaidya, Nitin H.; Hadjicostis, Christoforos N.; Domínguez-García, Alejandro D.
Subject(s):Distributed algorithms
Average consensus
Markov chains
Coefficients of ergodicity
Abstract:In this two-part paper, we consider multicomponent systems in which each component can iteratively exchange information with other components in its neighborhood in order to compute, in a distributed fashion, the average of the components’ initial values or some other quantity of interest (i.e., some function of these initial values). In particular, we study an iterative algorithm for computing the average of the initial values of the nodes. In this algorithm, each component maintains two sets of variables that are updated via two identical linear iterations. The average of the initial values of the nodes can be asymptotically computed by each node as the ratio of two of the variables it maintains. In the first part of this paper, we show how the update rules for the two sets of variables can be enhanced so that the algorithm becomes tolerant to communication links that may drop packets, independently among them and independently between different transmission times. In this second part, by rewriting the collective dynamics of both iterations, we show that the resulting system is mathematically equivalent to a finite inhomogenous Markov chain whose transition matrix takes one of finitely many values at each step. Then, by using e a coefficients of ergodicity approach, a method commonly used for convergence analysis of Markov chains, we prove convergence of the robustified consensus scheme. The analysis suggests that similar convergence should hold under more general conditions as well.
Issue Date:2011-09
Publisher:Coordinated Science Laboratory, University of Illinois at Urbana-Champaign
Series/Report:Coordinated Science Laboratory Report no. UILU-ENG-11-2208, CRHC-11-06
Description:Coordinated Science Laboratory was formerly known as Control Systems Laboratory
Sponsor:National Science Foundation / ECCS-CAR-0954420 and 1059540
European Commission Seventh Framework Programme / INFSO-ICT-223844 and PIRG02-GA-2007-224877
Army Research Office / W-911-NF-0710287
Date Available in IDEALS:2015-04-06

This item appears in the following Collection(s)

Item Statistics