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.