We present randomized wait-free lock implementations that are simple and time- and space-efficient. One of them uses only three shared variables and has expected step complexity O(κ log2 κ), where κ is the maximum point contention. The other ones have optimal expected step complexity O(κ), but require O(log n) space, where n is the number of processes in the system. All of our algorithms can be easily implemented on standard hardware that supports compare-and-swap and fetch-and-increment/decrement operations.

At STOC 2021, Giakkoupis, Giv, and Woelfel [10], presented an efficient randomized implementation of Double Compare-And-Swap (DCAS) from Compare-And-Swap (CAS) objects. DCAS is a useful and fundamental synchronization primitive for shared memory systems, which, contrary to CAS, is not available in hardware. The DCAS algorithm has O(log n) expected amortized step complexity against an oblivious adversary, where n is the number of processes in the system. The bottleneck of this algorithm is a building block, introduced in the same paper: A repeated choice (RC) object, which allows processes to propose values, and later agree on (and "lock in") one of the proposed values, which is roughly uniformly distributed among the "recently" proposed ones. The object can then be unlocked, and the process be repeated.