Constant-RMR implementations of CAS and other synchronization primitives using read and write operations
Wojciech Golab, Vassos Hadzilacos, Danny Hendler, Philipp Woelfel · 2007
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.