Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Nonblocking algorithms for concurrent data structures guarantee that a data structure is always accessible. This is in contrast to blocking algorithms in which a slow or halted process can render part or all of the data structure inaccessible to other processes. This paper proposes a technique that can convert most existing lock-based blocking data structure algorithms into nonblocking algorithms with the same functionality. Our instruction-by-instruction transformation can be applied to any algorithm having the following properties: •Interprocess synchronization is established solely through the use of locks. •There is no possiblity of deadlock (e.g. because of a well-ordering among the lock requests). In contrast to a previous work, our transformation requires only a constant amount of overhead per operation and, in the absence of failures, it incurs no penalty in the amount of concurrency that was available in the original data structure. The techniques in this paper may obviate the need for a wholesale reinvention of techniques for nonblocking concurrent data structure algorithms.

REFERENCES

• BS77: Bayer, M. and Scholnick. Concurrency of Operations on B-Trees. Acta Informatica, 9:1-21, 1977.
• CBDW91: A. Colbrook, E.A. Brewer, C.N. Dellarocas, and W.E. Weihl. An algorithm for concurrent search trees.In Proceedzngs of the #Oth International Conference on Parallel Processing, pages III138-III141, 1991.
• Her88: Maurice P. Herlihy, Impossibility and universality results for wait-free synchronization, Proceedings of the seventh annual ACM Symposium on Principles of distributed computing, p.276-290, August 15-17, 1988, Toronto, Ontario, Canada [doi>10.1145/62546.62593]
• IBM83: IBM. IBM 370 Pmnc#ples of Operation, May 1983. Publication GA22-7000.
• JS90: Theodore Johnson , Dennis Shasha, A framework for the performance analysis of concurrent B-tree algorithms, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.273-287, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298580]
• KL80: H. T. Kung , Philip L. Lehman, Concurrent manipulation of binary search trees, ACM Transactions on Database Systems (TODS), v.5 n.3, p.354-382, Sept. 1980 [doi>10.1145/320613.320619]
• LS81: Philip L. Lehman , s. Bing Yao, Efficient locking for concurrent operations on B-trees, ACM Transactions on Database Systems (TODS), v.6 n.4, p.650-670, Dec. 1981 [doi>10.1145/319628.319663]
• PLJ91: Prakash, S., Y. H. Lee, and T. Johnson. A Non-Blocking Algorithm for Shared Queues Using Compare-and-Swap. In Internatzonal Conference on Parallel Processing, 1991.
• Plo89: S. A. Plotkin, Sticky bits and universality of consensus, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing, p.159-175, June 1989, Edmonton, Alberta, Canada [doi>10.1145/72981.72992]
• SC91: V. Srinivasan , Michael J. Carey, Performance of B-tree concurrency control algorithms, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.416-425, May 29-31, 1991, Denver, Colorado, United States
• SG88: Dennis Shasha , Nathan Goodman, Concurrent search structure algorithms, ACM Transactions on Database Systems (TODS), v.13 n.1, p.53-90, March 1988 [doi>10.1145/42201.42204]
• Sto90: Janice M. Stone, A simple and correct shared-queue algorithm using compare-and-swap, Proceedings of the 1990 conference on Supercomputing, p.495-504, October 1990, New York, New York, United States
• Ten81: R. D. Tennent, Principles of Programming Languages, Prentice Hall PTR, Upper Saddle River, NJ, 1981
• WW90: W.E. Weihl and P. Wang. Multi-version memory: Software cache management for concurrent B-trees. In Proceedsngs of the 2nd IEEE Sympossum on Parallel and Dsstmbuted Process,ng, pages 650-655, 1990.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Concurrency

General Terms:
Algorithms, Design