Geographic gossip on geometric random graphs via affine combinations

ABSTRACT

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. We develop a new protocol for Geographic Gossip, in which counter-intuitively, we use "non-convex affinecombinations" as updates in addition to convex combinations to accelerate the averaging process.

REFERENCES

• 1: Dimitri P. Bertsekas , John N. Tsitsiklis, Parallel and Distributed Computation: Numerical Methods, Athena Scientific, 1997
• 2: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Gossip algorithms : Design, analysis and applications. In Proceedings of the 24th Conference of the IEEE Communications Society (INFOCOM 2005), 2005.
• 3: S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Mixing Times for Random Walks on Geometric Random Graphs. SIAM ANALCO 2005.
• 4: P. Gupta and P. Kumar. The capacity of wireless networks. IEEE Transactions on Information Theory, 46(2):388--404, March 2000.
• 5: Alexandros G. Dimakis , Anand D. Sarwate , Martin J. Wainwright, Geographic gossip: efficient aggregation for sensor networks, Proceedings of the fifth international conference on Information processing in sensor networks, April 19-21, 2006, Nashville, Tennessee, USA [doi>10.1145/1127777.1127791]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.1 Systems and Information Theory
          Subjects: Information theory

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Measurement

Keywords:
affine combinations, geometric random graphs, gossip algorithms