To access the full text documents, please follow this link:

HyperChromatic trees: a fine-grained approach to distributed algorithms on RedBlack trees
Messeguer Peypoch, Xavier; Valles Fuente, Borja
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
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 that 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.
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
RedBlack trees
Concurrent algorithms
Concurrent rebalancing
Safety and liveness proofs
Local rules

Show full item record

Related documents

Other documents of the same author

Gel Moreno, Bernat; Jenkinson, Andrew M; Jimenez, Rafael C; Messeguer Peypoch, Xavier; Hermjakob, Henning
Rozas Liras, Julio A.; Sánchez del Barrio, Juan Carlos; Messeguer Peypoch, Xavier; Rozas, Ricardo
Ruiz Orera, Jorge; Messeguer Peypoch, Xavier; Subirana Torrent, Juan A.; Albà Soler, M. Mar
Rozas, Julio; Sánchez del Barrio, Juan C.; Messeguer Peypoch, Xavier; Rozas, Ricardo
Blanco García, Enrique; Messeguer Peypoch, Xavier; Smith, T. F.; Guigó Serra, Roderic