Concurrent Maintenance of Skip Lists
| dc.contributor.author | Pugh, William | en_US |
| dc.date.accessioned | 2004-05-31T22:20:48Z | |
| dc.date.available | 2004-05-31T22:20:48Z | |
| dc.date.created | 1990-06 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.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) | en_US |
| dc.format.extent | 262287 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/542 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | UMIACS Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-2222 | en_US |
| dc.relation.ispartofseries | UMIACS; UMIACS-TR-90-80 | en_US |
| dc.title | Concurrent Maintenance of Skip Lists | en_US |
| dc.type | Technical Report | en_US |