Paper Info
Title
Queue-based broadcast gossip algorithm for consensus.
Abstract
We study broadcast gossip algorithms to compute the average of given initial sensor measurements. In the context of wireless networks, an algorithm was proposed by Scaglione et al. that allows a single node to broadcast at each time with geometrically fast convergence to consensus. To improve the rate of convergence to consensus, we go beyond this single node broadcast approach and propose a queue-based broadcast gossip algorithm, in which simultaneous node broadcasts are allowed. Since packet collisions may happen, we choose time-varying update weights. Using a novel interval-based consensus error analysis to handle the time-dependent update weights, we show that with appropriate choice of parameters, the proposed algorithm converges to consensus in the mean-square sense geometrically fast. We prove that for the class of networks modeled as non-bipartite Ramanujan graphs, the exponent of convergence of the proposed algorithm is independent of the number of nodes, unlike the single node broadcast case which converges slowly in large networks. We also demonstrate through simulations that our proposed algorithm improves the rate of convergence for some other example networks.
Year
Venue
Field
2016
2016 54TH ANNUAL ALLERTON CONFERENCE ON COMMUNICATION, CONTROL, AND COMPUTING (ALLERTON)
Convergence (routing),Broadcasting,Wireless network,Exponent,Ramanujan's sum,Computer science,Network packet,Queue,Theoretical computer science,Rate of convergence,Distributed computing
DocType
ISSN
Citations 
Conference
2474-0195
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Soummya Kar11874115.60
Rohit Negi2126397.44
Mahzoon, M.351.59
Anit Kumar Sahu416212.42