Robust Distributed Average Consensus via Exchange of Running Sums

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

Research output: Contribution to journalArticlepeer-review

Abstract

We consider a multi-component system in which each component (node) can send/receive information to/from sets of neighboring nodes via communication links (edges) that form a fixed strongly connected, possibly directed, communication topology (digraph). We analyze a class of distributed iterative algorithms that allow the nodes to asymptotically compute the exact average of their initial values, despite a variety of challenging scenarios, including possible packet drops in the communication links, and imprecise knowledge of the network. The algorithms in this class run the two linear iterations of the so-called ratio-consensus algorithm, modified so that messages sent by one node to another are encoded as running sums. This 'convolutional' encoding allows the receiving node l to infer information about past messages that node j meant to send to node l but may have been lost due to packet drops. Imprecise knowledge of the network (unknown out-neighborhoods) can be handled, at the cost of memory and communication overhead, by also having each node track the progress of running sums of other nodes, and forward to its out-neighboring nodes the updated value of one such running sum that it randomly selects. Our analysis relies on augmenting the digraph that describes the communication topology by introducing additional (virtual) nodes, and showing that the dynamics of each of the two iterations in the augmented digraph is mathematically equivalent to a finite inhomogeneous Markov chain. Almost sure convergence to exact average consensus is then established via weak ergodicity analysis of the resulting inhomogeneous Markov chain.

Original languageEnglish (US)
Article number7219386
Pages (from-to)1492-1507
Number of pages16
JournalIEEE Transactions on Automatic Control
Volume61
Issue number6
DOIs
StatePublished - Jun 2016

Keywords

  • Average consensus
  • coefficients of ergodicity
  • digraphs
  • imprecise network knowledge
  • inhomogeneous Markov chains
  • packet drops
  • weak ergodicity

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Robust Distributed Average Consensus via Exchange of Running Sums'. Together they form a unique fingerprint.

Cite this