Set agreement power is not a precise characterization for oblivious deterministic anonymous objects

Gadi Taubenfeld

פרסום מחקרי: פרק בספר / בדוח / בכנספרסום בספר כנסביקורת עמיתים

תקציר

Anonymous shared memory systems, recently introduced in [36], are composed of objects for which there is no a priori agreement between processes on their names. We resolve the following foundational open problems in theoretical distributed computing, for a model which includes both non-anonymous and anonymous shared objects: (1) Are non-trivial oblivious deterministic objects with the same set agreement power have the same computational power? (2) Is there a non-trivial oblivious deterministic object which is strictly weaker than an atomic read/write register? We prove that the answer to the first problem is negative, while the answer to the second problem is positive. The positive answer to the second problem implies that the common belief that every non-trivial deterministic object of consensus number one is at least as strong as atomic read/write registers is false. A noteworthy property of the proofs of our results lies in their simplicity.

שפה מקוריתאנגלית
כותר פרסום המארחStructural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, Proceedings
עורכיםKeren Censor-Hillel, Michele Flammini
מוציא לאורSpringer Verlag
עמודים293-308
מספר עמודים16
מסת"ב (מודפס)9783030249212
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2019
פורסם באופן חיצוניכן
אירוע26th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2019 - L'Aquila, איטליה
משך הזמן: 1 יולי 20194 יולי 2019

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך11639 LNCS
ISSN (מודפס)0302-9743
ISSN (אלקטרוני)1611-3349

כנס

כנס26th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2019
מדינה/אזוראיטליה
עירL'Aquila
תקופה1/07/194/07/19

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

Publisher Copyright:
© Springer Nature Switzerland AG 2019.

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Set agreement power is not a precise characterization for oblivious deterministic anonymous objects'. יחד הם יוצרים טביעת אצבע ייחודית.

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