Gossip-based aggregate computation: computing faster with non address-oblivious schemes

ABSTRACT

In this paper, we sketch a novel gossip-based scheme that allows all the nodes in an n-node overlay network to compute a common aggregate (MAX) of their values using O(n log log n) messages within O(log n) rounds of communication. Our result is achieved relaxing the hypothesis that nodes are address-oblivious, raising the question whether this paradigm (address-aware) is more expressive than the address-oblivious one.

REFERENCES

• 1: N. Alon, J.H. Spencer, P. Erdös "The Probabilistic Method," Wiley-Interscience Series in Discrete Mathematics and Optimization, 1992
• 2: S. P. Boyd, A. Ghosh, B. Prabhakar, D. Shah "Randomized gossip algorithms," IEEE Transactions on Information Theory, 2006, v. 52
• 3: R. Karp , C. Schindelhauer , S. Shenker , B. Vocking, Randomized rumor spreading, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.565, November 12-14, 2000
• 4: David Kempe , Alin Dobra , Johannes Gehrke, Gossip-Based Computation of Aggregate Information, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.482, October 11-14, 2003
• 5: R. Di Pietro, L. V. Mancini, A. Mei "Efficient and Resilient Key Discovery Based on Pseudo-Random Key Pre-Deployment," In Proc. of IEEE IPDPS, 2004

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation

General Terms:
Algorithms

Keywords:
algorithms, design, theory.