Local Interference Can Accelerate Gossip Algorithms.
Lists
Only you see this
Abstract
In this paper, we show how interference can be exploited to perform gossip computations for average-based consensus over a larger local neighborhood, rather than only pairs of nodes. We use a new channel coding technique called computation coding to compute sums reliably over the wireless medium. Since many nodes can simultaneously average in a single round, our neighborhood gossip algorithm converges faster than the standard nearest neighbor gossip algorithm. For a network with <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> nodes and size <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</i> neighborhoods, neighborhood gossip requires <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</i> ( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> / <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">m</i> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) rounds while standard gossip requires Θ( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup> ) rounds. Furthermore, we show that if the power path loss coefficient is less than 4, the total transmit energy employed by neighborhood gossip is polynomially smaller than that employed by standard gossip.
BibTeX
@inproceedings{nazer2008local,
author = {Bobak Nazer and Alexandros G. Dimakis and Michael Gastpar},
title = {{Local Interference Can Accelerate Gossip Algorithms.}},
booktitle = {Allerton},
year = {2008},
doi = {10.1109/allerton.2008.4797612},
}Loading related content...