The speed of greed: Characterizing myopic gossip through network voracity

TitleThe speed of greed: Characterizing myopic gossip through network voracity
Publication TypeConference Proceedings
Year of Publication2009
AuthorsÜstebay, D., B. N. Oreshkin, M. J. Coates, and M. G. Rabbat
Conference NameIEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP)
Pagination3665 - 3668
Date PublishedApr. 2009
Conference LocationTaipei, Taiwan
Keywordsaverage consensus, distributed signal processing, gossip algorithms, wireless sensor networks

This paper analyzes the rate of convergence of greedy gossip with eavesdropping (GGE). In previous work, we proposed GGE, a fast gossip algorithm based on exploiting the broadcast nature of wireless communications rather than location information. Assuming all transmissions are wireless broadcasts, nodes can keep track of their neighbors' values by eavesdropping on their communications. Then, when it comes time to gossip, a node greedily and myopically gossips with the neighbor whose value is most different from its own, rather than with a randomly chosen neighbor. Previously, we have proved that GGE converges to the average consensus on connected network topologies and demonstrated that GGE outperforms standard randomized gossip (RG). In this paper we study the rate of convergence of GGE in terms of network voracity which is a topology-dependent constant analogous to the second-largest eigenvalue characterization for RG. Simulations demonstrate that the convergence rate of GGE is superior to existing average consensus algorithms such as geographic gossip.

Refereed DesignationRefereed