More Web Proxy on the site http://driver.im/

research-article

Load Balancing and Range Queries in P2P Systems Using P-Ring

Authors:

Adina Crainiceanu,

Ashwin Machanavajjhala,

Johannes Gehrke,

Jayavel ShanmugasundaramAuthors Info & Claims

ACM Transactions on Internet Technology (TOIT), Volume 10, Issue 4

Article No.: 16, Pages 1 - 30

https://doi.org/10.1145/1944339.1944343

Published: 01 March 2011 Publication History

Abstract

In peer-to-peer (P2P) systems, computers from around the globe share data and can participate in distributed computation. P2P became famous, and infamous, due to file-sharing systems like Napster. However, the scalability and robustness of these systems make them appealing to a wide range of applications.

This article introduces P-Ring, a new peer-to-peer index structure. P-Ring is fully distributed, fault tolerant, and provides load balancing and logarithmic search performance while supporting both equality and range queries. Our theoretical analysis as well as experimental results, obtained both in a simulated environment and on PlanetLab, show the performance of our system.

References

[1]

Aberer, K. 2001. P-Grid: A self-organizing access structure for p2p information systems. In Proceedings of the IFCIS Conference on Cooperative Information Systems (CoopIS).

Digital Library

[2]

Aspnes, J. and Shah, G. 2003. Skip graphs. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA).

Digital Library

[3]

Bharambe, A. R., Agrawal, M., and Seshan, S. 2004. Mercury: Supporting scalable multi-attribute range queries. SIGCOMM Comput. Comm. Rev. 34, 4.

Digital Library

[4]

Cai, M., Frank, M., Chen, J., and Szekely, P. 2003. Maan: A multi-attribute addressable network for grid information services. In Proceedings of the 4th International Workshop on Grid Computing.

Digital Library

[5]

Crainiceanu, A., Linga, P., Gehrke, J., and Shanmugasundaram, J. 2004a. Querying peer-to-peer networks using p-trees. In Proceedings of the International Workshop on Web and Databases (WebDB).

Digital Library

[6]

Crainiceanu, A., Linga, P., Machanavajjhala, A., Gehrke, J., and Shanmugasundaram, J. 2004b. An indexing framework for peer-to-peer systems. In Proceedings of the World Wide Web Conference (WWW) (poster).

[7]

Crainiceanu, A., Linga, P., Machanavajjhala, A., Gehrke, J., and Shanmugasundaram, J. 2007. P-Ring: An efficient and robust p2p range index structure. In Proceedings of the ACM SIGMOD International Conference on Management of Data.

Digital Library

[8]

Dabek, F., Kaas Hoek, M. F., Karger, D., Morris, R., and Stoica, I. 2001. Wide-Area cooperative storage with CFS. In Proceedings of the SIGOPS Symposium on Operating Systems Principles (SOSP).

Digital Library

[9]

Daskos, A., Ghandeharizadeh, S., and An, X. 2003. Peper: A distributed range addressing space for p2p systems. In Proceedings of the International Workshop on Databases, Information Systems and Peer-to-Peer Computing (DBISP2P).

[10]

Datta, A., Hauswirth, M., John, R., Schmidt, R., and Aberer, K. 2005. Range-Queries in trie-structured overlays. In Proceedings of the P2P Computing Conference.

Digital Library

[11]

Ganesan, P., Bawa, M., and Garcia-Molina, H. 2004. Online balancing of range-partitioned data with applications to peer-to-peer systems. In Proceedings of the International Conference on Very Large Databases (VLDB).

Digital Library

[12]

Gupta, A., Agrawal, D., and El Abbadi, A. 2003. Approximate range selection queries in peer-to-peer systems. In Proceedings of the Conference on Innovative Data Systems Research (CIDR).

[13]

Harvey, N., Jones, M., Saroiu, S., Theimer, M., and Wolman, A. 2003. Skipnet: A scalable overlay network with practical locality properties. In Proceedings of the USENIX Symposium on Internet Technologies and Systems (USITS).

Digital Library

[14]

Jagadish, H., Ooi, B. C., and Vu, Q. H. 2005. Baton: A balanced tree structure for peer-to-peer networks. In Proceedings of the International Conference on Very Large Databases (VLDB).

Digital Library

[15]

Jagadish, H., Ooi, B. C., Tan, K.-L., Vu, Q. H., and Zhang, R. 2006. Speeding up search in peer-to-peer networks with a multi-way tree structure. In Proceedings of the ACM SIGMOD International Conference on Management of Data.

Digital Library

[16]

JBI. 2011. http://www.rl.af.mil/programs/jbi/.

[17]

