research-article

LH*_RS^P2P: a scalable distributed data structure for P2P environment

Authors:

Witold Litwin,

Hanafi Yakouben,

Thomas SchwarzAuthors Info & Claims

NOTERE '08: Proceedings of the 8th international conference on New technologies in distributed systems

Article No.: 1, Pages 1 - 6

https://doi.org/10.1145/1416729.1416731

Published: 23 June 2008 Publication History

Get Access

Abstract

LH*_RS^P2P is a Scalable Distributed Data Structure (SDDS) designed for P2P applications. It stores and processes data on SDDS peer nodes. Each node is both an SDDS client and, actually or potentially, an SDDS server with application or parity data. The scheme improves on LH*_RS. The basic difference is that now key-based queries require at most one forwarding message, instead of possibly two for LH*_RS. This property makes LH*_RS^P2P the fastest P2P or SDDS addressing scheme. The scan operation now also takes at most two rounds. LH*_RS^P2P parity management reuses the LH*_RS Reed Salomon erasure correction scheme to deal efficiently with churn. The file supports unavailability or withdrawal of up to any k ≥ 1 peers, where k is a parameter that can scale dynamically. We discuss the LH*_RS^P2P design, implementation issues and variants, as well as related work.

References

[1]

Crainiceanu A. Linga, P. Gehrke, J, & Shanmugasundaram, J. Querying Peer-to-Peer Networks Using P-Trees. 7th Intl. Workshop on the Web and Databases (WebDB 2004). Paris, June 2004.

Digital Library

Google Scholar

[2]

Bolosky W. J, Douceur, J. R and Howel, I J. The Farsite Project: A Retrospective. Operating System Review, April 2007, p. 17--26.

Digital Library

Google Scholar

[3]

Devine R. Design and Implementation of DDH: A Distributed Dynamic Hashing Algorithm, 4^th Intl. Found. of Data Organisation and Algorithms -- FODO, 1993.

Digital Library

Google Scholar

[4]

Litwin, W. Linear Hashing: A new tool for file and table addressing, VLDB-80, Montreal, 1980. Reprinted in Readings in Database Systems, M. Stonebreaker ed., 2^nd Edition, Morgan Kaufmann, 1995.

Digital Library

Google Scholar

[5]

Litwin, W. Neimat, M-A., Schneider, D. LH*: Linear Hashing for Distributed Files. ACM-SIGMOD Int. Conf. On Management of Data, 93.

Digital Library

Google Scholar

[6]

Litwin, W, Neimat, M-A., Schneider, D. LH*: A Scalable Distributed Data Structure. ACM-TODS, (Dec. 1996).

Digital Library

Google Scholar

[7]

Litwin, W., Neimat, M-A. High Availability LH* Schemes with Mirroring, Intl. Conf on Cooperating systems, Brussels, IEEE Press 1996.

Digital Library

Google Scholar

[8]

Litwin, W, Moussa R, Schwarz T. LH*rs- A Highly Available Distributed Data Storage. VLDB-04 Conference, Toronto, Canada, 2004.

Digital Library

Google Scholar

[9]

Litwin, W. Moussa R, Schwarz T. LH*rs- A Highly Available Scalable Distributed Data Structure. ACM-TODS, Sept 2005.

Digital Library

Google Scholar

[10]

Gribble S, Brewer E, Hellerstein J, M. & Culler D. Scalable, Distributed Data Structures for Internet Service Construction. OSDI 2000.

Digital Library

Google Scholar

[11]

Stoica I, Morris R, Karger D, Kaashoek F, Balakrishma. H. CHORD: A scalable Peer to Peer Lookup Service for Internet Application. SIGCOMM'O, 2001.

Digital Library

Google Scholar

Cited By

View all

