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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 1989
פורסם באופן חיצוניכן
אירוע3rd International Workshop on Distributed Algorithms, WDAG 1989 - Nice, צרפת
משך הזמן: 26 ספט׳ 198928 ספט׳ 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/8928/09/89

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

Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1989.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Possibility and impossibility results in a shared memory environment'. יחד הם יוצרים טביעת אצבע ייחודית.

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