Lagoze, C. and de Sompel, H. V. 2001. The open archive initiative: Building a low-barrier interoperability framework. In Proceedings of the ACM/IEEE-CS Joint Conference on Digital Libraries (JCDL).

Digital Library

[18]

Li, J., Stribling, J., Morris, R., Kaashoek, M. F., and Gil, T. M. 2005. A performance vs. cost framework for evaluating dht design tradeoffs under churn. In Proceedings of the Annual Joint Conference of the IEEE Computer and Communications Societies (InfoCom).

[19]

Linga, P., Crainiceanu, A., Gehrke, J., and Shanmugasundaram, J. 2005. Guaranteeing correctness and availability in p2p range indices. In Proceedings of the ACM SIGMOD International Conference on Management of Data.

Digital Library

[20]

Litwin, W., Neimat, M.-A., and Schneider, D. A. 1993. Lh* - Linear hashing for distributed files. In Proceedings of the ACM SIGMOD International Conference on Management of Data.

Digital Library

[21]

Litwin, W., Neimat, M.-A., and Schneider, D. A. 1994. Rp*: A family of order preserving scalable distributed data structures. In Proceedings of the International Conference on Very Large Databases (VLDB).

Digital Library

[22]

Lomet, D. B. 1996. Replicated indexes for distributed data. In Proceedings of the International Conference on Parallel and Distributed Information Systems (PDIS).

Digital Library

[23]

Planet Lab. 2011. Planet Lab homepage. www.planet-lab.org.

[24]

Ramakrishnan, R. and Gehrke, J. 2003. Database Management Systems. McGraw Hill.

Digital Library

[25]

Ratnasamy, S., Francis, P., Handley, M., Karp, R., and Shenker, S. 2001. A scalable content-addressable network. In Proceedings of the ACM SIGCOMM International Conference on Management of Data.

Digital Library

[26]

Rhea, S., Geels, D., Roscoe, T., and Kubiatowicz, J. 2004. Handling churn in a dht. In Proceedings of the USENIX Annual Tech Conference.

Digital Library

[27]

Rowstron, A. and Druschel, P. 2001. Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems. In Proceedings of the International ACM/IFIP/USENIX Middleware Conference (Middleware).

Digital Library

[28]

Sahin, O. D., Gupta, A., Agrawal, D., and El Abbadi, A. 2004. A p2p framework for caching range queries. In Proceedings of the International Conference on Data Engineering (ICDE).

Digital Library

[29]

Stoica, I., Morris, R., Karger, D., Frans Kaas Hoek, M., and Balakrishnan, H. 2001. Chord: A scalable peer-to-peer lookup service for internet applications. In Proceedings of the ACM SIGCOMM Conference.

Digital Library

[30]

Zhao, B. Y., Kubiatowicz, J., and Joseph, A. 2001. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Tech. rep., University of California Berkeley.

Digital Library

Cited By

Sioutas SSourla ETsichlas KVonitsanos GZaroliagis C(2022)A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical InfrastructuresAlgorithms10.3390/a1503009615:3(96)Online publication date: 18-Mar-2022
https://doi.org/10.3390/a15030096
Arulprakash ABaalamurugan KDhanaraj RSampath Kumar KGupta PRehman S(2022)Aggregation Technique Using Dynamic Cross-Propagation Clustering Algorithm in Wireless Body Sensor NetworksWireless Communications & Mobile Computing10.1155/2022/61025842022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/6102584
Pundkar SKarmakar SMishra SSingh SVrind T(2022)Energy Aware Dynamic Load Balancer for Embedded Multi-core Systems2022 35th International Conference on VLSI Design and 2022 21st International Conference on Embedded Systems (VLSID)10.1109/VLSID2022.2022.00023(56-61)Online publication date: Feb-2022
https://doi.org/10.1109/VLSID2022.2022.00023
Show More Cited By

Index Terms

Load Balancing and Range Queries in P2P Systems Using P-Ring
1. Information systems
  1. Data management systems
    1. Data structures
      1. Data access methods
    2. Database management system engines
      1. Parallel and distributed DBMSs

Recommendations

P-ring: an efficient and robust P2P range index structure
SIGMOD '07: Proceedings of the 2007 ACM SIGMOD international conference on Management of data

Peer-to-peer systems have emerged as a robust, scalable and decentralized way to share and publish data. In this paper, we propose P-Ring, a new P2P index structure that supports both equality and range queries. P-Ring is fault-tolerant, provides ...
Randomized load balancing strategies with churn resilience in peer-to-peer networks

The objective of load balancing in peer-to-peer (P2P) networks is to balance the workload of peer nodes in proportion to their capacity so as to eliminate performance bottlenecks. It is challenging because of the dynamic nature in overlay networks, the ...
Load balancing for structured P2P networks using the advanced finger selection algorithm (AFSA)
SAC '10: Proceedings of the 2010 ACM Symposium on Applied Computing

