ملخص
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
!!Conference | 3rd International Workshop on Distributed Algorithms, WDAG 1989 |
---|---|
الدولة/الإقليم | فرنسا |
المدينة | Nice |
المدة | ٢٦/٠٩/٨٩ → ٢٨/٠٩/٨٩ |
ملاحظة ببليوغرافية
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1989.