Jen-Yeu Chen
ABSTRACT
Motivated by applications to modern networking technologies, there has been interest in designing efficient gossip-based protocols for computing aggregate functions. While gossip-based protocols provide robustness due to their randomized nature, reducing the message and time complexity of these protocols is also of paramount importance in the context of resource-constrained networks such as sensor and peer-to-peer networks.
We present the first provably almost-optimal gossip-based algorithms for aggregate computation that are both time optimal and message-optimal. Given a n-node network, our algorithms guarantee that all the nodes can compute the common aggregates (such as Min, Max, Count, Sum, Average, Rank etc.) of their values in optimal O(log n) time and using O(n log log n) messages. Our result improves on the algorithm of Kempe et al. [11] that is time-optimal, but uses O(n log n) messages as well as on the algorithm of Kashyap et al. [10] that uses O(n log log n) messages, but is not time-optimal (takes O(log n log log n) time). Furthermore, we show that our algorithms can be used to improve gossip-based aggregate computation in sparse communication networks, such as in peer-to-peer networks.
The main technical ingredient of our algorithm is a technique called distributed random ranking (DRR) that can be useful in other applications as well. DRR gives an efficient distributed procedure to partition the network into a forest of (disjoint) trees of small size. Since the size of each tree is small, aggregates within each tree can be efficiently obtained at their respective roots. All the roots then perform a uniform gossip algorithm on their local aggregates to reach a distributed consensus on the global aggregates.
Our algorithms are non-address oblivious. In contrast, we show a lower bound of Ω(n log n) on the message complexity of any address-oblivious algorithm for computing aggregates. This shows that non-address oblivious algorithms are needed to obtain significantly better message complexity. Our lower bound holds regardless of the number of rounds taken or the size of the messages used. Our lower bound is the first non-trivial lower bound for gossip-based aggregate computation and also gives the first formal proof that computing aggregates is strictly harder that rumor spreading in the address-oblivious model.
- S. Boyd, A. Ghosh, B. Prabhakar, and D. Shah. Randomized gossip algorithms. IEEE Trans. on Infor. Theory, 52(6): 2508--2530, 2006. Google Scholar
Digital Library
- J.-Y. Chen and J. Hu. Analysis of distributed random grouping for aggregate computation on wireless sensor networks with randomly changing graphs. IEEE Trans. on Parallel and Distributed Systems, 19:1136--1149, 2008. Google ScholarDigital Library
- J.-Y. Chen and G. Pandurangan. Optimal gossip-based aggregate computation. 2009. http://arxiv.org/pdf/1001.3242.Google Scholar
- J.-Y. Chen, G. Pandurangan, and D. Xu. Robust aggregate computation in wireless sensor network: distributed randomized algorithms and analysis. IEEE Trans. on Parallel and Distributed Systems, 17(9):987--1000, Sep. 2006. Google ScholarDigital Library
- A. Demers, D. Greene, C. Hauser, W. Irish, J. Larson, S. Shenker, H. Sturgis, D. Swinehart, and D. Terry. Epidemic algorithms for replicated database maintenance. In PODC, pages 1--12, 1987. Google ScholarDigital Library
- A. G. Dimakis, A. D. Sarwate, and M. J. Wainwright. Geographic gossip: efficient aggregation for sensor networks. In IPSN, pages 69--76, 2006. Google ScholarDigital Library
- J. Gao, L. Guibas, N. Milosavljevic, and J. Hershberger. Sparse data aggregation in sensor networks. In IPSN, pages 430--439, 2007. Google ScholarDigital Library
- M. Jelasity, A. Montresor, and O. Babaoglu. Gossip-based aggregation in large dynamic networks. ACM Trans. Comput. Syst., 23(3):219--252, 2005. Google ScholarDigital Library
- R. M. Karp, C. Schindelhauer, S. Shenker, and B. Vöcking. Randomized rumor spreading. In FOCS, pages 565--574, 2000. Google ScholarDigital Library
- S. Kashyap, S. Deb, K. V. M. Naidu, R. Rastogi, and A. Srinivasan. Efficient gossip-based aggregate computation. In PODS, pages 308--317, 2006. Google ScholarDigital Library
- D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In FOCS, pages 482--491, 2003. Google ScholarDigital Library
- V. King, S. Lewis, J. Saia, and M. Young. Choosing a random peer in chord. Algorithmica, 49(2):147--169, 2007. Google ScholarDigital Library
- B. Krishnamachari, D. Estrin, and S. B. Wicker. The impact of data aggregation in wireless sensor networks. In DEBS, pages 575--578, 2002. Google ScholarDigital Library
- P. Kyasanur, R. R. Choudhury, and I. Gupta. Smart gossip: An adaptive gossip-based broadcasting service for sensor networks. In MASS, pages 91--100, 2006.Google ScholarCross Ref
- S. Madden, M. J. Franklin, J. M. Hellerstein, and W. Hong. Tag: a tiny aggregation service for ad-hoc sensor networks. SIGOPS Oper. Syst. Rev., 36(SI):131--146, 2002. Google ScholarDigital Library
- M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005.Google ScholarDigital Library
- R. Morselli, B. Bhattacharjee, M. A. Marsh, and A. Srinivasan. Efficient lookup on unstructured topologies. In PODC, pages 77--86, 2005. Google ScholarDigital Library
- D. Mosk-Aoyama and D. Shah. Computing separable functions via gossip. In PODC, pages 113--122, 2006. Google ScholarDigital Library
- S. Nath, P. B. Gibbons, S. Seshan, and Z. R. Anderson. Synopsis diffusion for robust aggregation in sensor networks. In SenSys, pages 250--262, 2004. Google ScholarDigital Library
- A. Panconesi and A. Srinivasan. Randomized distributed edge coloring via an extension of the Chernoff-Hoeffding bounds. SIAM Journal on Computing, 26:350--368, 1997. Google ScholarDigital Library
- D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. Google ScholarDigital Library
- R. D. Pietro and P. Michiardi. Brief announcement: Gossip-based aggregate computation: computing faster with non address-oblivious schemes. In PODC, 2008, page 442. Extended version at http://www.eurecom.fr/ michiard/downloads/podc08_a_ext.pdf . Google ScholarDigital Library
- B. Pittel. On spreading a rumor. SIAM J. Appl. Math., 47(1):213--223, 1987. Google ScholarDigital Library
- A. I. T. Rowstron and P. Druschel. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Middleware, pages 329--350, 2001. Google ScholarDigital Library
- R. Sarkar, X. Zhu, and J. Gao. Hierarchical spatial gossip for multi-resolution representation in sensor netowrk. In IPSN, pages 420--429, 2007. Google ScholarDigital Library
- N. Shrivastava, C. Buragohain, D. Agrawal, and S. Suri. Medians and beyond: new aggregation techniques for sensor networks. In SenSys, pages 239--249, 2004. Google ScholarDigital Library
- I. Stoica, R. Morris, D. Karger, M. F. Kaashoek, and H. Balakrishnan. Chord: A scalable peer-to-peer lookup service for internet applications. In SIGCOMM, pages 149--160, 2001. Google ScholarDigital Library
- M. Zhong and K. Shen. Random walk based node sampling in self-organizing networks. SIGOPS Oper. Syst. Rev., 40(3):49--55, 2006. Google ScholarDigital Library
Index Terms
- Optimal gossip-based aggregate computation
Recommendations
Efficient gossip-based aggregate computation
PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsRecently, there has been a growing interest in gossip-based protocols that employ randomized communication to ensure robust information dissemination. In this paper, we present a novel gossip-based scheme using which all the nodes in an n-node overlay ...
Gossip-based aggregate computation: computing faster with non address-oblivious schemes
PODC '08: Proceedings of the twenty-seventh ACM symposium on Principles of distributed computingIn 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 ...
Cache-oblivious range reporting with optimal queries requires superlinear space
SCG '09: Proceedings of the twenty-fifth annual symposium on Computational geometryWe consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space required by any cache-oblivious data structure for these problems that achieves an optimal query bound of O(logBN + K/B) block ...
Comments