On Spatial Gossip Algorithms for Average Consensus

@inproceedings{citeulike:2363740, abstract = {This paper investigates the use of spatial gossip to compute the average consensus in networks such as grids or random geometric graphs, where connectivity is a function of proximity. Randomized gossip is a framework for distributed computation where, at each iteration, a random pair of nodes exchanges information, and then updates their local values by averaging. This simple protocol converges to an average consensus: every node obtains the average of the initial values across the network. In spatial gossip, if the distance between two nodes is d, then they communicate with probability proportional to d-{\ss} for some {\ss} ¿ 0. The special case {\ss} = 0 corresponds to an algorithm known in the sensor network literature as geographic gossip. Dimakis et al. have shown that geographic gossip computes the average to accuracy n-1 in O(n3/2¿log n) transmissions. In this paper we show that the same rates are achieved for {\ss} = 2 and {\ss} = 3. Each setting offers a different balance between the rate of convergence (in gossip rounds) and the average number of transmissions per gossip round. We illustrate, via simulation, that spatial gossip with {\ss} = 2 generally yields superior performance over geographic gossip by a constant factor.}, author = {Rabbat, Michael G. }, booktitle = {Statistical Signal Processing, 2007. SSP '07. IEEE/SP 14th Workshop on}, citeulike-article-id = {2363740}, doi = {http://dx.doi.org/10.1109/SSP.2007.4301350}, journal = {Statistical Signal Processing, 2007. SSP '07. IEEE/SP 14th Workshop on}, keywords = {gossip}, pages = {705--709}, posted-at = {2008-02-11 20:59:17}, priority = {2}, title = {On Spatial Gossip Algorithms for Average Consensus}, url = {http://dx.doi.org/10.1109/SSP.2007.4301350}, year = {2007} }

TY - CONF ID - citeulike:2363740 L3 - citeulike-article-id:2363740 N2 - This paper investigates the use of spatial gossip to compute the average consensus in networks such as grids or random geometric graphs, where connectivity is a function of proximity. Randomized gossip is a framework for distributed computation where, at each iteration, a random pair of nodes exchanges information, and then updates their local values by averaging. This simple protocol converges to an average consensus: every node obtains the average of the initial values across the network. In spatial gossip, if the distance between two nodes is d, then they communicate with probability proportional to d-ß for some ß ¿ 0. The special case ß = 0 corresponds to an algorithm known in the sensor network literature as geographic gossip. Dimakis et al. have shown that geographic gossip computes the average to accuracy n-1 in O(n3/2¿log n) transmissions. In this paper we show that the same rates are achieved for ß = 2 and ß = 3. Each setting offers a different balance between the rate of convergence (in gossip rounds) and the average number of transmissions per gossip round. We illustrate, via simulation, that spatial gossip with ß = 2 generally yields superior performance over geographic gossip by a constant factor. JF - Statistical Signal Processing, 2007. SSP '07. IEEE/SP 14th Workshop on EP - 709 TI - On Spatial Gossip Algorithms for Average Consensus T2 - Statistical Signal Processing, 2007. SSP '07. IEEE/SP 14th Workshop on SP - 705 KW - gossip AU - Rabbat, Michael PY - 2007/// UR - http://dx.doi.org/10.1109/SSP.2007.4301350 ER -