Title | Fast Decentralized Averaging via Multi-scale Gossip |
Publication Type | Conference Proceedings |
Year of Publication | 2010 |
Authors | Tsianos, K. I., and M. G. Rabbat |
Conference Name | IEEE Distributed Computing in Sensor Systems (DCOSS) |
Series Title | Lecture Notes in Computer Science |
Volume | 6131 |
Pagination | 320-333 |
Date Published | 06/2010 |
Publisher | Springer Berlin / Heidelberg |
Conference Location | Santa Barbara |
ISBN | 978-3-642-13650-4 |
Keywords | distributed computing, gossip algorithms |
Abstract | We are interested in the problem of computing the average consensus in a distributed fashion on random geometric graphs. We describe a new algorithm called Multi-scale Gossip which employs a hierarchical decomposition of the graph to partition the computation into tractable sub-problems. Using only pairwise messages of fixed size that travel at most O(n^1/3 ) hops, our algorithm is robust and has communication cost of O(n log log n log(epsilon^-1) ) transmissions, which is order-optimal up to the logarithmic factor in n. Simulated experiments verify the good expected performance on graphs of many thousands of nodes. |
URL | http://dx.doi.org/10.1007/978-3-642-13651-1_23 |
Refereed Designation | Refereed |
Attachment | Size |
---|---|
dcoss2010.pdf | 430.33 KB |