Consensus Propagation

We propose consensus propagation, an asynchronous distributed protocol for averaging numbers across a network. We establish convergence, characterize the convergence rate for regular graphs, and demonstrate that the protocol exhibits better scaling properties than pairwise averaging, an alternative that has received much recent attention. Consensus propagation can be viewed as a special case of belief propagation, and our results contribute to the belief propagation literature. In particular, beyond singly-connected graphs, there are very few classes of relevant problems for which belief propagation is known to converge

• Publication year

  2005

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2005-12-05

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2006.883539arXiv cs/0603078
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Distributed average consensus with least-mean-square deviation

  2007cited by this paper
• Fastest Mixing Markov Chain on a Path

  2006cited by this paper
• Convergence of the Min-Sum Message Passing Algorithm for Quadratic Optimization

  2006cited by this paper
• Distributed Detection in Sensor Networks With Packet Losses and Finite Capacity Links

  2006cited by this paper
• Sufficient Conditions for Convergence of Loopy Belief Propagation

  2005cited by this paper
• A scheme for robust distributed sensor fusion based on average consensus

  2005influential reference
• Convergence in Multiagent Coordination, Consensus, and Flocking

  2005cited by this paper
• Symmetry Analysis of Reversible Markov Chains

  2005cited by this paper
• Gossip algorithms: design, analysis and applications

  2005cited by this paper
• Walk-Sum Interpretation and Analysis of Gaussian Belief Propagation

  2005cited by this paper
• Information Dissemination via Gossip: Applications to Averaging and Coding

  2005cited by this paper
• Asynchronous Distributed Detection in Sensor Networks ∗

  2005cited by this paper
• Mixing Times for Random Walks on Geometric Random Graphs

  2005cited by this paper
• Approximate aggregation techniques for sensor databases

  2004cited by this paper
• Bounding Fastest Mixing

  2004cited by this paper
• Epidemic-style proactive aggregation in large overlay networks

  2004cited by this paper
• On the Uniqueness of Loopy Belief Propagation Fixed Points

  2004cited by this paper
• Message Errors in Belief Propagation

  2004cited by this paper
• Robust aggregation protocols for large-scale overlay networks

  2004cited by this paper
• Estimating Aggregates on a Peer-to-Peer Network

  2003cited by this paper
• Computing aggregates for monitoring wireless sensor networks

  2003cited by this paper
• Gossip-based computation of aggregate information

  2003cited by this paper
• Tree-based reparameterization framework for analysis of sum-product and related algorithms

  2003cited by this paper
• Distributed Optimization in Adaptive Networks

  2003cited by this paper
• Supporting aggregate queries over ad-hoc wireless sensor networks

  2002cited by this paper
• Loopy Belief Propogation and Gibbs Measures

  2002cited by this paper
• An analysis of belief propagation on the turbo decoding graph with Gaussian densities

  2001cited by this paper
• The capacity of low-density parity-check codes under message-passing decoding

  2001cited by this paper
• ANALYSIS OF A NONREVERSIBLE MARKOV CHAIN SAMPLER

  2000cited by this paper
• Correctness of Local Probability Propagation in Graphical Models with Loops

  2000cited by this paper
• Directed diffusion: a scalable and robust communication paradigm for sensor networks

  2000cited by this paper
• Correctness of Belief Propagation in Gaussian Graphical Models of Arbitrary Topology

  1999cited by this paper
• IEEE TRANSACTIONS ON INFORMATION THEORY

  1998cited by this paper
• Iterative decoding on graphs with a single cycle

  1998cited by this paper
• Partial Solutions Manual Parallel and Distributed Computation : Numerical Methods

  1997cited by this paper
• Probabilistic Counting Algorithms for Data Base Applications

  1985cited by this paper
• Problems in decentralized decision making and computation

  1984cited by this paper
• Proceedings of the 5th Symposium on Operating Systems Design and Implementation Tag: a Tiny Aggregation Service for Ad-hoc Sensor Networks

  year unknowncited by this paper

• Unified Cooperative Localization via Augmented Factor Graph and Error State Message Passing

  2025cites this paper
• Message Passing-Based Distributed Track-Level Fusion Tracking for Space-Based Radar Networks With Time-Varying Topology

  2025cites this paper
• Adaptive diffusion networks: An overview

  2024cites this paper
• Optimizing Gossiping for Asynchronous Fault-Prone IoT Networks With Memory and Battery Constraints

  2024cites this paper
• The $s$-Energy and Its Applications

  2024cites this paper
• Decentralized Expectation Propagation for Semi-Blind Channel Estimation in Cell-Free Networks

  2024cites this paper
• Distributed Memory Approximate Message Passing

  2024cites this paper
