University of Illinois Urbana-Champaign

Distributed Algorithms for Consensus and Coordination in the Presence of Packet-Dropping Communication Links: Part I: Statistical Moments Analysis Approach

Domínguez-García, Alejandro D.; Hadjicostis, Christoforos N.; Vaidya, Nitin H.

Content Files
UILU-ENG-11-2207.pdf

Permalink

https://hdl.handle.net/2142/90430

Description

Title
Distributed Algorithms for Consensus and Coordination in the Presence of Packet-Dropping Communication Links: Part I: Statistical Moments Analysis Approach
Author(s)
  • Domínguez-García, Alejandro D.
  • Hadjicostis, Christoforos N.
  • Vaidya, Nitin H.
Issue Date
2011-09
Keyword(s)
  • Distributed algorithms
  • Average consensus
  • Markov chains
  • Coefficients of ergodicity
Date of Ingest
  • 2016-07-06T21:03:23Z
  • 2017-07-14T23:15:17Z
Abstract
This two-part paper discusses robustification methodologies for linear-iterative distributed algorithms for consensus and coordination problems in multicomponent systems, in which unreliable communication links may drop packets. We consider a setup where communication links between components can be asymmetric (i.e., component j might be able to send information to component i, but not necessarily vice-versa), so that the information exchange between components in the system is in general described by a directed graph that is assumed to be strongly connected. In the absence of communication link failures, each component i maintains two auxiliary variables and updates each of their values to be a linear combination of their corresponding previous values and the corresponding previous values of neighboring components (i.e., components that send information to node i). By appropriately initializing these two (decoupled) iterations, the system components can asymptotically calculate variables of interest in a distributed fashion; in particular, the average of the initial conditions can be calculated as a function that involves the ratio of these two auxiliary variables. The focus of this paper to robustify this double-iteration algorithm against communication link failures. We achieve this by modifying the double-iteration algorithm (by introducing some additional auxiliary variables) and prove that the modified double-iteration converges almost surely to average consensus. In the first part of the paper, we study the first and second moments of the two iterations, and use them to establish convergence, and illustrate the performance of the algorithm with several numerical examples. In the second part, in order to establish the convergence of the algorithm, we use coefficients of ergodicity commonly used in analyzing inhomogeneous Markov chains.
Publisher
Coordinated Science Laboratory, University of Illinois at Urbana-Champaign
Series/Report Name or Number
Coordinated Science Laboratory Report no. UILU-ENG-11-2207, CRHC-11-05
Type of Resource
text
Genre of Resource
Technical Report
Language
en
Permalink
http://hdl.handle.net/2142/90430
Sponsor(s)/Grant Number(s)
  • 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

Owning Collections

Report - Coordinated Science Laboratory PRIMARY