You can manage bookmarks using lists, please log in to your user account for this.
Media type:
E-Article
Title:
Anonymous Shared Memory
Contributor:
Taubenfeld, Gadi
Published:
Association for Computing Machinery (ACM), 2022
Published in:
Journal of the ACM, 69 (2022) 4, Seite 1-30
Language:
English
DOI:
10.1145/3529752
ISSN:
0004-5411;
1557-735X
Origination:
Footnote:
Description:
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.