Título:
|
Height-relaxed AVL rebalancing: a unified, fine-grained approach to concurrent dictionaries
|
Autor/a:
|
Bouge, L; Gabarró Vallès, Joaquim; Messeguer Peypoch, Xavier; Schabanel, N
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació |
Abstract:
|
We show that this problem can be studied through the
self-reorganization of distributed systems of nodes controlled by
local evolution rules in the line of the approach of Dijkstra and
Scholten. This yields a much simpler algorithm that the ones
previously known. Based on the basic rebalancing framework, we describe
algorithms to manage concurrent insertion and deletion of keys.
Finally, this approach is used to emulate other well known
concurrent AVL algorithms.
As a by-product, this solves in a very general setting an old
question raised by H.T. Kung and P.L. Lehman: where should rotations
take place to rebalance arbitrary search trees? |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica -Search trees -Distributed systems -Concurrent algorithms -Concurrent insertions and deletions -Concurrent generalized rotations -Safety and liveness proofs -Emulation |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Informe |
Compartir:
|
|