TY - JOUR
T1 - The impact of mobility on gossip algorithms
AU - Sarwate, Anand Dilip
AU - Dimakis, Alexandros G.
N1 - Funding Information:
Manuscript received December 29, 2009; revised June 27, 2011; accepted September 16, 2011. Date of current version February 29, 2012. The work of A. D. Sarwate was supported by the California Institute for Telecommunications and Information Technology (CALIT2) at University of California, San Diego. The work of A. G. Dimakis was supported by the National Science Foundation Career Award CCF 1055099. The material in this paper was presented in part at INFOCOM 2009 and CAMSAP 2009.
PY - 2012/3
Y1 - 2012/3
N2 - The influence of node mobility on the convergence time of averaging gossip algorithms in networks is studied. It is shown that a small number of fully mobile nodes can yield a significant decrease in convergence time. A method is developed for deriving lower bounds on the convergence time by merging nodes according to their mobility pattern. This method is used to show that if the agents have 1-D mobility in the same direction, the convergence time is improved by at most a constant. Upper bounds on the convergence time are obtained using techniques from the theory of Markov chains and show that simple models of mobility can dramatically accelerate gossip as long as the mobility paths overlap significantly. Simulations verify that different mobility patterns can have significantly different effects on the convergence of distributed algorithms.
AB - The influence of node mobility on the convergence time of averaging gossip algorithms in networks is studied. It is shown that a small number of fully mobile nodes can yield a significant decrease in convergence time. A method is developed for deriving lower bounds on the convergence time by merging nodes according to their mobility pattern. This method is used to show that if the agents have 1-D mobility in the same direction, the convergence time is improved by at most a constant. Upper bounds on the convergence time are obtained using techniques from the theory of Markov chains and show that simple models of mobility can dramatically accelerate gossip as long as the mobility paths overlap significantly. Simulations verify that different mobility patterns can have significantly different effects on the convergence of distributed algorithms.
KW - Consensus protocols
KW - Markov chains
KW - distributed algorithms
KW - distributed averaging
KW - distributed processing
KW - gossip protocols
KW - mobility
KW - peer-to-peer networks
KW - wireless sensor networks
UR - http://www.scopus.com/inward/record.url?scp=84857713234&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84857713234&partnerID=8YFLogxK
U2 - 10.1109/TIT.2011.2177753
DO - 10.1109/TIT.2011.2177753
M3 - Article
AN - SCOPUS:84857713234
SN - 0018-9448
VL - 58
SP - 1731
EP - 1742
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 3
M1 - 6157082
ER -