Selective Gossip

Motivated by applications in compression and distributed transform coding, we propose a new gossip algorithm called selective gossip to efficiently compute sparse approximations of network data. We consider running parallel gossip algorithms on the elements of a vector of transform coefficients. Unlike classical randomized gossip, communication between adjacent nodes is data driven and only performed if deemed to significantly improve the estimate of the signal vector. In particular nodes adaptively estimate and focus on using communication resources to compute significant coefficients (above a pre-defined threshold in magnitude). Consequently, energy and bandwidth are conserved by not gossiping on insignificant coefficients. The proposed procedure guarantees that all nodes will reach consensus on (i) the values of significant coefficients and (ii) the indices of insignificant coefficients. Insignificant values are not computed. We illustrate the significant communication savings over global randomized gossiping in a distributed transform coding application.