dblp.uni-trier.de www.dagstuhl.de www.uni-trier.de

Lazy Updates for Distributed Search Structure.

Theodore Johnson, Padmashree Krishna: Lazy Updates for Distributed Search Structure. SIGMOD Conference 1993: 337-346
@inproceedings{DBLP:conf/sigmod/JohnsonK93,
  author    = {Theodore Johnson and
               Padmashree Krishna},
  editor    = {Peter Buneman and
               Sushil Jajodia},
  title     = {Lazy Updates for Distributed Search Structure},
  booktitle = {Proceedings of the 1993 ACM SIGMOD International Conference on
               Management of Data, Washington, D.C., May 26-28, 1993},
  publisher = {ACM Press},
  year      = {1993},
  pages     = {337-346},
  ee        = {http://doi.acm.org/10.1145/170035.170085},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Very large database systems require distributed storage, which means that they need distributed search structures for fast and eficient access to the data. In this paper, we present an approach to maintaining distributed data structures that uses lazy updates, which take advantage of the semantics of the search structure operations to allow for scalable and low-overhead replication. Lazy updates can be used to design distributed search structures that support very high levels of concurrency. The alternatives to lazy update algorithms (eager updates) use synchronization to ensure consistency, while lazy update algorithms avoid blocking. Since lazy updates avoid the use of synchronization, they are much easier to implement than eager update algorithms. We demonstmte the application of lazy updates to the dB-tree, which is a distributed B+ tree that replicates its interior nodes for highly parallel access. We develop a correctness theory for lazy updates so that our algorithms can be applied to other distributed search structures.

Copyright © 1993 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.


ACM SIGMOD Anthology

Online Version (ACM WWW Account required): Full Text in PDF Format

CDROM Version: Load the CDROM "Volume 1 Issue 1, SIGMOD '93-'97" and ...

DVD Version: Load ACM SIGMOD Anthology DVD 1" and ...

Printed Edition

Peter Buneman, Sushil Jajodia (Eds.): Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data, Washington, D.C., May 26-28, 1993. ACM Press 1993 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML, SIGMOD Record 22(2), June 1993
Contents

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1086 KB]

References

[1]
Farokh B. Bastani, S. Sitharama Iyengar, I-Ling Yen: Concurrent Maintenance of Data Structures in a Distributed Environment. Comput. J. 31(2): 165-174(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[2]
Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[3]
...
[4]
Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[5]
...
[6]
...
[7]
Maurice Herlihy, Jeannette M. Wing: Linearizability: A Correctness Condition for Concurrent Objects. ACM Trans. Program. Lang. Syst. 12(3): 463-492(1990) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[8]
...
[9]
Theodore Johnson, Dennis Shasha: Utilization of B-trees with Inserts, Deletes and Modifies. PODS 1989: 235-246 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[10]
Theodore Johnson, Dennis Shasha: A Framework for the Performance Analysis of Concurrent B-tree Algorithms. PODS 1990: 273-287 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[11]
...
[12]
Rivka Ladin, Barbara Liskov, Liuba Shrira: Lazy Replication: Exploiting the Semantics of Distributed Services. PODC 1990: 43-57 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[13]
...
[14]
Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[15]
Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37 CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[16]
Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988) CiteSeerX Google scholar pubzone.org BibTeX bibliographical record in XML
[17]
...
[18]
...

Last update Tue Sep 18 00:25:09 2012 CET by the DBLP TeamThis material is Open Data Data released under the ODC-BY 1.0 license — See also our legal information page