Title :
The speed of greed: Characterizing myopic gossip through network voracity
Author :
Üstebay, Deniz ; Oreshkin, Boris ; Coates, Mark ; Rabbat, Michael
Author_Institution :
Dept. of Electr. & Comput. Eng., McGill Univ., Montreal, QC
Abstract :
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.
Keywords :
convergence of numerical methods; eigenvalues and eigenfunctions; greedy algorithms; radio broadcasting; radio networks; random processes; randomised algorithms; telecommunication network topology; convergence rate; eigenvalue characterization; greedy gossip; myopic gossip; network voracity; randomized gossip; topology-dependent constant; wireless broadcasting; wireless communication; Algorithm design and analysis; Broadcasting; Computer networks; Convergence; Eigenvalues and eigenfunctions; Network topology; Roentgenium; Signal processing algorithms; Wireless communication; Wireless sensor networks; Distributed signal processing; average consensus; gossip algorithms; wireless sensor networks;
Conference_Titel :
Acoustics, Speech and Signal Processing, 2009. ICASSP 2009. IEEE International Conference on
Conference_Location :
Taipei
Print_ISBN :
978-1-4244-2353-8
Electronic_ISBN :
1520-6149
DOI :
10.1109/ICASSP.2009.4960421