Consensus propagation

被引:140
作者
Moallemi, Ciamac C. [1 ]
Van Roy, Benjamin
机构
[1] Stanford Univ, Dept Elect Engn, Stanford, CA 94305 USA
[2] Stanford Univ, Dept Management Sci & Engn, Stanford, CA 94305 USA
基金
美国国家科学基金会;
关键词
belief propagation; distributed averaging; distributed consensus; distributed signal processing; Gaussian Markov random fields; max-product algorithm; message-passing algorithms; min-sum algorithm; sum-product algorithm;
D O I
10.1109/TIT.2006.883539
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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 painvise 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.
引用
收藏
页码:4753 / 4766
页数:14
相关论文
共 38 条
  • [1] AJI SM, 1998, P C INF SCI SYST PRI
  • [2] [Anonymous], 2003, Estimating aggregates on a peer-to-peer network
  • [3] Bayati M, 2005, 2005 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), VOLS 1 AND 2, P1763
  • [4] Bertsekas D., 2015, Parallel and distributed computation: numerical methods
  • [5] Blondel VD, 2005, IEEE DECIS CONTR P, P2996
  • [6] Boyd S, 2005, IEEE INFOCOM SER, P1653
  • [7] Fastest mixing Markov chain on a path
    Boyd, S
    Diaconis, P
    Sun, J
    Xiao, L
    [J]. AMERICAN MATHEMATICAL MONTHLY, 2006, 113 (01) : 70 - 74
  • [8] Boyd S., 2005, P SIAM WORKSH AN ALG
  • [9] Symmetry Analysis of Reversible Markov Chains
    Boyd, Stephen
    Diaconis, Persi
    Parrilo, Pablo
    Xiao, Lin
    [J]. INTERNET MATHEMATICS, 2005, 2 (01) : 31 - 71
  • [10] Approximate aggregation techniques for sensor databases
    Considine, J
    Li, FF
    Kollios, G
    Byers, J
    [J]. 20TH INTERNATIONAL CONFERENCE ON DATA ENGINEERING, PROCEEDINGS, 2004, : 449 - 460