• Expectation Propagation for Semi-Blind Channel Estimation in Cell-Free Networks

  2024cites this paper
• Distributed Inference With Variational Message Passing in Gaussian Graphical Models: Tradeoffs in Message Schedules and Convergence Conditions

  2024cites this paper
• Decentralized Generalized Approximate Message-Passing for Tree-Structured Networks

  2023influential citation
• Design and Implementation of Ambiently Powered Internet of Things-That-Think With Asynchronous Inference

  2023cites this paper
• A Connectivity-Sensitive Approach to Consensus Dynamics

  2023cites this paper
• A Distributed Average Cost Reinforcement Learning approach for Power Control in Wireless 5G Networks

  2022cites this paper
• Robust one-dimensional calibration and localisation of a distributed camera sensor network

  2020cites this paper
• Optimal Combination Weight for Sparse Diffusion Least-Mean-Square based on Consensus Propagation

  2020cites this paper
• Distributed Verification of Belief Precisions Convergence in Gaussian Belief Propagation

  2020cites this paper
• Workspace Partitioning and Topology Discovery Algorithms for Heterogeneous Multiagent Networks

  2020cites this paper
• Convergence Analysis of Gaussian SPAWN Under High-Order Graphical Models

  2020cites this paper
• Asynchronous epidemic algorithms for consistency in large-scale systems

  2020cites this paper
• Efficient distributed average consensus in wireless sensor networks

  2020cites this paper
• A Factor Graph-Based Distributed Consensus Kalman Filter

  2020cites this paper
• Resilient Multi-Dimensional Consensus and Optimization in Adversarial Environment

  2020cites this paper
• Resilient multi-dimensional consensus in adversarial environment

  2020cites this paper
• Convergence of Gaussian Belief Propagation Under General Pairwise Factorization: Connecting Gaussian MRF with Pairwise Linear Gaussian Model

  2019influential citation
• On the Convergence of Message Passing Computation of Harmonic Influence in Social Networks

  2019cites this paper
• Diffusion LMS Based on Message Passing Algorithm

  2019influential citation
• Analysis of containment control for multi-agent systems based on broadcast gossip algorithm

  2019cites this paper
• Convergence Analysis of Gaussian Belief Propagation Under High-Order Factorization and Asynchronous Scheduling

  2019cites this paper
• Fixed Points of Gaussian Belief Propagation and Relation to Convergence

  2019cites this paper
• Accelerated Gossip in Networks of Given Dimension Using Jacobi Polynomial Iterations

  2018influential citation
• Consensus‐based distributed learning for robust convex optimization with a scenario approach

  2018cites this paper
• Distributed Approximate Message Passing Algorithm Using Summation Propagation

  2018cites this paper
• Distributed Optimization Over Networks

  2018cites this paper
• An Adaptive Combination Rule for Diffusion LMS Based on Consensus Propagation

  2018cites this paper
• Distributed energy sharing in energy internet through distributed averaging

  2018cites this paper
• Averaging in Time-Invariant Networks

  2018cites this paper
• Distributed Approximate Message Passing with Summation Propagation

  2018cites this paper
• A Method of Indirect Configuration Propagation With Estimation of System State in Networked Multi-Agent Dynamic Systems

  2018cites this paper
• Gossip of Statistical Observations using Orthogonal Polynomials

  2018influential citation
• Consensus Filter-Based Distributed Variational Bayesian Algorithm for Flow and Speed Density Prediction With Distributed Traffic Sensors

  2017cites this paper
• Decentralized Task Allocation Using Local Information Consistency Assumptions

  2017cites this paper
• Fast distributed demand response algorithm in smart grid

  2017cites this paper
• Accelerated consensus via Min-Sum Splitting

  2017influential citation
• Based Organization : Notions and definitions

  2017cites this paper
• Effect of gossiping on some basic wireless sensor network protocols

  2017cites this paper
• A CONVERGENCE ANALYSIS OF LDPC DECODING BASED ON EIGENVALUES Neha Ashok Kharate Thesis Prepared for the Degree of MASTER OF SCIENCE UNIVERSITY OF NORTH TEXAS August 2017 Kharate, Neha Ashok. A Convergence Analysis of LDPC Decoding based on Eigenvalues

  2017cites this paper
• Networks in Smart Cities from a Graph Theoretic Point of View

  2017cites this paper
• Diffusion LMS using consensus propagation

  2017influential citation
• Distributed Algorithms for Aggregative Games on Graphs

  2016cites this paper
• A novel distributed variational approximation method for density estimation in sensor networks

  2016cites this paper
• An unequal error protection scheme for reliable peer-to-peer scalable video streaming

  2016influential citation
• Topology control in mobile sensor networks using information space feedback

  2016cites this paper
• A new approach to Laplacian solvers and flow problems

  2016cites this paper
