Computer Science – Multiagent Systems
Scientific paper
2006-12-04
Computer Science
Multiagent Systems
15 pages, submitted
Scientific paper
In recent times, a considerable amount of work has been devoted to the development and analysis of gossip algorithms in Geometric Random Graphs. In a recently introduced model termed "Geographic Gossip," each node is aware of its position but possesses no further information. Traditionally, gossip protocols have always used convex linear combinations to achieve averaging. We develop a new protocol for Geographic Gossip, in which counter-intuitively, we use {\it non-convex affine combinations} as updates in addition to convex combinations to accelerate the averaging process. The dependence of the number of transmissions used by our algorithm on the number of sensors $n$ is $n \exp(O(\log \log n)^2) = n^{1 + o(1)}$. For the previous algorithm, this dependence was $\tilde{O}(n^{1.5})$. The exponent 1+ o(1) of our algorithm is asymptotically optimal. Our algorithm involves a hierarchical structure of $\log \log n$ depth and is not completely decentralized. However, the extent of control exercised by a sensor on another is restricted to switching the other on or off.
No associations
LandOfFree
Geographic Gossip on Geometric Random Graphs via Affine Combinations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Geographic Gossip on Geometric Random Graphs via Affine Combinations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Geographic Gossip on Geometric Random Graphs via Affine Combinations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-649451