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-factor increase in RMR complexity.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:OTU.1807/26182 |
| Date | 15 February 2011 |
| Creators | Golab, Wojciech |
| Contributors | Hadzilacos, Vassos |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | en_ca |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0018 seconds