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

research-article

LH*G: A High-Availability Scalable Distributed Data Structure By Record Grouping

Authors:

Tore RischAuthors Info & Claims

IEEE Transactions on Knowledge and Data Engineering, Volume 14, Issue 4

Pages 923 - 927

https://doi.org/10.1109/TKDE.2002.1019223

Published: 01 July 2002 Publication History

Abstract

LH*g is a high-availability extension of the LH* Scalable Distributed Data Structure. An LH*g file scales up with constant key search and insert performance, while surviving any single-site unavailability (failure). We achieve high-availability through a new principle of record grouping. A group is a logical structure of up to k records, where k is a file parameter. Every group contains a parity record allowing for the reconstruction of an unavailable member. The basic scheme may be generalized to support the unavailability of any number of sites, at the expense of storage and messaging. Other known high-availability schemes are static, or require more storage, or provide worse search performance.

References

[1]

G. Alvarez W. Burkhard and F. Cristian, “Tolerating Multiple-Failures in RAID Architecture with Optimal Storage and Uniform Declustering,” Proc. Int'l Symp. Computer Architecture (ISCA-97), 1997.

Digital Library

[2]

W. Bennour, et al. “Scalable Distributed Linear Hashing LH<sup>*</sup> <inf>LH</inf> Under Windows NT,” Proc. IEEE Fourth World Multiconf. Systems Cybernetics & Informatics and Information Systems Analysis & Synthesis, 2000.

[3]

D. Culler, “NOW: Towards Everyday Supercomputing on a Network of Workstations,” EECS technical reprt, UC Berkeley, 1994.

[4]

R. Devine, “Design and Implementation of DDH: Distributed Dynamic Hashing,” Proc. Int'l Conf. Foundations of Data Organizations (FODO-93), Oct. 1993.

Digital Library

[5]

J. Gray, “Super-Servers: Commodity Computer Clusters Pose a Software Challenge,” Microsoft, http:\\www.researchmicrosoft.com\, 1996.

[6]

D. Hsio and D. DeWitt, “Chained Declustering: A New Availability Strategy for Multiprocessor Database Machine,” Proc. Sixth Int'l IEEE Conf. Data Eng., 1990.

Digital Library

[7]

J. Hartman and J. Ousterhout, “The Zebra Striped Network File System,” ACM Trans. Computer Systems, vol. 13, no. 3, pp. 275-309, 1995.

Digital Library

[8]

S-O. Hvasshovd, et al. “A Continuously Available and Highly Scalable Transaction Server,” Proc. Fourth Int'l Workshop High Performance Transaction Systems, 1991.

[9]

J. Karlsson W. Litwin and T. Risch, “LH*lh: A Scalable High Performance Data Structure for Switched Multicomputers,” Proc. Int'l Conf. Extending Database Technology (EDBT-96), Mar. 1996.

Digital Library

[10]

D. Knuth, The Art of Computer Programming, Vol. 3, Sorting and Searching, second ed. Addison-Wesley, p. 780, 1998.

Digital Library

[11]

B. Kroll and P. Widmayer, “Distributing a Search Tree Among a Growing Number of Processors,” Proc. ACM-SIGMOD Int'l Conf. Management of Data, 1994.

Digital Library

[12]

J.-C. Laprie, “Dependable Computing and Fault Tolerance: Concepts and Terminology,” Proc. 15th Int'l Symp. Fault-Tolerant, pp. 2-11, 1985.

[13]

R. Lindberg, “A Java Implementation of a Highly Available Scalable and Distributed Data Structure LH*g,” master's thesis, LiTH-IDA-Ex-97/65, Univ. of Linkoping, p. 62, 1997.

[14]

W. Litwin J. Menon and T. Risch, “Design Issues For Scalable Availability LH* Schemes with Record Grouping,” Proc. Workshop Distributed Data and Structures (DIMACS), J. Menon, T. Risch, and T. Schwarz, eds., 1999.

Digital Library

[15]

W. Litwin M.-A. Neimat and D. Schneider, “LH*: Linear Hashing for Distributed Files,” Proc. ACM-SIGMOD Int'l Conf. Management of Data, 1993.

Digital Library

[16]

W. Litwin M.-A. Neimat and D. Schneider, “RP*: A Family of Order-Preserving Scalable Distributed Data Structures,” Proc. 20th Int'l Conf. Very Large Data Bases (VLDB), 1994.

Digital Library

[17]

W. Litwin M.-A. Neimat and D. Schneider, “LH*: A Scalable Distributed Data Structure,” ACM Trans. Database Systems (ACM-TODS), Dec. 1996.

Digital Library

[18]

W. Litwin and M.-A. Neimat, “k-RP<sup>*</sup> <inf>N</inf>: A High Performance Multi-Attribute Scalable Distributed Data Structure,” Proc. IEEE Int'l Conf. Parallel and Distributed Information Systems, 1996.

Digital Library

[19]

W. Litwin and M.-A. Neimat, “High-Availability LH* Schemes with Mirroring,” Proc. Int'l Conf. Cooperating Information Systems, June 1996.

Digital Library

[20]

W. Litwin M.-A. Neimat G. Levy S. Ndiaye and T. Seck, “LH<sup>*</sup> <inf>S</inf>: A High-Availability and High-Security Scalable Distributed Data Structure,” IEEE-Research Issues in Data Eng., (RIDE-97), 1997.

Digital Library

[21]

W. Litwin and T. Risch, “LH*g : A High-Availability Scalable Distributed Data Structure by Record Grouping,” research report, Univ. of Paris 9 and Univ. of Linkoping, Apr. 1997, http://ceria.dauphine.fr/.

