%0 Conference Proceedings
%B IEEE Distributed Computing in Sensor Systems (DCOSS)
%D 2010
%T Fast Decentralized Averaging via Multi-scale Gossip
%A Konstantinos I Tsianos
%A Michael G. Rabbat
%C Santa Barbara
%I Springer Berlin / Heidelberg
%K distributed computing
%K gossip algorithms
%P 320-333
%S Lecture Notes in Computer Science
%U http://dx.doi.org/10.1007/978-3-642-13651-1_23
%V 6131
%X 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.
%Z Best Student Paper Award
%8 06/2010
%> http://networks.ece.mcgill.ca/sites/default/files/dcoss2010_0.pdf