A general technique for non-blocking trees

We describe a general technique for obtaining provably cor-rect, non-blocking implementations of a large class of tree data structures where pointers are directed from parents to children. Updates are permitted to modify any contiguous portion of the tree atomically. Our non-blocking algorithms make use of the LLX, SCX and VLX primitives, which are multi-word generalizations of the standard LL, SC and VL primitives and have been implemented from single-word CAS [10]. To illustrate our technique, we describe how it can be used in a fairly straightforward way to obtain a non-blocking implementation of a chromatic tree, which is a relaxed vari-ant of a red-black tree. The height of the tree at any time is O(c + log n), where n is the number of keys and c is the number of updates in progress. We provide an experimen-tal performance analysis which demonstrates that our Java implementation of a chromatic tree rivals, and often signifi-cantly outperforms, other leading concurrent dictionaries. Categories and Subject Descriptors E.1 [Data]: Data Structures—Distributed data structure