Concurrent Maintenance of Skip Lists
Concurrent Maintenance of Skip Lists
Loading...
Files
Publication or External Link
Date
1998-10-15
Authors
Pugh, William
Advisor
Citation
DRUM DOI
Abstract
This papers describes a new approach to providing
efficient concurrent access to a dynamic search structure.
Previous approaches have attempted to solve this problem using
search trees (either balanced or unbalanced). We describe
methods for performing concurrent access and updates using skip lists.
Skip lists are a probabilistic alternative to balanced trees that
provide much of the simplicity of unbalanced trees, together
with good worst-case expected performance. In this paper, we briefly
review skip lists, describe simple methods for concurrent maintenance
of sorted linked lists, formally prove the correctness of these methods,
and show how they can be extended to provide simple and efficient
algorithms for concurrent maintenance of skip lists.
(Also cross-referenced as UMIACS-TR-90-80)