HyperChromatic trees: a fine-grained approach to distributed algorithms on RedBlack trees
Xavier Messeguer, Borja Valles Fuente · 1998
. We introduce a relaxed version of RedBlack trees. As concurrent algorithms on balanced search trees are nowadays based on local rules, we propose a set of fine-grained local rules that take more advantage of concurrency than previous approaches. Based on them we design a rebalancing concurrent algorithm and prove its correctness. Finally we sketch how to complete this algorithm to include concurrent insertions and deletions. Keywords: Concurrent algorithms, RedBlack trees, Concurrent rebalancing, Safety and liveness proofs, Local rules. 1 Motivation RedBlack trees are balanced search trees that have been recognized as an important data structure to deal with Dictionaries and Data Bases [CLR90]. Our aim is to deal with RedBlack trees in a concurrent environment. In this section we survey the previous approaches to this problem and outline our contributions. In a concurrent approach, algorithms are designed for a shared-memory asynchronous parallel architecture. The first ones were d...