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
مستوى الصوت69
رقم الإصدار4
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 16 أغسطس 2022
منشور خارجيًانعم

ملاحظة ببليوغرافية

Publisher Copyright:
© 2022 Association for Computing Machinery.


أدرس بدقة موضوعات البحث “Anonymous Shared Memory'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا