Greedy Gossip With Eavesdropping

Date Added: Feb 2010
Format: PDF

This paper presents Greedy Gossip with Eavesdropping (GGE), a novel randomized gossip algorithm for distributed computation of the average consensus problem. In gossip algorithms, nodes in the network randomly communicate with their neighbors and exchange information iteratively. The algorithms are simple and decentralized, making them attractive for wireless network applications. In general, gossip algorithms are robust to unreliable wireless conditions and time varying network topologies. In this paper, the authors introduce GGE and demonstrate that greedy updates lead to rapid convergence. They do not require nodes to have any location information. Instead, greedy updates are made possible by exploiting the broadcast nature of wireless communications.