Digital Library

[22]

W. Litwin and T. Schwarz, “LH<sup>*</sup> <inf>RS</inf>: A High-Availability Scalable Distributed Data Structure Using Reed Solomon Codes,” Proc. ACM-SIGMOD-2000 Int'l Conf. Management of Data, 2000.

Digital Library

[23]

D. Patterson G. Gibson and R.H. Katz, A Case for Redundant Arrays of Inexpensive Disks (RAID). ACM Special Interest Group on Management of Data, 1988.

Digital Library

[24]

M. Stonebraker and G. Schloss, “Distributed RAID—A New Multiple Copy Algorithm,” Proc. Sixth Int'l IEEE Conf. Data Eng., pp. 430-437, 1990.

Digital Library

[25]

A.S. Tanenbaum, Distributed Operating Systems. Prentice Hall, p. 601, 1995.

Digital Library

[26]

O. Torbjornsen, “Multi-Site Declustering Strategies for Very High Database Service Availabiity,” Thesis Norges Technical Hogskoule, IDT Report 1995.2, 1995.

[27]

S. Tung H. Zha and T. Kefe, “Concurrent Scalable Distributed Data Structures,” Proc. ISCA Int'l Conf. Parallel and Distributed Computing Systems, K. Yetongnon and S. Harini, eds., pp. 131-136, Sept. 1996.

[28]

R. Vingralek Y. Breitbart and G. Weikum, “Distributed File Organization with Scalable Cost/Performance,” Proc. ACM-SIGMOD Int'l Conf. Management of Data, 1994.

Digital Library

[29]

J. Wilkes, et al. “The HP AutoRAID Hierarchical Storage System,” ACM Trans. Computer Science, vol. 14, no. 1, 1996.

Digital Library

Cited By

Tanin EHarwood ASamet HNayar DNutanong S(2018)Building and Querying a P2P Virtual WorldGeoinformatica10.1007/s10707-005-4887-810:1(91-116)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10707-005-4887-8
Mense MScheideler CTeng S(2008)SPREADProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347206(1135-1144)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347206
Tanin EHarwood ASamet H(2007)Using a distributed quadtree index in peer-to-peer networksThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-005-0001-y16:2(165-178)Online publication date: 29-Apr-2007
https://dl.acm.org/doi/10.1007/s00778-005-0001-y
Show More Cited By

Index Terms

LH*G: A High-Availability Scalable Distributed Data Structure By Record Grouping
1. Computer systems organization
  1. Architectures
    1. Distributed architectures
    2. Parallel architectures
  2. Dependable and fault-tolerant systems and networks
2. Software and its engineering
  1. Software organization and properties
    1. Software system structures
      1. Distributed systems organizing principles

Recommendations

LH*RS: a high-availability scalable distributed data structure using Reed Solomon Codes

LH*_RS is a new high-availability Scalable Distributed Data Structure (SDDS). The data storage scheme and the search performance of LH*_RS are basically these of LH*. LH*_RS manages in addition the parity information to tolerate the unavailability of k ⪈ 1 ...
LH*_RS---a highly-available scalable distributed data structure

LH*_RS is a high-availability scalable distributed data structure (SDDS). An LH*_RS file is hash partitioned over the distributed RAM of a multicomputer, for example, a network of PCs, and supports the unavailability of any k ≥ 1 of its server nodes. The ...
Synchronous Byzantine quorum systems

Quorum systems have been used to implement many coordination problems in distributed systems such as mutual exclusion, data replication, distributed consensus, and commit protocols. Malkhi and Reiter recently proposed quorum systems that can tolerate ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Knowledge and Data Engineering

IEEE Transactions on Knowledge and Data Engineering Volume 14, Issue 4

July 2002

255 pages

ISSN:1041-4347

Issue’s Table of Contents

Copyright © Copyright © 2002 IEEE. All Rights Reserved.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 July 2002

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 17 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Tanin EHarwood ASamet HNayar DNutanong S(2018)Building and Querying a P2P Virtual WorldGeoinformatica10.1007/s10707-005-4887-810:1(91-116)Online publication date: 24-Dec-2018
https://dl.acm.org/doi/10.1007/s10707-005-4887-8
Mense MScheideler CTeng S(2008)SPREADProceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms10.5555/1347082.1347206(1135-1144)Online publication date: 20-Jan-2008
https://dl.acm.org/doi/10.5555/1347082.1347206
Tanin EHarwood ASamet H(2007)Using a distributed quadtree index in peer-to-peer networksThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-005-0001-y16:2(165-178)Online publication date: 29-Apr-2007
https://dl.acm.org/doi/10.1007/s00778-005-0001-y
Litwin WMoussa RSchwarz T(2005)LH*RS---a highly-available scalable distributed data structureACM Transactions on Database Systems (TODS)10.1145/1093382.109338630:3(769-811)Online publication date: 1-Sep-2005
https://dl.acm.org/doi/10.1145/1093382.1093386
Tanin EHarwood ASamet HDawes SHovy EDelcambre L(2004)Indexing distributed complex data for complex queriesProceedings of the 2004 annual national conference on Digital government research10.5555/1124191.1124254(1-10)Online publication date: 24-May-2004
https://dl.acm.org/doi/10.5555/1124191.1124254
Tanin EHarwood ASamet HNutanong STruong MCruz IPfoser D(2004)A serverless 3D worldProceedings of the 12th annual ACM international workshop on Geographic information systems10.1145/1032222.1032246(157-165)Online publication date: 12-Nov-2004
https://dl.acm.org/doi/10.1145/1032222.1032246

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents