Master of Science in Computer Science
First Committee Member
Ajoy K. Datta
Second Committee Member
Ajoy K. Datta
Third Committee Member
Lawrence L. Larmore
Fourth Committee Member
Fifth Committee Member
Number of Pages
We present a non-blocking lock-free implementation of skip list data structure using multi word compare and swap (CASN) operation. This operation is designed to work on arbitrary number of memory locations as a single atomic step. We discuss the implementation details of CASN operation which only utilizes the single word compare and swap atomic primitive found in most of the contemporary multiprocessor systems. Using this operation, we first design lock-free algorithms to implement various operations on linked list data structure, then extend it to design skip lists. Skip list is a probabilistic data structure composed of linked lists stacked together forming different levels. It provides expected logarithmic time search like balanced search trees, but without requiring rebalancing. The fundamental operations on a skip list data structure require traversing and updating a number of memory locations. Due to this nature of the data structure, using a powerful atomic primitive like CASN in its implementation simplifies the design and makes the concurrent reasoning easier. In addition to fundamental operations, we present a variety of other operations on linked list and skip list data structures and provide examples to support the correctness of the proposed algorithms.
casn; concurrent; data structure; skip-list
University of Nevada, Las Vegas
Tuladhar, Anish Ratna, "Concurrent Non-blocking Skip List Using Multi-word Compare and Swap Operation" (2015). UNLV Theses, Dissertations, Professional Papers, and Capstones. 2438.
IN COPYRIGHT. For more information about this rights statement, please visit http://rightsstatements.org/vocab/InC/1.0/