Anonymous Shared Memory

Gadi Taubenfeld

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים


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.

שפה מקוריתאנגלית
מספר המאמר4
עמודים (מ-עד)24:1-24:30
מספר עמודים30
כתב עתJournal of the ACM
מספר גיליון4
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 16 אוג׳ 2022
פורסם באופן חיצוניכן

הערה ביבליוגרפית

Publisher Copyright:
© 2022 Association for Computing Machinery.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Anonymous Shared Memory'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי