Consensus Propagation
arXiv:cs/0603078 · doi:10.1109/TIT.2006.883539
Abstract
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.
journal version
Cited by in corpus (32)
- Gossip Algorithms for Distributed Signal Processing
- Geographic Gossip: Efficient Averaging for Sensor Networks
- Optimization and Analysis of Distributed Averaging with Short Node Memory
- Polynomial Filtering for Fast Convergence in Distributed Consensus
- Belief-Propagation for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs with Integer Solutions
- On distributed convex optimization under inequality and equality constraints via primal-dual subgradient methods
- Efficient Information Aggregation Strategies for Distributed Control and Signal Processing
- Consensus over Random Graph Processes: Network Borel-Cantelli Lemmas for Almost Sure Convergence
- Location-Aided Fast Distributed Consensus in Wireless Networks
- Convergence of the Min-Sum Algorithm for Convex Optimization
- Fixing Convergence of Gaussian Belief Propagation
- Convergence Speed of the Consensus Algorithm with Interference and Sparse Long-Range Connectivity
- Convergence Speed in Distributed Consensus and Control
- Workspace Partitioning and Topology Discovery Algorithms for Heterogeneous Multi-Agent Networks
- Order-Optimal Consensus through Randomized Path Averaging
- Two Lectures on Iterative Coding and Statistical Mechanics
- A Chemistry-Inspired Framework for Achieving Consensus in Wireless Sensor Networks
- Randomized Gossip Algorithm with Unreliable Communication
- Convergence of Min-Sum Message Passing for Quadratic Optimization
- The harmonic influence in social networks and its distributed computation by message passing
- Average-Consensus Algorithms in a Deterministic Framework
- Distributed Consensus Formation Through Unconstrained Gossiping
- Decentralized Eigenvalue Algorithms for Distributed Signal Detection in Cognitive Networks
- Gaussian Belief with dynamic data and in dynamic network
- Orbit-Product Representation and Correction of Gaussian Belief Propagation
- A distributed classification/estimation algorithm for sensor networks
- Mathematical Programs for Belief Propagation and Consensus
- Controlled Hopwise Averaging: Bandwidth/Energy-Efficient Asynchronous Distributed Averaging for Wireless Networks
- A lower bound for distributed averaging algorithms
- Collection and Dissemination of Data on Time-Varying Digraphs
- Distributed Algorithms for Aggregative Games on Graphs
- Distributed Clock Skew and Offset Estimation in Wireless Sensor Networks: Asynchronous Algorithm and Convergence Analysis