Abstract
Convergence Analysis of Scalable Gossip Protocols
by: Stacy Patterson, Bassam Bamieh, and Amr El Abbadi
Abstract:
We present a simple, deterministic gossip protocol for solving the distributed averaging problem and characterize the relationship between the convergence rate of the protocol and the dimensionality of the network graph. We first give an analysis of the protocol in structured networks, namely d-dimensional discrete tori and d-lattices, and show that the number of rounds required for the protocol to converge to within ε of the average is in 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.
Keywords:
Date:
July 2006
Document: 2006-09
