Efficient decentralized approximation via selective gossip

D. Üstebay, R.M. Castro, M. Rabbat

Research output: Contribution to journalArticlepeer-review

26 Citations (Scopus)
177 Downloads (Pure)


Recently, gossip algorithms have received much attention from the wireless sensor network community due to their simplicity, scalability and robustness. Motivated by applications such as compression and distributed transform coding, we propose a new gossip algorithm called Selective Gossip. Unlike traditional randomized gossip which computes the average of scalar values, we run gossip algorithms in parallel on the elements of a vector. The goal is to compute only the entries which are above a defined threshold in magnitude, i.e., significant entries. Nodes adaptively approximate the significant entries while abstaining from calculating the insignificant ones. Consequently, network lifetime and bandwidth are preserved. We show that with the proposed algorithm nodes reach consensus on the values of the significant entries and on the indices of insignificant ones. We illustrate the performance of our algorithm with a field estimation application. For regular topologies, selective gossip computes an approximation of the field using the wavelet transform. For irregular network topologies, we construct an orthonormal transform basis using eigenvectors of the graph Laplacian. Using two real sensor network datasets we show substantial communication savings over randomized gossip. We also propose a decentralized adaptive threshold mechanism such that nodes estimate the threshold while approximating the entries of the vector for computing the best m-term approximation of the data.
Original languageEnglish
Pages (from-to)805-816
JournalIEEE Journal of Selected Topics in Signal Processing
Issue number4
Publication statusPublished - 2011


Dive into the research topics of 'Efficient decentralized approximation via selective gossip'. Together they form a unique fingerprint.

Cite this