- Relaxed Balance for Search Trees with Local Rebalancing.
- Kim S. Larsen, Thomas Ottmann, and Eljas Soisalon-Soininen.
In 5th Annual European Symposium on Algorithms (ESA), volume 1284 of Lecture Notes in Computer Science, pages 350-363. Springer, 1997.
Search trees with relaxed balance were introduced
with the aim of facilitating fast updating on shared-memory
asynchronous parallel architectures.
To obtain this, rebalancing has been uncoupled from the updating,
so extensive locking in connection with updates is avoided.
Rebalancing is taken care of by background processes, which do only
a constant amount of work at a time before they release locks. Thus,
the rebalancing and the associated locks are very localized in time
as well as in space. In particular, there is no exclusive locking of
whole paths. This means
that the amount of parallelism possible is not limited by the
height of the tree.
Search trees with relaxed balance have been obtained by
adapting standard sequential search trees to this new paradigm;
clearly using similar techniques in each case, but no
general result has been obtained.
We show how any search
tree with local bottom-up rebalancing can be used in a
relaxed variant preserving the complexity of the rebalancing
from the sequential case.
Additionally, we single out the one
high level locking mechanism that a parallel implementation must
provide in order to guarantee consistency.
- Link to the publication at the publisher's site - subscription may be required.
Text required by the publisher (if any):
The final publication is available at link.springer.com.
Link to the journal version containing all the material and proofs, some of which are usually omitted in the conference version due to space constraints.
Other publications by the author.