Lock-free linked lists and skip lists

@inproceedings{citeulike:375335, abstract = {Lock-free shared data structures implement distributed objects without the use of mutual exclusions, thus providing robustness and reliability. We present new implementations of lock-free linked list and lock-free skip list dictionary data structures for shared-memory systems. We give a detailed proof of correctness for both of them and present an amortized performance analysis for our linked lists. To the best of our knowledge, our implementation of the lock-free skip lists is the first that does not use the universal constructions. We also show that our linked lists implementation has a better amortized performance than prior lock-free implementations of this data structure. Our algorithms use the single word C\&S synchronization primitive.}, address = {New York, NY, USA}, author = {Fomitchev, M. and Ruppert, E. }, booktitle = {PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing}, citeulike-article-id = {375335}, keywords = {multithreading, programming, synchronization}, pages = {50--59}, posted-at = {2008-06-28 15:42:12}, priority = {4}, publisher = {ACM Press}, title = {Lock-free linked lists and skip lists}, year = {2004} }

TY - CONF ID - citeulike:375335 L3 - citeulike-article-id:375335 TI - Lock-free linked lists and skip lists T2 - PODC '04: Proceedings of the twenty-third annual ACM symposium on Principles of distributed computing SP - 50 EP - 59 AD - New York, NY, USA PB - ACM Press N2 - Lock-free shared data structures implement distributed objects without the use of mutual exclusions, thus providing robustness and reliability. We present new implementations of lock-free linked list and lock-free skip list dictionary data structures for shared-memory systems. We give a detailed proof of correctness for both of them and present an amortized performance analysis for our linked lists. To the best of our knowledge, our implementation of the lock-free skip lists is the first that does not use the universal constructions. We also show that our linked lists implementation has a better amortized performance than prior lock-free implementations of this data structure. Our algorithms use the single word C&S synchronization primitive. KW - multithreading KW - programming KW - synchronization AU - Fomitchev, M AU - Ruppert, E PY - 2004/// ER -