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
Volume6131
Pagination320-333
Date Published06/2010
PublisherSpringer Berlin / Heidelberg
Conference LocationSanta Barbara
ISBN978-3-642-13650-4
Keywordsdistributed 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.

URLhttp://dx.doi.org/10.1007/978-3-642-13651-1_23
Refereed DesignationRefereed
AttachmentSize
dcoss2010.pdf430.33 KB