Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/84042

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
info:eu-repo/semantics/publishedVersion
Informe
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

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