Fast Decentralized Averaging via Multi-scale Gossip

TitleFast Decentralized Averaging via Multi-scale Gossip
Publication TypeConference Proceedings
Year of Publication2010
AuthorsTsianos, K. I., and M. G. Rabbat
Conference NameIEEE Distributed Computing in Sensor Systems (DCOSS)
Series TitleLecture Notes in Computer Science
Date Published06/2010
PublisherSpringer Berlin / Heidelberg
Conference LocationSanta Barbara
Keywordsdistributed computing, gossip algorithms

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.

Refereed DesignationRefereed
dcoss2010.pdf430.33 KB