תקציר
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 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 1989 |
פורסם באופן חיצוני | כן |
אירוע | 3rd International Workshop on Distributed Algorithms, WDAG 1989 - Nice, צרפת משך הזמן: 26 ספט׳ 1989 → 28 ספט׳ 1989 |
סדרות פרסומים
שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
כרך | 392 LNCS |
ISSN (מודפס) | 0302-9743 |
ISSN (אלקטרוני) | 1611-3349 |
כנס
כנס | 3rd International Workshop on Distributed Algorithms, WDAG 1989 |
---|---|
מדינה/אזור | צרפת |
עיר | Nice |
תקופה | 26/09/89 → 28/09/89 |
הערה ביבליוגרפית
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1989.