Brief announcement: Are lock-free concurrent algorithms practically wait-free?

D. Alistarh, K. Censor Hille, N. Shavit, in:, ACM, 2014, pp. 50–52.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ;
Abstract
Lock-free concurrent algorithms guarantee that some concurrent operation will always make progress in a finite number of steps. Yet programmers would prefer to treat concurrent code as if it were wait-free, guaranteeing that all operations always make progress. Unfortunately, designing wait-free algorithms is in general a complex undertaking, and the resulting algorithms are not always efficient, so most non-blocking commercial code is only lock-free, and the design of efficient wait-free algorithms has been left to the academic community. In [2], we suggest a solution to this problem. We show that, for a large class of lock-free algorithms, under scheduling conditions which approximate those found in commercial hardware architectures, lock-free algorithms behave as if they are wait-free. In other words, programmers can keep on designing simple lock-free algorithms instead of complex wait-free ones, and in practice, they will get wait-free progress. Our main contribution is a new way of analyzing a general class of lock-free algorithms under a stochastic scheduler. Our analysis relates the individual performance of processes with the global performance of the system using Markov chain lifting between a complex per-process chain and a simpler system progress chain. We show that lock-free algorithms are not only wait-free with probability 1, but that in fact a broad subset of lock-free algorithms can be closely bounded in terms of the average number of steps required until an operation completes.
Publishing Year
Date Published
2014-01-01
Acknowledgement
Dan Alistarh - Part of this work was performed while the author was a Postdoctoral Associate at MIT CSAIL, where he was supported by SNF Postdoctoral Fellows Program, NSF grant CCF-1217921, DoE ASCR grant ER26116/DE-SC0008923, and by grants from the Oracle and Intel corporations. Keren Censor-Hille - Shalon Fellow Nir Shavit - This work was supported in part by NSF grants CCF-1217921 and CCF-1301926, DoE ASCR grant ER26116/DE- SC0008923, and by grants from the Oracle and Intel corporations.
Page
50 - 52
Conference
PODC: Principles of Distributed Computing
IST-REx-ID

Cite this

Alistarh D, Censor Hille K, Shavit N. Brief announcement: Are lock-free concurrent algorithms practically wait-free? In: ACM; 2014:50-52. doi:10.1145/2611462.2611502
Alistarh, D., Censor Hille, K., & Shavit, N. (2014). Brief announcement: Are lock-free concurrent algorithms practically wait-free? (pp. 50–52). Presented at the PODC: Principles of Distributed Computing, ACM. https://doi.org/10.1145/2611462.2611502
Alistarh, Dan, Keren Censor Hille, and Nir Shavit. “Brief Announcement: Are Lock-Free Concurrent Algorithms Practically Wait-Free?,” 50–52. ACM, 2014. https://doi.org/10.1145/2611462.2611502.
D. Alistarh, K. Censor Hille, and N. Shavit, “Brief announcement: Are lock-free concurrent algorithms practically wait-free?,” presented at the PODC: Principles of Distributed Computing, 2014, pp. 50–52.
Alistarh D, Censor Hille K, Shavit N. 2014. Brief announcement: Are lock-free concurrent algorithms practically wait-free? PODC: Principles of Distributed Computing 50–52.
Alistarh, Dan, et al. Brief Announcement: Are Lock-Free Concurrent Algorithms Practically Wait-Free? ACM, 2014, pp. 50–52, doi:10.1145/2611462.2611502.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar