Concurrent Maintenance of Skip Lists

Loading...
Thumbnail Image
Files
CS-TR-2222.ps(256.14 KB)
No. of downloads: 1005
CS-TR-2222.pdf(87.72 KB)
No. of downloads: 2961
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)
Notes
Rights