Paper Info
Title
Convergence of local communication chain strategies via linear transformations: or how to trade locality for speed
Abstract
Consider two far apart base stations connected by an arbitrarily winding chain of n relay robots to transfer messages between them. Each relay acts autonomously, has a limited communication range, and knows only a small, local part of its environment. We seek a strategy for the relays to minimize the chain's length. We describe a large strategy class in form of linear transformations of the spatial vectors connecting neighboring robots. This yields surprising correlations between several strategy properties and characteristics of these transformations (e.g., "reasonable" strategies correspond to transformations given by doubly stochastic matrices). Based on these results, we give almost tight bounds on the strategies' convergence speed by applying and extending results about the mixing time of Markov chains. Eventually, our framework enables us to define strategies where each relay bases its decision where to move only on the positions of its k next left and right neighbors, and to prove a convergence speed of Θ(n2/k2 log n) for these strategies. This not only closes a gap between upper and lower runtime bounds of a known strategy (Go-To-The-Middle), but also allows for a trade-off between convergence properties and locality.
Year
DOI
Venue
2011
10.1145/1989493.1989517
SPAA
Keywords
Field
DocType
local communication chain strategy,convergence property,convergence speed,known strategy,k2 log n,large strategy class,base station,linear transformation,strategy property,k next left,acts autonomously,markov chain,distributed algorithm,distributed algorithms,swarm robotics,markov chains,mixing time
Convergence (routing),Mathematical optimization,Locality,Matrix (mathematics),Computer science,Markov chain,Distributed algorithm,Linear map,Relay,Distributed computing,Swarm robotics
Conference
Citations 
PageRank 
References 
5
0.42
9
Authors
2
Name
Order
Citations
PageRank
Peter Kling1346.05
Friedhelm Meyer auf der Heide21744238.01