@proceedings {53,
title = {Fast Decentralized Averaging via Multi-scale Gossip},
journal = {IEEE Distributed Computing in Sensor Systems (DCOSS)},
volume = {6131},
year = {2010},
note = {Best Student Paper Award},
month = {06/2010},
pages = {320-333},
publisher = {Springer Berlin / Heidelberg},
address = {Santa Barbara},
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.},
keywords = {distributed computing, gossip algorithms},
issn = {978-3-642-13650-4},
url = {http://dx.doi.org/10.1007/978-3-642-13651-1_23},
attachments = {http://networks.ece.mcgill.ca/sites/default/files/dcoss2010_0.pdf},
author = {Konstantinos I Tsianos and Michael G. Rabbat}
}