Concurrent Maintenance of Skip Lists

Loading...
Thumbnail Image

Files

CS-TR-2222.ps (256.14 KB)
No. of downloads: 1043
CS-TR-2222.pdf (87.72 KB)
No. of downloads: 3184

Publication or External Link

Date

1998-10-15

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