Greedy Gossip with Eavesdropping

Details Greedy Gossip with Eavesdropping Greedy Gossip with Eavesdropping

2009-09-09

arxiv.org/abs/0909.1830v1

Computer Science

Distributed, Parallel, and Cluster Computing

25 pages, 7 figures

Scientific paper

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 we introduce GGE and demonstrate that greedy updates lead to rapid convergence. We do not require nodes to have any location information. Instead, greedy updates are made possible by exploiting the broadcast nature of wireless communications. During the operation of GGE, when a node decides to gossip, instead of choosing one of its neighbors at random, it makes a greedy selection, choosing the node which has the value most different from its own. In order to make this selection, nodes need to know their neighbors' values. Therefore, we assume that all transmissions are wireless broadcasts and nodes keep track of their neighbors' values by eavesdropping on their communications. We show that the convergence of GGE is guaranteed for connected network topologies. We also study the rates of convergence and illustrate, through theoretical bounds and numerical simulations, that GGE consistently outperforms randomized gossip and performs comparably to geographic gossip on moderate-sized random geometric graph topologies.

Affiliated with

Also associated with

No associations

Rating

Greedy Gossip with Eavesdropping does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Greedy Gossip with Eavesdropping, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Greedy Gossip with Eavesdropping will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-130929