Name
Title | ||
|---|---|---|
Constant-RMR implementations of CAS and other synchronization primitives using read and write operations |
Abstract | ||
|---|---|---|
We consider asynchronous multiprocessors where processes communicate only by reading or writing shared memory. We show how to implement consensus, all comparison primitives (such as CAS and TAS), and load-linked/store-conditional using only a constant number of remote memory references (RMRs), in both the cache-coherent and the distributed-shared-memory models of such multiprocessors. Our implementations are blocking, rather than wait-free: they ensure progress provided all processes that invoke the implemented primitive are live. Our results imply that any algorithm using read and write operations, comparison primitives, and load-linked/store-conditional, can be simulated by an algorithm that uses read and write operations only, with at most a constant blowup in RMR complexity. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1145/1281100.1281105 | PODC |
Keywords | Field | DocType |
consensus,distributed shared memory,cache coherence,shared memory,mutual exclusion | Programming language,Computer science,Cache-only memory architecture,Theoretical computer science,Compare-and-swap,Distributed computing,Asynchronous communication,Synchronization,Shared memory,Parallel computing,Distributed memory,Distributed shared memory,Mutual exclusion | Conference |
Citations | PageRank | References |
19 | 0.85 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Wojciech Golab | 1 | 210 | 17.22 |
| Vassos Hadzilacos | 2 | 1204 | 199.70 |
| Danny Hendler | 3 | 726 | 44.54 |
| Philipp Woelfel | 4 | 432 | 38.40 |