The Impact of Mobility on Gossip Algorithms

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2012-03, Vol.58 (3), p.1731-1742
Main Authors: Sarwate, A. D., Dimakis, A. G.
Format: Article
Language:English
Subjects:
Ad hoc networks
Algorithms
Applied sciences
Business and industry local networks
Computer simulation
Consensus protocols
Convergence
Detection, estimation, filtering, equalization, prediction
distributed algorithms
distributed averaging
distributed processing
Exact sciences and technology
gossip protocols
Information theory
Information, signal and communications theory
Lower bounds
Markov analysis
Markov chains
Markov processes
Merging
Mobile communication
mobility
Networks
Networks and services in france and abroad
Partitioning algorithms
peer-to-peer networks
Services and terminals of telecommunications
Signal and communications theory
Signal, noise
Simulation
Systems, networks and services of telecommunications
Telecommunications
Telecommunications and information theory
Telemetry. Remote supervision. Telewarning. Remote control
Teleprocessing networks. Isdn
Upper bound
Upper bounds
Vectors
wireless sensor networks
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2011.2177753