Techreport,
Concurrent Maintenance of Skip Lists
Technical Report, UMIACS-TR-90-80. University of Maryland at College Park, (1998)
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)
