Stochastic multiscale approaches to consensus problems

Jong Han Kim, Matthew West, Sanjay Lall, Eelco Scholte, Andrzej Banaszuk

Research output: Chapter in Book/Report/Conference proceedingConference contribution


While peer-to-peer consensus algorithms have enviable robustness and locality for distributed estimation and computation problems, they have poor scaling behavior with network diameter. We show how deterministic multi-scale consensus algorithms overcome this limitation and provide optimal scaling with network size, but at the cost of requiring global knowledge of network topology. To obtain the benefits of both single-and multi-scale consensus methods we introduce a class of stochastic message-passing schemes that require no topology information and yet transmit information on several scales, achieving scalability. The algorithm is described by a sequence of random Markov chains, allowing us to prove convergence for general topologies.

Original languageEnglish (US)
Title of host publicationProceedings of the 47th IEEE Conference on Decision and Control, CDC 2008
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages7
ISBN (Print)9781424431243
StatePublished - 2008
Event47th IEEE Conference on Decision and Control, CDC 2008 - Cancun, Mexico
Duration: Dec 9 2008Dec 11 2008

Publication series

NameProceedings of the IEEE Conference on Decision and Control
ISSN (Print)0743-1546
ISSN (Electronic)2576-2370


Other47th IEEE Conference on Decision and Control, CDC 2008

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Modeling and Simulation
  • Control and Optimization


Dive into the research topics of 'Stochastic multiscale approaches to consensus problems'. Together they form a unique fingerprint.

Cite this