McGill Computer Networks Research Lab

Many distributed signal processing problems involve aggregating vectors of data, and often we are interested in the largest entries of the aggregate vector. For example, in distributed particle filtering one may be interested in fusing information about particles with the largest weights. Gossip algorithms are an attractive method for distributed processing in unreliable networks. We propose top-k selective gossip, an algorithm which reduces the amount of information communicated by updating only the highest k entries at each iteration. We derive convergence properties for this algorithm, and simulation results illustrate significant communication savings compared to randomized gossip.