Title:
|
HyperChromatic trees: a fine-grained approach to distributed algorithms on RedBlack trees
|
Author:
|
Messeguer Peypoch, Xavier; Valles Fuente, Borja
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
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. |
Subject(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -RedBlack trees -Concurrent algorithms -Concurrent rebalancing -Safety and liveness proofs -Local rules |
Rights:
|
|
Document type:
|
Article - Published version Report |
Share:
|
|