## תקציר

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 יולי 2019 → 4 יולי 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/19 → 4/07/19 |

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

Publisher Copyright:© Springer Nature Switzerland AG 2019.