Abstract
We present a simple, deterministic gossip protocol for solving the distributed averaging problem. Each node has an initial value and the objective is for all nodes to reach consensus on the average of these values using only communication between neighbors in the network. We first give an analysis of the protocol in structured networks, namely d-dimensional discrete tori and lattices, and show that in an n node network, the number of rounds required for the protocol to converge to within ε of the average is O(|log(ε)| n 2/ d). We then extend our results to derive upper and lower bounds on convergence for arbitrary graphs based on the dimensions of spanning supergraphs and subgraphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Salapaka, S., Peirce, A., Dahleh, M.: Analysis of a circulant based preconditioner for a class of lower rank extracted systems. In: Numerical Linear Algebra with Applications, vol. 12, pp. 9–32 (2005)
Patterson, S., Bamieh, B., El Abbadi, A.: Convergence analysis of scalable gossip protocols. Technical Report 2006-09, Department of Computer Science, University of California, Santa Barbara (2006)
Kempe, D., Dobra, A., Gehrke, J.: Gossip-based computation of aggregate information. In: IEEE Symposium on Foundations of Computer Science, p. 482 (2003)
Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Gossip algorithms: Design, analysis and applications. In: INFOCOM, vol. 3, pp. 1653–1664 (2005)
Xiao, L., Boyd, S.: Fast linear iterations for distributed averaging. In: Systems and Control Letters, vol. 53, pp. 65–78 (2005)
Kranakis, E., Krizanc, D., van den Berg, J.: Computing boolean functions on anonymous networks. Information and Computation 114(2), 214–236 (1994)
Barooah, P., Hespanha, J.: Graph effective resistances and distributed control: Part ii – electrical analogy and scalability. In: 45th IEEE Conference on Decision and Control (February 2006) (submitted, 2006)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Patterson, S., Bamieh, B., El Abbadi, A. (2006). Brief Announcement: Convergence Analysis of Scalable Gossip Protocols. In: Dolev, S. (eds) Distributed Computing. DISC 2006. Lecture Notes in Computer Science, vol 4167. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11864219_39
Download citation
DOI: https://doi.org/10.1007/11864219_39
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44624-8
Online ISBN: 978-3-540-44627-9
eBook Packages: Computer ScienceComputer Science (R0)