Chabkinian JSchwarz Sj T(2016)Fast LH$$*$$źInternational Journal of Parallel Programming10.1007/s10766-015-0371-844:4(709-734)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s10766-015-0371-8
Grampone SLitwin WSj Schwarz T(2015)A Dependable, Scalable, Distributed, Virtual Data StructureProceedings of the ICA3PP International Workshops and Symposiums on Algorithms and Architectures for Parallel Processing - Volume 953210.1007/978-3-319-27161-3_66(724-735)Online publication date: 18-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-319-27161-3_66
Chabkinian JSchwarz T(2013)Fast LH*Proceedings of the 2013 25th International Symposium on Computer Architecture and High Performance Computing10.1109/SBAC-PAD.2013.15(57-64)Online publication date: 23-Oct-2013
https://dl.acm.org/doi/10.1109/SBAC-PAD.2013.15
Show More Cited By

Index Terms

LH*_RS^P2P: a scalable distributed data structure for P2P environment
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

Trustworthiness of Acquaintances in Peer-to-Peer(P2P) Overlay Networks
CISIS '10: Proceedings of the 2010 International Conference on Complex, Intelligent and Software Intensive Systems

Systems using peer-to-peer (P2P) overlay networks are getting a central position in information systems. P2P systems are in nature fully distributed, with no centralized coordinator and each peer is autonomous. Each peer has to obtain information on ...
LH * RSP 2 P : a fast and high churn resistant scalable distributed data structure for P2P systems

LH*<SUB align=right>RS<SUP align=right>P2P</SUP> is a new scalable distributed data structure (SDDS) for P2P applications. It deals with two major issues in P2P systems. One is efficient location of the peers with searched data ...
A Dynamic Hashing Approach to Supporting Load Balance in P2P Systems
ICDCSW '08: Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems Workshops

In a structured P2P system, peers maintain information about what resources neighbor peers offer. Chord is one of well-known structured P2P systems to efficiently support resource finding based on the hashing approach. However, in Chord, most of data ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

NOTERE '08: Proceedings of the 8th international conference on New technologies in distributed systems

June 2008

399 pages

ISBN:9781595939371

DOI:10.1145/1416729

Conference Chairs:
Djamal Benslimane
University of Lyon, France
,
Aris Ouksel
Northwestern University

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: 23 June 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Sixth Framework Programme

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
160
Total Downloads

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

Reflects downloads up to 30 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chabkinian JSchwarz Sj T(2016)Fast LH$$*$$źInternational Journal of Parallel Programming10.1007/s10766-015-0371-844:4(709-734)Online publication date: 1-Aug-2016
https://dl.acm.org/doi/10.1007/s10766-015-0371-8
Grampone SLitwin WSj Schwarz T(2015)A Dependable, Scalable, Distributed, Virtual Data StructureProceedings of the ICA3PP International Workshops and Symposiums on Algorithms and Architectures for Parallel Processing - Volume 953210.1007/978-3-319-27161-3_66(724-735)Online publication date: 18-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-319-27161-3_66
Chabkinian JSchwarz T(2013)Fast LH*Proceedings of the 2013 25th International Symposium on Computer Architecture and High Performance Computing10.1109/SBAC-PAD.2013.15(57-64)Online publication date: 23-Oct-2013
https://dl.acm.org/doi/10.1109/SBAC-PAD.2013.15
Yakouben HSoror S(2010)LH * RSP 2 P : a fast and high churn resistant scalable distributed data structure for P2P systemsInternational Journal of Internet Technology and Secured Transactions10.1504/IJITST.2010.0314702:1/2(5-31)Online publication date: 1-Feb-2010
https://dl.acm.org/doi/10.1504/IJITST.2010.031470
Tarkoma S(2010)ReferencesOverlay Networks10.1201/9781439813737-b(217-234)Online publication date: 9-Apr-2010
https://doi.org/10.1201/9781439813737-b

View Options

Login options

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

Cited By

Index Terms

Recommendations

Trustworthiness of Acquaintances in Peer-to-Peer(P2P) Overlay Networks

LH * RSP 2 P : a fast and high churn resistant scalable distributed data structure for P2P systems

A Dynamic Hashing Approach to Supporting Load Balance in P2P Systems