%0 Conference Paper %1 Kogan:2012:MCF:2145816.2145835 %A Kogan, Alex %A Petrank, Erez %B Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming %C New York, NY, USA %D 2012 %I ACM %K composition sharedmemory %P 141--150 %R 10.1145/2145816.2145835 %T A methodology for creating fast wait-free data structures %U http://doi.acm.org/10.1145/2145816.2145835 %X Lock-freedom is a progress guarantee that ensures overall program progress. Wait-freedom is a stronger progress guarantee that ensures the progress of each thread in the program. While many practical lock-free algorithms exist, wait-free algorithms are typically inefficient and hardly used in practice. In this paper, we propose a methodology called <i>fast-path-slow-path</i> for creating efficient wait-free algorithms. The idea is to execute the efficient lock-free version most of the time and revert to the wait-free version only when things go wrong. The generality and effectiveness of this methodology is demonstrated by two examples. In this paper, we apply this idea to a recent construction of a wait-free queue, bringing the wait-free implementation to perform in practice as efficient as the lock-free implementation. In another work, the fast-path-slow-path methodology has been used for (dramatically) improving the performance of a wait-free linked-list. %@ 978-1-4503-1160-1

@inproceedings{Kogan:2012:MCF:2145816.2145835, abstract = {Lock-freedom is a progress guarantee that ensures overall program progress. Wait-freedom is a stronger progress guarantee that ensures the progress of each thread in the program. While many practical lock-free algorithms exist, wait-free algorithms are typically inefficient and hardly used in practice. In this paper, we propose a methodology called <i>fast-path-slow-path</i> for creating efficient wait-free algorithms. The idea is to execute the efficient lock-free version most of the time and revert to the wait-free version only when things go wrong. The generality and effectiveness of this methodology is demonstrated by two examples. In this paper, we apply this idea to a recent construction of a wait-free queue, bringing the wait-free implementation to perform in practice as efficient as the lock-free implementation. In another work, the fast-path-slow-path methodology has been used for (dramatically) improving the performance of a wait-free linked-list.}, acmid = {2145835}, added-at = {2012-08-29T11:28:28.000+0200}, address = {New York, NY, USA}, author = {Kogan, Alex and Petrank, Erez}, biburl = {https://www.bibsonomy.org/bibtex/2b57bb0655e33878eb3460d9f09fab95d/giuliano.losa}, booktitle = {Proceedings of the 17th ACM SIGPLAN symposium on Principles and Practice of Parallel Programming}, description = {A methodology for creating fast wait-free data structures}, doi = {10.1145/2145816.2145835}, interhash = {5cdbccea09119816beb670f0ccb35ce8}, intrahash = {b57bb0655e33878eb3460d9f09fab95d}, isbn = {978-1-4503-1160-1}, keywords = {composition sharedmemory}, location = {New Orleans, Louisiana, USA}, numpages = {10}, pages = {141--150}, publisher = {ACM}, series = {PPoPP '12}, timestamp = {2012-08-29T11:28:28.000+0200}, title = {A methodology for creating fast wait-free data structures}, url = {http://doi.acm.org/10.1145/2145816.2145835}, year = 2012 }