Consensus Propagation

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 (6)

• Geographic Gossip: Efficient Averaging for Sensor Networks
• Polynomial Filtering for Fast Convergence in Distributed Consensus
• Convergence of the Min-Sum Algorithm for Convex Optimization
• Order-Optimal Consensus through Randomized Path Averaging
• Convergence of Min-Sum Message Passing for Quadratic Optimization
• Orbit-Product Representation and Correction of Gaussian Belief Propagation