Structured Peer-to-Peer (P2P) networks, such as networks based on Distributed Hash Tables (DHTs), can be enhanced by using load balancing mechanisms. Current load balancing mechanisms are either trying to achieve even distribution of objects among nodes,...

Reviews

Reviewer: Todor Todorov

P-Ring is a new peer-to-peer (P2P) index structure. This paper introduces and describes this fully distributed, fault-tolerant structure that provides load balancing and logarithmic search performance while supporting both equality and range queries. The authors describe the model and architecture in detail, and present pseudocode algorithms. They also document the testing results and performance analysis. The authors conclude that "P-Ring outperforms [most of the] existing index structures[, and ...] that it maintains its excellent search performance with low maintenance cost in a dynamic P2P system."? I recommend this paper to anyone interested in P2P systems and their application. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Internet Technology

ACM Transactions on Internet Technology Volume 10, Issue 4

March 2011

120 pages

ISSN:1533-5399

EISSN:1557-6051

DOI:10.1145/1944339

Issue’s Table of Contents

Copyright © 2011 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 March 2011

Accepted: 01 February 2011

Revised: 01 October 2010

Received: 01 January 2010

Published in TOIT Volume 10, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
578
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)1

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sioutas SSourla ETsichlas KVonitsanos GZaroliagis C(2022)A Dynamic Distributed Deterministic Load-Balancer for Decentralized Hierarchical InfrastructuresAlgorithms10.3390/a1503009615:3(96)Online publication date: 18-Mar-2022
https://doi.org/10.3390/a15030096
Arulprakash ABaalamurugan KDhanaraj RSampath Kumar KGupta PRehman S(2022)Aggregation Technique Using Dynamic Cross-Propagation Clustering Algorithm in Wireless Body Sensor NetworksWireless Communications & Mobile Computing10.1155/2022/61025842022Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1155/2022/6102584
Pundkar SKarmakar SMishra SSingh SVrind T(2022)Energy Aware Dynamic Load Balancer for Embedded Multi-core Systems2022 35th International Conference on VLSI Design and 2022 21st International Conference on Embedded Systems (VLSID)10.1109/VLSID2022.2022.00023(56-61)Online publication date: Feb-2022
https://doi.org/10.1109/VLSID2022.2022.00023
Djellabi BYounis MAmad M(2020)Effective peer-to-peer design for supporting range query in Internet of Things applicationsComputer Communications10.1016/j.comcom.2019.12.017150:C(506-518)Online publication date: 15-Jan-2020
https://dl.acm.org/doi/10.1016/j.comcom.2019.12.017
Sioutas SVonitsanos GZacharatos NZaroliagis C(2019)Scalable and Hierarchical Distributed Data Structures for Efficient Big Data ManagementAlgorithmic Aspects of Cloud Computing10.1007/978-3-030-58628-7_8(122-160)Online publication date: 10-Sep-2019
https://dl.acm.org/doi/10.1007/978-3-030-58628-7_8
Shao XJibiki MTeranishi YNishinaga N(2018)An efficient load-balancing mechanism for heterogeneous range-queriable cloud storageFuture Generation Computer Systems10.1016/j.future.2017.07.05378:P3(920-930)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1016/j.future.2017.07.053
Takeda AOide TTakahashi ASuganuma T(2015)Efficient Dynamic Load Balancing for Structured P2P NetworkProceedings of the 2015 18th International Conference on Network-Based Information Systems10.1109/NBiS.2015.66(432-437)Online publication date: 2-Sep-2015
https://dl.acm.org/doi/10.1109/NBiS.2015.66
Shao XJibiki MTeranishi YNishinaga N(2015)Effective Load Balancing Mechanism for Heterogeneous Range Queriable Cloud StorageProceedings of the 2015 IEEE 7th International Conference on Cloud Computing Technology and Science (CloudCom)10.1109/CloudCom.2015.55(405-412)Online publication date: 30-Nov-2015
https://dl.acm.org/doi/10.1109/CloudCom.2015.55
Singh RChakraborty SKarmakar S(2015)Concurrent deterministic 1–2 skip list in distributed message passing systemsInternational Journal of Parallel, Emergent and Distributed Systems10.1080/17445760.2013.87663730:2(135-174)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1080/17445760.2013.876637
Sioutas SSourla ETsichlas KZaroliagis C(2015)D 3-Tree: A Dynamic Deterministic Decentralized StructureAlgorithms - ESA 201510.1007/978-3-662-48350-3_82(989-1000)Online publication date: 12-Nov-2015
https://doi.org/10.1007/978-3-662-48350-3_82
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents