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 ...

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the CD and click on the path of your mount point:
/Anthology/smod9397 or /cdrom

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

Windows: Click the letter of your CD drive
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Mac: Click here
UNIX/LINUX: mount the DVD and click on the path of your mount point:
/Anthology/aDVD1 or /dvd

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

, 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)
[2]: Philip A. Bernstein, Vassos Hadzilacos, Nathan Goodman: Concurrency Control and Recovery in Database Systems. Addison-Wesley 1987, ISBN 0-201-10715-5
Contents
[3]: ...
[4]: Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979)
[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)
[8]: ...
[9]: Theodore Johnson, Dennis Shasha: Utilization of B-trees with Inserts, Deletes and Modifies. PODS 1989: 235-246
[10]: Theodore Johnson, Dennis Shasha: A Framework for the Performance Analysis of Concurrent B-tree Algorithms. PODS 1990: 273-287
[11]: ...
[12]: Rivka Ladin, Barbara Liskov, Liuba Shrira: Lazy Replication: Exploiting the Semantics of Distributed Services. PODC 1990: 43-57
[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)
[15]: Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37
[16]: Dennis Shasha, Nathan Goodman: Concurrent Search Structure Algorithms. ACM Trans. Database Syst. 13(1): 53-90(1988)
[17]: ...
[18]: ...

Last update Tue Sep 18 00:25:09 2012 CET by the DBLP Team —

Data released under the ODC-BY 1.0 license — See also our legal information page