Life Beyond Set Agreement
| Autor: | David Yu Cheng Chan, Vassos Hadzilacos, Sam Toueg |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Discrete mathematics
Sequence Asynchronous system Hierarchy (mathematics) Computer Networks and Communications media_common.quotation_subject 020207 software engineering 0102 computer and information sciences 02 engineering and technology Object (computer science) 01 natural sciences Agreement Theoretical Computer Science Set (abstract data type) Computational Theory and Mathematics Shared memory Hardware and Architecture 010201 computation theory & mathematics Theory of computation 0202 electrical engineering electronic engineering information engineering Computer communication networks Shared object media_common Mathematics |
| Zdroj: | PODC |
| DOI: | 10.1145/3087801.3087822 |
| Popis: | The set agreement power of a shared object O describes O’s ability to solve set agreement problems: it is the sequence $$(n_1, n_2, {\ldots }, n_k, {\ldots })$$ such that, for every $$k\ge 1$$, using O and registers one can solve the k-set agreement problem among at most $$n_k$$ processes. It has been shown that the ability of an object O to implement other objects is not fully characterized by its consensus number (the first component of its set agreement power). This raises the following natural question: is the ability of an object O to implement other objects fully characterized by its set agreement power? We prove that the answer is no: every level $$n \ge 2$$ of Herlihy’s consensus hierarchy has two linearizable objects that have the same set agreement power but are not equivalent, i.e., at least one cannot implement the other. We also show that every level $$n \ge 2$$ of the consensus hierarchy contains a deterministic linearizable object $$O_n$$ with some set agreement power $$(n_1,n_2,\ldots ,n_k,\ldots )$$ such that being able to solve the k-set agreement problems among $$n_k$$ processes, for all $$k\ge 1$$, is not enough to implement $$O_n$$. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|