• The role of information assumptions in decentralized task allocation: A tutorial

  2016cites this paper
• The harmonic influence in social networks and its distributed computation by message passing

  2016cites this paper
• Collection and Dissemination of Data on Time-Varying Digraphs

  2016cites this paper
• Distributed Soft-Data-Constrained Multi-Model Particle Filter

  2015cites this paper
• Topology Control for Connectivity Maintenance in Cooperative Mobile Robot Networks

  2015cites this paper
• Distributed Iterative Thresholding for $\ell _{0}/\ell _{1}$ -Regularized Linear Inverse Problems

  2015cites this paper
• Theoretical guarantees and complexity reduction in information planning

  2015cites this paper
• Decentralized Eigenvalue Algorithms for Distributed Signal Detection in Wireless Networks

  2015cites this paper
• A link between consensus building and Low Density Parity Check decoding

  2015cites this paper
• Distributed Hybrid Information and Plan Consensus HIPC for Semi-autonomous UAV Teams

  2015cites this paper
• Energy conservative distributed average consensus through connected dominating set

  2015cites this paper
• A Fast Robust Nonlinear Dynamic Average Consensus Estimator in Discrete Time∗∗This work was supported in part by a grant from the Office of Naval Research.

  2015cites this paper
• CONTROLE DE TOPOLOGIA PARA A MANUTENÇÃO DA CONECTIVIDADE EM SISTEMAS MULTI-ROBÔS UTILIZANDO CONSENSO E CONTROLE PREDITIVO

  2015cites this paper
• Cooperative Mission Planning for Multi-UAV Teams

  2015cites this paper
• Online learning over distributed networks

  2015cites this paper
• D.2.1 – Query Based Organization : Notions and definitions

  2015cites this paper
• Message passing algorithms - methods and applications

  2015cites this paper
• Convergence Rate of Distributed Averaging Dynamics and Optimization in Networks

  2015cites this paper
• Mathematical Programs for Belief Propagation and Consensus

  2015cites this paper
• Decentralized Bayesian consensus over networks

  2014cites this paper
• High-level Information Fusion for Constrained SMC Methods and Applications

  2014influential citation
• The Hybrid Information and Plan Consensus Algorithm with Imperfect Situational Awareness

  2014cites this paper
• On the convergence of average consensus with generalized metropolis-hasting weights

  2014cites this paper
• Source-reliability-adaptive distributed information fusion

  2014influential citation
• High-level Information Fusion for Constrained SMC Methods and Applications

  2014cites this paper
• Self-stabilizing Consensus Average Algorithm in Distributed Sensor Networks

  2013cites this paper
• Variational Sparse Bayesian Learning: Centralized and Distributed Processing

  2013influential citation
• Gossip-based Protocols for Large-scale Distributed Systems = Pletyka protokollok nagyméretű elosztott rendszerekben

  2013cites this paper
• Distributed Consensus Formation Through Unconstrained Gossiping

  2013cites this paper
• A strategy for adjusting combination weights over adaptive networks

  2013cites this paper
• Distributed soft thresholding for sparse signal recovery

  2013cites this paper
• A Distributed Algorithm for Solving Positive Definite Linear Equations Over Networks With Membership Dynamics

  2013cites this paper
• Running Consensus for Decentralized Detection

  2013cites this paper
• Extending Robustness and Randomization from Consensus to Symmetrization Algorithms

  2013cites this paper
• The Security Properties of In-Network Aggregation

  2013cites this paper
• A Chemistry-Inspired Framework for Achieving Consensus in Wireless Sensor Networks

  2013cites this paper
• Structured Variational Methods for Distributed Inference in Networked Systems: Design and Analysis

  2013influential citation
• Decentralized Eigenvalue Algorithms for Distributed Signal Detection in Cognitive Networks

  2013cites this paper
• Bayes’sche Consensus-Regelung in dezentralen vernetzten Systemen / Bayesian Consensus Control in Decentralized Networked Systems

  2013cites this paper
• A Gossip Method for Optimal Consensus on a Binary State From Binary Actions

  2013cites this paper
• A hybrid sender/receiver-driven error protection scheme for reliable P2P scalable video streaming

  2013cites this paper
• Distributed Asynchronous Algorithms for Solving Positive Definite Linear Equations over Dynamic Networks

  2013cites this paper
• Randomized Gossip Algorithm with Unreliable Communication

  2012cites this paper
• Decision, Risk & Operations Working Papers Series

  2012cites this paper
• A large scale analysis of a classification algorithm over sensor networks

  2012cites this paper
• Controlled Hopwise Averaging and Its Convergence Rate

  2012cites this paper
• Decentralized Task Re-planning Approaches with en Route Information Rewards

  2012cites this paper