Name
Abstract | ||
|---|---|---|
Recoverable mutual exclusion (RME) is a variation on the classic mutual exclusion (ME) problem that allows processes to crash and recover. The time complexity of RME algorithms is quantified in the same way as for ME, namely by counting remote memory references -- expensive memory operations that traverse the processor-to-memory interconnect. Prior work on the RME problem established an upper bound of O(log N) RMRs in an asynchronous shared memory model with N processes that communicate using atomic read and write operations, prompting the question whether sub-logarithmic RMR complexity is attainable using common read-modify-write primitives. We answer this question positively in the cache-coherent model by presenting an RME algorithm that incurs O(log N / log log N) RMRs and uses read, write, Fetch-And-Store, and Compare-And-Swap instructions. We also present an O(1) RMRs algorithm that relies on double-word Compare-And-Swap and a double-word variation of Fetch-And-Store. Both algorithms are inspired by Mellor-Crummey and Scott's queue lock. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1145/3087801.3087819 | PODC |
Keywords | Field | DocType |
Mutual exclusion, recovery, fault tolerance, concurrency, shared memory, multi-core algorithms, non-volatile main memory, persistent data structures | Asynchronous communication,Binary logarithm,Shared memory,Upper and lower bounds,Concurrency,Computer science,Queue,Theoretical computer science,Time complexity,Mutual exclusion,Distributed computing | Conference |
Citations | PageRank | References |
3 | 0.40 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wojciech Golab | 1 | 210 | 17.22 |
| Danny Hendler | 2 | 726 | 44.54 |