Applications such as airlines, telecommunications, banks, and real-time database will in the near future require 1000 or more transactions per second, where a transaction consists of 4-6 record accesses most of them through data structures. At these transaction rates and implied multiprocessing levels, classical concurrent data structure techniques may be too slow. This work seeks methods to eliminate the bottleneck of slow transaction rates. A variety of algorithmic ideas, including cooperative concurrent and wait-free techniques, will be evaluated to determine what features a concurrent data structure algorithm should possess to achieve high performance. The goal is to provide a rational method for choosing (or inventing): 1. algorithmic strategies (e.g. bottom-up link technique); 2. recovery strategies (e.g. operation logging as opposed to physical logging); and 3. tradeoffs between space and time, (e.g. the benefits of merge-at-half compared to merge-at-empty). Besides the direct benefit to high performance database management systems, this work will shed insight on the general area of concurrent and parallel computation.
