Robust aggregation in peer-to-peer database systems

ABSTRACT

Peer-to-peer database systems (P2PDBs) aim at providing database services with node autonomy, high availability and loose coupling between participating nodes by building the DBMS on top of a peer-to-peer network. A key feature of current peer-to-peer systems is resilience to churn in the overlay network layer. A major challenge in P2PDBs is to provide similar robustness in the data and query processing layer. In this paper we in particular describe how aggregation queries in P2PDBs can be handled in order to reduce the impact of churn on accuracy of results. We perform a formal study of data loss and accuracy of such queries, and describe new approaches that increase the accuracy of aggregation queries in P2PDBs under churn.

REFERENCES

• 1: Benjamin Arai , Gautam Das , Dimitrios Gunopulos , Vana Kalogeraki, Approximating Aggregation Queries in Peer-to-Peer Networks, Proceedings of the 22nd International Conference on Data Engineering, p.42, April 03-07, 2006 [doi>10.1109/ICDE.2006.23]
• 2: Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007627]
• 3: Alan Demers , Johannes Gehrke , Rajmohan Rajaraman , Niki Trigoni , Yong Yao, The Cougar Project: a work-in-progress report, ACM SIGMOD Record, v.32 n.4, December 2003 [doi>10.1145/959060.959070]
• 4: The Piazza Peer Data Management System, IEEE Transactions on Knowledge and Data Engineering, v.16 n.7, p.787-798, July 2004 [doi>10.1109/TKDE.2004.1318562]
• 5: R. Huebsch, B. N. Chun, J. M. Hellerstein, B. T. Loo, P. Maniatis, T. Roscoe, S. Shenker, I. Stoica, and A. R. Yumerefendi. The architecture of PIER: an internet-scale query processor. In Proceedings of CIDR, pages 28--43, 2005.
• 6: Ryan Huebsch , Joseph M. Hellerstein , Nick Lanham , Boon Thau Loo , Scott Shenker , Ion Stoica, Querying the internet with PIER, Proceedings of the 29th international conference on Very large data bases, p.321-332, September 09-12, 2003, Berlin, Germany
• 7: Ji Li , Karen Sollins , Dah-Yoh Lim, Implementing aggregation and broadcast over Distributed Hash Tables, ACM SIGCOMM Computer Communication Review, v.35 n.1, p.81-92, January 2005 [doi>10.1145/1052812.1052813]
• 8: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for ad-hoc sensor networks, ACM SIGOPS Operating Systems Review, v.36 n.SI, Winter 2002 [doi>10.1145/844128.844142]
• 9: W. S. Ng, B. C. Ooi, K.-L. Tan, and A. Zhou. PeerDB: A P2P-based system for distributed data sharing. In Proceedings of ICDE'2003, 2003.
• 10: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 11: Robbert Van Renesse , Kenneth P. Birman , Werner Vogels, Astrolabe: A robust and scalable technology for distributed system monitoring, management, and data mining, ACM Transactions on Computer Systems (TOCS), v.21 n.2, p.164-206, May 2003 [doi>10.1145/762483.762485]
• 12: Antony I. T. Rowstron , Peter Druschel, Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems, Proceedings of the IFIP/ACM International Conference on Distributed Systems Platforms Heidelberg, p.329-350, November 12-16, 2001
• 13: Sankardas Roy , Sanjeev Setia , Sushil Jajodia, Attack-resilient hierarchical data aggregation in sensor networks, Proceedings of the fourth ACM workshop on Security of ad hoc and sensor networks, October 30-30, 2006, Alexandria, Virginia, USA [doi>10.1145/1180345.1180355]
• 14: N. Ryeng and K. Nørvåg. Accuracy of aggregation in peer-to-peer DBMSs. In Proceedings of DBISP2P'2007, 2007.
• 15: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 16: P. Valduriez and E. Pacitti. Data management in large-scale P2P systems. In Proceedings of VECPAR'2004, 2004.
• 17: Praveen Yalagandula , Mike Dahlin, A scalable distributed information management system, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Algorithms, Performance, Reliability

Keywords:
aggregation, distributed querying, peer-to-peer systems