We present a linearizable, non-blocking @math -ary search tree ( @math -ST) that supports fast searches and range queries. Our algorithm uses single-word compare-and-swap (CAS) operations, and tolerates any number of crash failures. Performance experiments show that, for workloads containing small range queries, our @math -ST significantly outperforms other algorithms which support these operations, and rivals the performance of a leading concurrent skip-list, which provides range queries that cannot always be linearized.
We introduce a generalization of the atomic snapshot object, which we call the partial snapshot object. This object stores a vector of values. Processes may write components of the vector individually or atomically read any subset of the components. We investigate implementations of the latter partial scan operation that are more efficient than the complete scans of traditional snapshot objects. We present an algorithm that is based on a new implementation of the active set abstraction, which may be of independent interest. This paper introduces a general formulation of atomic snapshot memory , a sharedmemory partitioned into words written( updated ) by individual processes, orinstantaneously read ( scanned ) in itsentirety. This paper presents three wait-free implementations of atomicsnapshot memory. The first implementation in this paper uses unbounded(integer) fields in these registers, and is particularly easy tounderstand. The second implementation uses bounded registers. Itscorrectness proof follows the ideas of the unbounded implementation.Both constructions implement a single-writer snapshot memory, in whicheach word may be updated by only one process, from single-writer, n -reader registers. The thirdalgorithm implements a multi-writer snapshot memory from atomic n -writer, n -reader registers, again echoing keyideas from the earlier constructions. All operations requireT( n 2 ) readsand writes to the component shared registers in the worst case. — Authors' Abstract