Concurrent Search Structure Algorithms.

@article{DBLP:journals/tods/ShashaG88,
  author    = {Dennis Shasha and
               Nathan Goodman},
  title     = {Concurrent Search Structure Algorithms},
  journal   = {ACM Trans. Database Syst.},
  volume    = {13},
  number    = {1},
  year      = {1988},
  pages     = {53-90},
  ee        = {http://doi.acm.org/10.1145/42201.42204, db/journals/tods/ShashaG88.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

Copyright © 1988 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.

Joint ACM SIGMOD / IEEE Computer Society Anthology

• 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/An3-1 or /cdrom

• 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/aDVD2 or /dvd

References

[1]

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974, ISBN 0-201-00029-6
BibTeX

[2]

James E. Allchin, Martin S. McKendry: Synchronization and Recovery of Actions. PODC 1983: 31-44 BibTeX

[3]

Catriel Beeri, Philip A. Bernstein, Nathan Goodman: A Concurrency Control Theory for Nested Transactions. PODC 1983: 45-62 BibTeX

[4]

Jon Louis Bentley, Jerome H. Friedman: Data Structures for Range Searching. ACM Comput. Surv. 11(4): 397-409(1979) BibTeX

[5]

Philip A. Bernstein, Nathan Goodman: Concurrency Control in Distributed Database Systems. ACM Comput. Surv. 13(2): 185-221(1981) BibTeX

[6]

Philip A. Bernstein, Nathan Goodman, Ming-Yee Lai: Two Part Proof Schema for Database Concurrency Control. Berkeley Workshop 1981: 71-84 BibTeX

[7]

Rudolf Bayer, Mario Schkolnick: Concurrency of Operations on B-Trees. Acta Inf. 9: 1-21(1977) BibTeX

[8]

...

[9]

Douglas Comer: The Ubiquitous B-Tree. ACM Comput. Surv. 11(2): 121-137(1979) BibTeX

[10]

Carla Schlatter Ellis: Concurrent Search and Insertion in 2-3 Trees. Acta Inf. 14: 63-86,(1980) BibTeX

[11]

Carla Schlatter Ellis: Extendible Hashing for Concurrent Operations and Distributed Data. PODS 1983: 106-116 BibTeX

[12]

Carla Schlatter Ellis: Concurrency and Linear Hashing. PODS 1985: 1-7 BibTeX

[13]

Kapali P. Eswaran, Jim Gray, Raymond A. Lorie, Irving L. Traiger: The Notions of Consistency and Predicate Locks in a Database System. Commun. ACM 19(11): 624-633(1976) BibTeX

[14]

Ray Ford, Jim Calhoun: Concurrency Control Mechanisms and the Serializability of Concurrent Tree Algorithms. PODS 1984: 51-60 BibTeX

[15]

Hector Garcia-Molina: Using Semantic Knowledge for Transaction Processing in Distributed Database. ACM Trans. Database Syst. 8(2): 186-213(1983) BibTeX

[16]

James R. Goodman, Carlo H. Séquin: Hypertree: A Multiprocessor Interconnection Topology. IEEE Trans. Computers 30(12): 923-933(1981) BibTeX

[17]

Nathan Goodman, Dennis Shasha: Semantically-based Concurrency Control for Search Structures. PODS 1985: 8-19 BibTeX

[18]

Allan Gottlieb, Ralph Grishman, Clyde P. Kruskal, Kevin P. McAuliffe, Larry Rudolph, Marc Snir: The NYU Ultracomputer - Designing an MIMD Shared Memory Parallel Computer. IEEE Trans. Computers 32(2): 175-189(1983) BibTeX

[19]

Leonidas J. Guibas, Robert Sedgewick: A Dichromatic Framework for Balanced Trees. FOCS 1978: 8-21 BibTeX

[20]

...

[21]

H. T. Kung, Philip L. Lehman: Concurrent Manipulation of Binary Search Trees. ACM Trans. Database Syst. 5(3): 354-382(1980) BibTeX

[22]

H. T. Kung, Christos H. Papadimitriou: An Optimality Theory of Concurrency Control for Databases. Acta Inf. 19: 1-11(1983) BibTeX

[23]

Zvi M. Kedem, Abraham Silberschatz: Locking Protocols: From Exclusive to Shared Locks. J. ACM 30(4): 787-804(1983) BibTeX

[24]

Yat-Sang Kwong, Derick Wood: A New Method for Concurrency in B-Trees. IEEE Trans. Software Eng. 8(3): 211-222(1982) BibTeX

[25]

Vladimir Lanin, Dennis Shasha: A Symmetric Concurrent B-Tree Algorithm. FJCC 1986: 380-389 BibTeX

[26]

Philip L. Lehman, S. Bing Yao: Efficient Locking for Concurrent Operations on B-Trees. ACM Trans. Database Syst. 6(4): 650-670(1981) BibTeX

[27]

Barbara Liskov, Robert Scheifler: Guardians and Actions: Linguistic Support for Robust, Distributed Programs. POPL 1982: 7-19 BibTeX

[28]

David B. Lomet: Bounded Index Exponential Hashing. ACM Trans. Database Syst. 8(1): 136-165(1983) BibTeX

[29]

Udi Manber, Richard E. Ladner: Concurrency Control in a Dynamic Search Structure. PODS 1982: 268-282 BibTeX

[30]

...

[31]

Yehudit Mond, Yoav Raz: Concurrency Control in B+-Trees Databases Using Preparatory Operations. VLDB 1985: 331-334 BibTeX

[32]

Christos H. Papadimitriou: The serializability of concurrent database updates. J. ACM 26(4): 631-653(1979) BibTeX

[33]

...

[34]

Yehoshua Sagiv: Concurrent Operations on B-Trees with Overtaking. PODS 1985: 28-37 BibTeX

[35]

Behrokh Samadi: B-Trees in a System with Multiple Users. Inf. Process. Lett. 5(4): 107-112(1976) BibTeX

[36]

Gunter Schlageter: Process Synchronization in Database Systems. ACM Trans. Database Syst. 3(3): 248-271(1978) BibTeX

[37]

...

[38]

...

[39]

Dennis Shasha: What Good are Concurrent Search Structure Algorithms for databases Anyway? IEEE Database Eng. Bull. 8(2): 84-90(1985) BibTeX

[40]

Alexander Tuzhilin, Paul G. Spirakis: A Semantic Approach to Correctness of Concurrent Transaction Executions. PODS 1985: 85-95 BibTeX

[41]

William E. Weihl: Data-dependent Concurrency Control and Recovery (Extended Abstract). PODC 1983: 63-75 BibTeX

[42]

...

[43]

Gerhard Weikum: A Theoretical Foundation of Multi-Level Concurrency Control. PODS 1986: 31-43 BibTeX