The speed of greed: Characterizing myopic gossip through network voracity

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.