Anonymous Shared Memory
Open Access
- 16 August 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 69 (4), 1-30
- https://doi.org/10.1145/3529752
Abstract
Assuming that there is an a priori agreement between processes on the names of shared memory locations, as is done in almost all the publications on concurrent shared memory algorithms, is tantamount to assuming that agreement has already been solved at a lower-level. It is intriguing to figure out how coordination can be achieved without relying on such lower-level agreement. To better understand the new model, we first design new algorithms for several important problems, such as mutual exclusion, consensus, election, and renaming. Then, we prove space lower bounds, impossibility results, and resolve two foundational long-standing open problems in the context of anonymous memory systems. Using these results, we identify fundamental differences between the standard shared memory model and the strictly weaker anonymous shared memory model. Besides enabling us to understand better the intrinsic limits for coordinating the actions of asynchronous processes, the new model has been shown to be useful in modeling biologically inspired distributed computing methods, especially those based on ideas from molecular biology.Keywords
This publication has 58 references indexed in Scilit:
- Anonymous asynchronous systems: the case of failure detectorsDistributed Computing, 2012
- Fully-adaptive algorithms for long-lived renamingDistributed Computing, 2011
- Algorithms in nature: the convergence of systems biology and computational thinkingMolecular Systems Biology, 2011
- Anonymous and fault-tolerant shared-memory computingDistributed Computing, 2007
- On the importance of having an identity or, is consensus really universal?Distributed Computing, 2005
- Randomized protocols for asynchronous consensusDistributed Computing, 2003
- Algorithms adapting to point contentionJournal of the ACM, 2003
- Robust wait-free hierarchiesJournal of the ACM, 1997
- Wait-free algorithms for fast, long-lived renamingScience of Computer Programming, 1995
- On interprocess communicationDistributed Computing, 1986