Consensus Propagation
- 23 October 2006
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 52 (11) , 4753-4766
- https://doi.org/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 convergeKeywords
All Related Versions
This publication has 23 references indexed in Scilit:
- Convergence in Multiagent Coordination, Consensus, and FlockingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2006
- Fastest Mixing Markov Chain on a PathThe American Mathematical Monthly, 2006
- Gossip algorithms: design, analysis and applicationsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2005
- Bounding Fastest MixingElectronic Communications in Probability, 2005
- Symmetry Analysis of Reversible Markov ChainsInternet Mathematics, 2005
- Approximate aggregation techniques for sensor databasesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Gossip-based computation of aggregate informationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Probabilistic counting algorithms for data base applicationsPublished by Elsevier ,2003
- Tree-based reparameterization framework for analysis of sum-product and related algorithmsIEEE Transactions on Information Theory, 2003
- Analysis of a nonreversible Markov chain samplerThe Annals of Applied Probability, 2000