ACM SIGMOD Anthology ACM SIGMOD dblp.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, db/conf/sigmod/JohnsonK93.html},
  crossref  = {DBLP:conf/sigmod/93},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

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

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

Referenced by

  1. Mong-Li Lee, Masaru Kitsuregawa, Beng Chin Ooi, Kian-Lee Tan, Anirban Mondal: Towards Self-Tuning Data Placement in Parallel Database Systems. SIGMOD Conference 2000: 225-236
  2. Takahiro Hara, Kaname Harumoto, Masahiko Tsukamoto, Shojiro Nishio: Database Migration: A New Architecture for Transaction Processing in Broadband Networks. IEEE Trans. Knowl. Data Eng. 10(5): 839-854(1998)
  3. André Eickler, Alfons Kemper, Donald Kossmann: Finding Data in the Neighborhood. VLDB 1997: 336-345
  4. Vibby Gottemukkala, Edward Omiecinski, Umakishore Ramachandran: Relaxed Index Consistency for a Client-Server Database. ICDE 1996: 352-361
  5. Gerhard Weikum: Tutorial on Parallel Database Systems. ICDT 1995: 33-37
  6. Witold Litwin, Marie-Anne Neimat, Donovan A. Schneider: RP*: A Family of Order Preserving Scalable Distributed Data Structures. VLDB 1994: 342-353
  7. Radek Vingralek, Yuri Breitbart, Gerhard Weikum: Distributed File Organization with Scalable Cost/Performance. SIGMOD Conference 1994: 253-264
  8. Brigitte Kröll, Peter Widmayer: Distributing a Search Tree Among a Growing Number of Processors. SIGMOD Conference 1994: 265-276
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:40:15 2009