Possibility and impossibility results in a shared memory environment

Gadi Taubenfeld, Shlomo Moran

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

We focus on unreliable asynchronous shared memory model which support only atomic read and write operations. For such a model we provide a necessary condition for the solvability of problems in the presence of multiple undetectable crash failures. Also, by using game-theoretical notions, a necessary and sufficient condition is provided, for the solvability of problems in the presence of multiple undetectable initial failures (i.e., processes may fail only prior to the execution). Our results imply that many problems such as consensus, choosing a leader, ranking, matching and sorting are unsolvable in the presence of a single crash failure, and that variants of these problems are solvable in the presence of a single crash failure, and that variants of these problems are solvable in the presence of t-1 crash failures but not in the presence of t crash failures. We show that a shared memory model can simulate various message passing models, and hence our impossibility results hold also for those message passing models. Our results extend and generalize previously known impossibility results for various asynchronous models.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفDistributed Algorithms - 3rd International Workshop, Proceedings
المحررونJean-Claude Bermond, Michel Raynal
ناشرSpringer Verlag
الصفحات254-267
عدد الصفحات14
رقم المعيار الدولي للكتب (المطبوع)9783540516873
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 1989
منشور خارجيًانعم
الحدث3rd International Workshop on Distributed Algorithms, WDAG 1989 - Nice, فرنسا
المدة: ٢٦ سبتمبر ١٩٨٩٢٨ سبتمبر ١٩٨٩

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت392 LNCS
رقم المعيار الدولي للدوريات (المطبوع)0302-9743
رقم المعيار الدولي للدوريات (الإلكتروني)1611-3349

!!Conference

!!Conference3rd International Workshop on Distributed Algorithms, WDAG 1989
الدولة/الإقليمفرنسا
المدينةNice
المدة٢٦/٠٩/٨٩٢٨/٠٩/٨٩

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

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1989.

بصمة

أدرس بدقة موضوعات البحث “Possibility and impossibility results in a shared memory environment'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا