Broadcast Gossip Algorithms for Consensus
Broadcast Gossip Algorithms for Consensus
复制标题
DOI：
10.1109/tsp.2009.2016247
复制
发表时间：
2009-07-01
影响因子：
5.4
通讯作者：
Scaglione, Anna
中科院分区：
文献类型：
--
作者：
Aysal, Tuncer Can;Yildiz, Mehmet Ercan;Scaglione, Anna
受无线传感器、对等网络和自组织网络应用的启发，我们研究了在任意连接的节点网络中交换信息和计算的分布式广播算法。具体来说，我们研究了一个基于广播的八卦算法计算（可能加权）的平均值的初始测量的节点在网络中的每个节点。我们表明，广播八卦算法几乎肯定会收敛到一个共识。我们证明了随机共识值是，在预期中，初始节点测量的平均值，它可以任意接近这个值的均方误差意义上，平衡的连接模型下，并通过权衡收敛速度与计算精度。我们提供的均方误差性能的理论和数值结果，收敛速度和研究的效果的“混合参数”的广播八卦算法的收敛速度。结果表明，均方误差严格减少，通过迭代，直到达成共识。最后，我们通过理论和数值结果评估和比较广播八卦算法实现给定共识距离的通信成本。
Motivated by applications to wireless sensor, peer-to-peer, and ad hoe networks, we study distributed broadcasting algorithms for exchanging information and computing in an arbitrarily connected network of nodes. Specifically, we study a broadcasting-based gossiping algorithm to compute the (possibly weighted) average of the initial measurements of the nodes at every node in the network. We show that the broadcast gossip algorithm converges almost surely to a consensus. We prove that the random consensus value is, in expectation, the average of initial node measurements and that it can be made arbitrarily close to this value in mean squared error sense, under a balanced connectivity model and by trading off convergence speed with accuracy of the computation. We provide theoretical and numerical results on the mean square error performance, on the convergence rate and study the effect of the "mixing parameter" on the convergence rate of the broadcast gossip algorithm. The results indicate that the mean squared error strictly decreases through iterations until the consensus is achieved. Finally, we assess and compare the communication cost of the broadcast gossip algorithm to achieve a given distance to consensus through theoretical and numerical results.