Neighborhood gossip: Concurrent averaging through local interference

In this paper, we study a gossip algorithm for distributed averaging over a wireless sensor network. The usual assumption is that, through properly chosen codes, the physical layer is reduced to a set of reliable bit pipes for the distributed averaging algorithm. However, with a new channel coding technique, computation coding, we can exploit the interference property of the wireless medium for efficient averaging. This then provides a new abstraction for the physical layer: reliable linear equations instead of reliable bit pipes. The ldquoneighborhood gossiprdquo algorithm operates modularly on top of this abstraction. We will show that for certain regimes, such an approach can lead to energy savings that are exponential in the network size and time savings that are polynomial.