{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T05:14:38Z","timestamp":1739596478075,"version":"3.37.1"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T00:00:00Z","timestamp":1737676800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T00:00:00Z","timestamp":1737676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100006260","name":"Technion - Israel Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100006260","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,3]]},"abstract":"Abstract<\/jats:title>\n 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 may fail if there is contention on the locks, in which case the code is not run. Given an upper bound \n \n $$\\kappa $$<\/jats:tex-math>\n \n \u03ba<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> known to the algorithm on the point contention of any lock, and an upper bound L<\/jats:italic> on the number of locks in a tryLock\u2019s set, a tryLock will succeed in acquiring its locks and running the code with probability at least \n \n $$1\/(\\kappa L)$$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n \/<\/mml:mo>\n (<\/mml:mo>\n \u03ba<\/mml:mi>\n L<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. It is thus fair. Furthermore, if the maximum step complexity for the code in any lock is T<\/jats:italic>, the operation will take \n \n $$O(\\kappa ^2 L^2 T)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u03ba<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n \n L<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n T<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> steps, regardless of whether it succeeds or fails. The operations are independent, thus if the tryLock is repeatedly retried on failure, it will succeed in \n \n $$O(\\kappa ^3 L^3 T)$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n \u03ba<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n \n L<\/mml:mi>\n 3<\/mml:mn>\n <\/mml:msup>\n T<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> expected steps. If the algorithm does not know the bounds \n \n $$\\kappa $$<\/jats:tex-math>\n \n \u03ba<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and L<\/jats:italic>, we present a variant that can guarantee a probability of at least \n \n $$1\/\\kappa L\\log (\\kappa L T)$$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n \/<\/mml:mo>\n \u03ba<\/mml:mi>\n L<\/mml:mi>\n log<\/mml:mo>\n (<\/mml:mo>\n \u03ba<\/mml:mi>\n L<\/mml:mi>\n T<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> of success. We assume an oblivious adversarial scheduler, which does not make decisions based on the operations, but can predetermine any schedule for the processes, which is unknown to our algorithm. Furthermore, to account for applications that change their future requests based on the results of previous tryLock operations, we strengthen the adversary by allowing decisions of the start times and lock sets of tryLock operations to be made adaptively, given the history of the execution so far.<\/jats:p>","DOI":"10.1007\/s00446-024-00474-4","type":"journal-article","created":{"date-parts":[[2025,1,24]],"date-time":"2025-01-24T06:21:25Z","timestamp":1737699685000},"page":"51-72","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast and fair randomized wait-free locks"],"prefix":"10.1007","volume":"38","author":[{"given":"Naama","family":"Ben-David","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guy E.","family":"Blelloch","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,1,24]]},"reference":[{"key":"474_CR1","doi-asserted-by":"crossref","unstructured":"Drachsler, D., Vechev, M., Yahav, E.: Practical concurrent binary search trees via logical ordering. In: ACM Symposium on Principles and Practice of Parallel Programming (PPOPP) (2014)","DOI":"10.1145\/2555243.2555269"},{"key":"474_CR2","doi-asserted-by":"crossref","unstructured":"Bronson, N.G., Casper, J., Chafi, H., Olukotun, K.: A practical concurrent binary search tree. In: ACM Symposium on Principles and Practice of Parallel Programming (PPOPP), pp. 257\u2013268 (2010)","DOI":"10.1145\/1693453.1693488"},{"key":"474_CR3","doi-asserted-by":"crossref","unstructured":"Mao, Y., Kohler, E., Morris, R.T.: Cache craftiness for fast multicore key-value storage. In: ACM European Conference on Computer Systems (EuroSys) (2012)","DOI":"10.1145\/2168836.2168855"},{"key":"474_CR4","doi-asserted-by":"crossref","unstructured":"Heller, S., Herlihy, M., Luchangco, V., Moir, M., Scherer, W.N., Shavit, N.: A lazy concurrent list-based set algorithm. In: Conf. on Principles of Distributed Systems (OPODIS) (2006)","DOI":"10.1007\/11795490_3"},{"issue":"3","key":"474_CR5","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1145\/320613.320619","volume":"5","author":"HT Kung","year":"1980","unstructured":"Kung, H.T., Lehman, P.L.: Concurrent manipulation of binary search trees. ACM Trans. Database Syst 5(3), 354\u2013382 (1980)","journal-title":"ACM Trans. Database Syst"},{"key":"474_CR6","unstructured":"Bayer, R., Schkolnick, M.: Concurrency of Operations on B-Trees, pp. 129\u2013139. Morgan Kaufmann Publishers Inc., San Francisco (1988)"},{"key":"474_CR7","doi-asserted-by":"crossref","unstructured":"Leis, V., Scheibner, F., Kemper, A., Neumann, T.: The art of practical synchronization. In: Proc. International Workshop on Data Management on New Hardware (2016)","DOI":"10.1145\/2933349.2933352"},{"key":"474_CR8","unstructured":"Pugh, W.: Concurrent maintenance of skip lists. Technical Report TR-CS-2222, Dept. of Computer Science, University of Maryland, College Park (1989)"},{"key":"474_CR9","unstructured":"Low, Y., Gonzalez, J.E., Kyrola, A., Bickson, D., Guestrin, C.E., Hellerstein, J.: Graphlab: A new framework for parallel machine learning. Uncertainty in Artificial Intelligence (UAI) (2010)"},{"key":"474_CR10","doi-asserted-by":"crossref","unstructured":"Brown, J., Grossman, J.P., Knight, T.: A lightweight idempotent messaging protocol for faulty networks. In: ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) (2002)","DOI":"10.1145\/564909.564912"},{"key":"474_CR11","doi-asserted-by":"crossref","unstructured":"de Kruijf, M.A., Sankaralingam, K., Jha, S.: Static analysis and compiler design for idempotent processing. In: ACM Conference on Programming Language Design and Implementation (PLDI) (2012)","DOI":"10.1145\/2254064.2254120"},{"key":"474_CR12","doi-asserted-by":"crossref","unstructured":"de Kruijf, M., Sankaralingam, K.: Idempotent code generation: Implementation, analysis, and evaluation. In: IEEE\/ACM International Symposium on Code Generation and Optimization (CGO) (2013)","DOI":"10.1109\/CGO.2013.6495002"},{"key":"474_CR13","doi-asserted-by":"crossref","unstructured":"Turek, J., Shasha, D., Prakash, S.: Locking without blocking: making lock based concurrent data structure algorithms nonblocking. In: Principles of Database Systems (PODS), pp. 212\u2013222 (1992)","DOI":"10.1145\/137097.137873"},{"key":"474_CR14","doi-asserted-by":"crossref","unstructured":"Barnes, G.: A method for implementing lock-free shared-data structures. In: ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 261\u2013270 (1993)","DOI":"10.1145\/165231.165265"},{"key":"474_CR15","doi-asserted-by":"crossref","unstructured":"Ben-David, N., Blelloch, G.E., Wei, Y.: Lock-free locks revisited. In: ACM Symposium on Principles and Practice of Parallel Programming (PPOPP) (2022)","DOI":"10.1145\/3503221.3508433"},{"key":"474_CR16","doi-asserted-by":"publisher","unstructured":"Abrahamson, K.R.: On achieving consensus using a shared memory. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 291\u2013302 (1988). https:\/\/doi.org\/10.1145\/62546.62594","DOI":"10.1145\/62546.62594"},{"key":"474_CR17","doi-asserted-by":"publisher","unstructured":"Rabin, M.O.: N-process synchronization by $$4 \\log _2 n$$-valued shared variables. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 407\u2013410 (1980). https:\/\/doi.org\/10.1109\/SFCS.1980.26","DOI":"10.1109\/SFCS.1980.26"},{"key":"474_CR18","doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Woelfel, P.: A tight rmr lower bound for randomized mutual exclusion. In: ACM Symposium on Theory of Computing (STOC), pp. 983\u20131002 (2012)","DOI":"10.1145\/2213977.2214066"},{"key":"474_CR19","doi-asserted-by":"crossref","unstructured":"Giakkoupis, G., Woelfel, P.: Randomized mutual exclusion with constant amortized rmr complexity on the dsm. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 504\u2013513 (2014). IEEE","DOI":"10.1109\/FOCS.2014.60"},{"key":"474_CR20","doi-asserted-by":"publisher","unstructured":"Lehmann, D., Rabin, M.O.: 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), pp. 133\u2013138 (1981). https:\/\/doi.org\/10.1145\/567532.567547","DOI":"10.1145\/567532.567547"},{"key":"474_CR21","doi-asserted-by":"publisher","unstructured":"Lynch, N.A., Saias, I., Segala, R.: Proving time bounds for randomized distributed algorithms. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 314\u2013323 (1994). https:\/\/doi.org\/10.1145\/197917.198117","DOI":"10.1145\/197917.198117"},{"key":"474_CR22","doi-asserted-by":"publisher","unstructured":"Duflot, M., Fribourg, L., Picaronny, C.: Randomized dining philosophers without fairness assumption. In: Foundations of Information Technology in the Era of Networking and Mobile Computing, IFIP, pp. 169\u2013180 (2002). https:\/\/doi.org\/10.1007\/978-0-387-35608-2_15","DOI":"10.1007\/978-0-387-35608-2_15"},{"key":"474_CR23","doi-asserted-by":"publisher","unstructured":"Saias, I.: Proving probabilistic correctness statements: the case of rabin\u2019s algorithm for mutual exclusion. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 263\u2013274 (1992). https:\/\/doi.org\/10.1145\/135419.135466","DOI":"10.1145\/135419.135466"},{"key":"474_CR24","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Rabin, M.O.: Randomized mutual exclusion algorithms revisited. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 275\u2013283 (1992)","DOI":"10.1145\/135419.135468"},{"issue":"3","key":"474_CR25","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/78969.78972","volume":"12","author":"MP Herlihy","year":"1990","unstructured":"Herlihy, M.P., Wing, J.M.: Linearizability: a correctness condition for concurrent objects. ACM Trans. Prog Languages and Syst. (TOPLAS) 12(3), 463\u2013492 (1990)","journal-title":"ACM Trans. Prog Languages and Syst. (TOPLAS)"},{"key":"474_CR26","doi-asserted-by":"publisher","unstructured":"Golab, W.M., Higham, L., Woelfel, P.: Linearizable implementations do not suffice for randomized distributed computation. In: ACM Symposium on Theory of Computing (STOC), pp. 373\u2013382 (2011). https:\/\/doi.org\/10.1145\/1993636.1993687","DOI":"10.1145\/1993636.1993687"},{"issue":"1","key":"474_CR27","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","volume":"70","author":"R Cole","year":"1986","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing with applications to optimal parallel list ranking. Inform. Control 70(1), 32\u201353 (1986)","journal-title":"Inform. Control"},{"issue":"1","key":"474_CR28","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1145\/114005.102808","volume":"13","author":"M Herlihy","year":"1991","unstructured":"Herlihy, M.: Wait-free synchronization. ACM Trans. Prog. Languages and Syst. (TOPLAS) 13(1), 124\u2013149 (1991)","journal-title":"ACM Trans. Prog. Languages and Syst. (TOPLAS)"},{"key":"474_CR29","doi-asserted-by":"crossref","unstructured":"Afek, Y., Merritt, M., Taubenfeld, G., Touitou, D.: Disentangling multi-object operations (extended abstract). In: ACM Symposium on Principles of Distributed Computing (PODC) (1997)","DOI":"10.1145\/259380.259431"},{"issue":"2","key":"474_CR30","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1145\/319566.319567","volume":"6","author":"HT Kung","year":"1981","unstructured":"Kung, H.T., Robinson, J.T.: On optimistic methods for concurrency control. ACM Trans. Database Syst. 6(2), 213\u2013226 (1981)","journal-title":"ACM Trans. Database Syst."},{"issue":"2","key":"474_CR31","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/s004460050028","volume":"10","author":"N Shavit","year":"1997","unstructured":"Shavit, N., Touitou, D.: Software transactional memory. Distrib. Comput. 10(2), 99\u2013116 (1997)","journal-title":"Distrib. Comput."},{"issue":"2","key":"474_CR32","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1145\/1233307.1233309","volume":"25","author":"K Fraser","year":"2007","unstructured":"Fraser, K., Harris, T.: Concurrent programming without locks. ACM Trans. Comput. Syst. (TOCS) 25(2), 5 (2007)","journal-title":"ACM Trans. Comput. Syst. (TOCS)"},{"key":"474_CR33","doi-asserted-by":"crossref","unstructured":"Attiya, H., Epstein, L., Shachnai, H., Tamir, T.: Transactional contention management as a non-clairvoyant scheduling problem. In: ACM Symposium on Principles of Distributed Computing (PODC) (2006)","DOI":"10.1145\/1146381.1146428"},{"key":"474_CR34","doi-asserted-by":"crossref","unstructured":"Guerraoui, R., Herlihy, M., Pochon, B.: Toward a theory of transactional contention managers. In: ACM Symposium on Principles of Distributed Computing (PODC) (2005)","DOI":"10.1145\/1073814.1073863"},{"key":"474_CR35","doi-asserted-by":"crossref","unstructured":"Schneider\u00a0J., W.R.: Bounds on contention management algorithms. In: International Symposium on Algorithms and Computation (ISAAC) (2009)","DOI":"10.1007\/978-3-642-10631-6_46"},{"key":"474_CR36","first-page":"299","volume":"4","author":"G Sharma","year":"2012","unstructured":"Sharma, G., Busch, C.: A competitive analysis for balanced transactional memory workloads. Algorithmica 4, 299\u2013322 (2012)","journal-title":"Algorithmica"},{"key":"474_CR37","doi-asserted-by":"crossref","unstructured":"Afek, Y., Dauber, D., Touitou, D.: Wait-free made fast. In: ACM Symposium on Theory of Computing (STOC), pp. 538\u2013547 (1995)","DOI":"10.1145\/225058.225271"},{"issue":"5","key":"474_CR38","doi-asserted-by":"publisher","first-page":"1013","DOI":"10.1145\/502102.502105","volume":"48","author":"H Attiya","year":"2001","unstructured":"Attiya, H., Dagan, E.: Improved implementations of binary universal operations. J. ACM 48(5), 1013\u20131037 (2001)","journal-title":"J. ACM"},{"issue":"1","key":"474_CR39","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1145\/366062.366084","volume":"4","author":"PZ Ingerman","year":"1961","unstructured":"Ingerman, P.Z.: Thunks: a way of compiling procedure statements with some comments on procedure declarations. Commun. ACM 4(1), 55\u201358 (1961)","journal-title":"Commun. ACM"},{"key":"474_CR40","volume-title":"Lambda: The ultimate imperative","author":"GL Steele Jr","year":"1976","unstructured":"Steele, G.L., Jr., Sussman, G.J.: Lambda: The ultimate imperative. Technical report, MIT CAMBRIDGE ARTIFICIAL INTELLIGENCE LAB (1976)"},{"issue":"4","key":"474_CR41","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1137\/S0097539790192635","volume":"23","author":"B Chor","year":"1994","unstructured":"Chor, B., Israeli, A., Li, M.: Wait-free consensus using asynchronous hardware. SIAM J. Comput. 23(4), 701\u2013712 (1994)","journal-title":"SIAM J. Comput."},{"key":"474_CR42","doi-asserted-by":"crossref","unstructured":"Ben-David, N., Blelloch, G.E., Friedman, M., Wei, Y.: Delay-free concurrency on faulty persistent memory. In: ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 253\u2013264 (2019)","DOI":"10.1145\/3323165.3323187"},{"key":"474_CR43","unstructured":"Blelloch, G.E., Wei, Y.: LL\/SC and Atomic Copy: Constant Time. In: International Symposium on Distributed Computing (DISC), Space Efficient Implementations Using Only Pointer-Width CAS. In (2020)"},{"key":"474_CR44","doi-asserted-by":"crossref","unstructured":"Aghazadeh, Z., Golab, W., Woelfel, P.: Making objects writable. In: ACM Symposium on Principles of Distributed Computing (PODC), pp. 385\u2013395 (2014)","DOI":"10.1145\/2611462.2611483"},{"key":"474_CR45","doi-asserted-by":"crossref","unstructured":"Afek, Y., Stupp, G., Touitou, D.: Long-lived adaptive collect with applications. In: IEEE Symposium on Foundations of Computer Science (FOCS), pp. 262\u2013272 (1999). IEEE","DOI":"10.1109\/SFFCS.1999.814598"},{"key":"474_CR46","doi-asserted-by":"crossref","unstructured":"Anderson, D., Blelloch, G.E., Wei, Y.: Concurrent deferred reference counting with constant-time overhead. In: ACM Conference on Programming Language Design and Implementation (PLDI) (2021)","DOI":"10.1145\/3410290"},{"issue":"2","key":"474_CR47","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1007\/BF01786228","volume":"1","author":"L Lamport","year":"1986","unstructured":"Lamport, L.: On interprocess communication. Distrib. Comput. 1(2), 86\u2013101 (1986)","journal-title":"Distrib. Comput."}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-024-00474-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-024-00474-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-024-00474-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T11:39:36Z","timestamp":1739533176000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-024-00474-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,24]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["474"],"URL":"https:\/\/doi.org\/10.1007\/s00446-024-00474-4","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,1,24]]},"assertion":[{"value":"20 November 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no other conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}