Fast and Fair Randomized Wait-Free Locks
Pages 187 - 197
Abstract
We present a randomized approach for wait-free locks with strong bounds on time and fairness in a context in which any process can be arbitrarily delayed. Our approach supports a tryLock operation that is given a set of locks, and code to run when all the locks are acquired. A tryLock operation, or attempt, may fail if there is contention on the locks, in which case the code is not run. Given an upper bound k known to the algorithm on the point contention of any lock, and an upper bound L on the number of locks in a try- Lock's set, a tryLock will succeed in acquiring its locks and running the code with probability at least 1/(kL). It is thus fair. Furthermore, if the maximum step complexity for the code in any lock is T, the attempt will take O(k2L2T ) steps, regardless of whether it succeeds or fails. The attempts are independent, thus if the tryLock is repeatedly retried on failure, it will succeed in O(k3L3T ) expected steps, and with high probability in not much more.
Supplementary Material
Presentation video
- Download
- 938.52 MB
References
[1]
Karl R. Abrahamson. On achieving consensus using a shared memory. In ACM Symposium on Principles of Distributed Computing (PODC), pages 291--302, 1988.
[2]
Yehuda Afek, Dalia Dauber, and Dan Touitou. Wait-free made fast. In ACM Symposium on Theory of Computing (STOC), pages 538--547, 1995.
[3]
Yehuda Afek, Michael Merritt, Gadi Taubenfeld, and Dan Touitou. Disentangling multi-object operations (extended abstract). In ACM Symposium on Principles of Distributed Computing (PODC), 1997.
[4]
Yehuda Afek, Gideon Stupp, and Dan Touitou. Long-lived adaptive collect with applications. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 262--272. IEEE, 1999.
[5]
Zahra Aghazadeh,Wojciech Golab, and PhilippWoelfel. Making objects writable. In ACM Symposium on Principles of Distributed Computing (PODC), pages 385--395, 2014.
[6]
Daniel Anderson, Guy E Blelloch, and Yuanhao Wei. Concurrent deferred reference counting with constant-time overhead. In ACM Conference on Programming Language Design and Implementation (PLDI), 2021.
[7]
Hagit Attiya and Eyal Dagan. Improved implementations of binary universal operations. J. ACM, 48(5), September 2001.
[8]
Hagit Attiya, Leah Epstein, Hadas Shachnai, and Tami Tamir. Transactional contention management as a non-clairvoyant scheduling problem. In ACM Symposium on Principles of Distributed Computing (PODC), 2006.
[9]
Greg Barnes. A method for implementing lock-free shared-data structures. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 261--270, 1993.
[10]
R. Bayer and M. Schkolnick. Concurrency of Operations on B-Trees, page 129--139. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1988.
[11]
Naama Ben-David and Guy E. Blelloch. Fast and fair lock-free locks. CoRR, abs/2108.04520, 2021.
[12]
Naama Ben-David, Guy E Blelloch, Michal Friedman, and Yuanhao Wei. Delayfree concurrency on faulty persistent memory. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pages 253--264, 2019.
[13]
Naama Ben-David, Guy E Blelloch, and Yuanhao Wei. Lock-free locks revisited. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP), 2022.
[14]
Guy E. Blelloch and Yuanhao Wei. LL/SC and Atomic Copy: Constant Time, Space Efficient Implementations Using Only Pointer-Width CAS. In International Symposium on Distributed Computing (DISC), 2020.
[15]
Nathan G. Bronson, Jared Casper, Hassan Chafi, and Kunle Olukotun. A practical concurrent binary search tree. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP), page 257--268, 2010.
[16]
Jeremy Brown, J. P. Grossman, and Tom Knight. A lightweight idempotent messaging protocol for faulty networks. In ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2002.
[17]
Benny Chor, Amos Israeli, and Ming Li. Wait-free consensus using asynchronous hardware. SIAM Journal on Computing, 23(4):701--712, 1994.
[18]
Richard Cole and Uzi Vishkin. Deterministic coin tossing with applications to optimal parallel list ranking. Information and Control, 70(1), 1986.
[19]
Marc de Kruijf and Karthikeyan Sankaralingam. Idempotent code generation: Implementation, analysis, and evaluation. In IEEE/ACM International Symposium on Code Generation and Optimization (CGO), 2013.
[20]
Marc A. de Kruijf, Karthikeyan Sankaralingam, and Somesh Jha. Static analysis and compiler design for idempotent processing. In ACM Conference on Programming Language Design and Implementation (PLDI), 2012.
[21]
Dana Drachsler, Martin Vechev, and Eran Yahav. Practical concurrent binary search trees via logical ordering. In ACM Symposium on Principles and Practice of Parallel Programming (PPOPP), 2014.
[22]
Marie Duflot, Laurent Fribourg, and Claudine Picaronny. Randomized dining philosophers without fairness assumption. In Foundations of Information Technology in the Era of Networking and Mobile Computing, IFIP, pages 169--180. Kluwer, 2002.
[23]
Keir Fraser and Tim Harris. Concurrent programming without locks. ACM Transactions on Computer Systems (TOCS), 25(2):5--es, 2007.
[24]
George Giakkoupis and PhilippWoelfel. A tight rmr lower bound for randomized mutual exclusion. In ACM Symposium on Theory of Computing (STOC), pages 983--1002, 2012.
[25]
George Giakkoupis and PhilippWoelfel. Randomized mutual exclusion with constant amortized rmr complexity on the dsm. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 504--513. IEEE, 2014.
[26]
Wojciech M. Golab, Lisa Higham, and Philipp Woelfel. Linearizable implementations do not suffice for randomized distributed computation. In ACM Symposium on Theory of Computing (STOC), pages 373--382, 2011.
[27]
Rachid Guerraoui, Maurice Herlihy, and Bastian Pochon. Toward a theory of transactional contention managers. In ACM Symposium on Principles of Distributed Computing (PODC), 2005.
[28]
Steve Heller, Maurice Herlihy, Victor Luchangco, Mark Moir, William N. Scherer, and Nir Shavit. A lazy concurrent list-based set algorithm. In Conf. on Principles of Distributed Systems (OPODIS), 2006.
[29]
Maurice Herlihy. Wait-free synchronization. ACM Transactions on Programming Languages and Systems (TOPLAS), 13(1):124--149, January 1991.
[30]
Maurice P. Herlihy and Jeanette M. Wing. Linearizability: A correctness condition for concurrent objects. ACM Transactions on Programming Languages and Systems (TOPLAS), 12(3), 1990.
[31]
Peter Zilahy Ingerman. Thunks: a way of compiling procedure statements with some comments on procedure declarations. Communications of the ACM, 4(1):55-- 58, 1961.
[32]
H. T. Kung and Philip L. Lehman. Concurrent manipulation of binary search trees. ACM Trans. Database Syst., 5(3), 1980.
[33]
H. T. Kung and John T. Robinson. On optimistic methods for concurrency control. ACM Trans. Database Syst., 6(2), June 1981.
[34]
Eyal Kushilevitz and Michael O Rabin. Randomized mutual exclusion algorithms revisited. In ACM Symposium on Principles of Distributed Computing (PODC), pages 275--283, 1992.
[35]
Leslie Lamport. On interprocess communication. Distributed computing, 1(2):86-- 101, 1986.
[36]
Daniel Lehmann and Michael O. Rabin. On the advantages of free choice: A symmetric and fully distributed solution to the dining philosophers problem. In ACM Symposium on Principles of Programming Languages (POPL), pages 133--138, 1981.
[37]
Viktor Leis, Florian Scheibner, Alfons Kemper, and Thomas Neumann. The art of practical synchronization. In Proc. International Workshop on Data Management on New Hardware, 2016.
[38]
Yucheng Low, Joseph E Gonzalez, Aapo Kyrola, Danny Bickson, Carlos E Guestrin, and Joseph Hellerstein. Graphlab: A newframework for parallel machine learning. Uncertainty in Artificial Intelligence (UAI), 2010.
[39]
Nancy A. Lynch, Isaac Saias, and Roberto Segala. Proving time bounds for randomized distributed algorithms. In ACM Symposium on Principles of Distributed Computing (PODC), pages 314--323, 1994.
[40]
Yandong Mao, Eddie Kohler, and Robert Tappan Morris. Cache craftiness for fast multicore key-value storage. In ACM European Conference on Computer Systems (EuroSys), 2012.
[41]
William Pugh. Concurrent maintenance of skip lists. Technical Report TR-CS- 2222, Dept. of Computer Science, University of Maryland, College Park, 1989.
[42]
Michael O. Rabin. N-process synchronization by 4 log2 n-valued shared variables. In IEEE Symposium on Foundations of Computer Science (FOCS), pages 407--410, 1980.
[43]
Isaac Saias. Proving probabilistic correctness statements: the case of rabin's algorithm for mutual exclusion. In ACM Symposium on Principles of Distributed Computing (PODC), pages 263--274, 1992.
[44]
Wattenhofer R. Schneider J. Bounds on contention management algorithms. In International Symposium on Algorithms and Computation (ISAAC), 2009.
[45]
G. Sharma and C Busch. A competitive analysis for balanced transactional memory workloads. Algorithmica, 4, 2012.
[46]
Nir Shavit and Dan Touitou. Software transactional memory. Distributed Computing, 10(2):99--116, 1997.
[47]
Guy Lewis Steele Jr and Gerald Jay Sussman. Lambda: The ultimate imperative. Technical report, MIT CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB, 1976.
[48]
John Turek, Dennis Shasha, and Sundeep Prakash. Locking without blocking: making lock based concurrent data structure algorithms nonblocking. In Principles of Database Systems (PODS), pages 212--222, 1992.
Index Terms
- Fast and Fair Randomized Wait-Free Locks
Recommendations
Lock-free locks revisited
PPoPP '22: Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel ProgrammingThis paper presents a new and practical approach to lock-free locks based on helping, which allows the user to write code using fine-grained locks, but run it in a lock-free manner. Although lock-free locks have been suggested in the past, they are ...
A practical wait-free simulation for lock-free data structures
PPoPP '14: Proceedings of the 19th ACM SIGPLAN symposium on Principles and practice of parallel programmingLock-free data structures guarantee overall system progress, whereas wait-free data structures guarantee the progress of each and every thread, providing the desirable non-starvation guarantee for concurrent data structures. While practical lock-free ...
WFR-TM
Transactional Memory (TM) is a promising concurrent programming paradigm which employs transactions to achieve synchronization in accessing common data known as transactional variables. A transaction may either commit, making its updates to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
509 pages
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 July 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
Acceptance Rates
Overall Acceptance Rate 740 of 2,477 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 297Total Downloads
- Downloads (Last 12 months)111
- Downloads (Last 6 weeks)31
Reflects downloads up to 15 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in