2026-10-03T12:33:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11802 2024-03-06T09:48:49Z ddc:004 open_access

On Deterministic Linearizable Set Agreement Objects de Azevedo Piovezan, Felipe Hadzilacos, Vassos Toueg, Sam Asynchronous shared-memory systems consensus set agreement deterministic objects A recent work showed that, for all n and k, there is a linearizable (n,k)-set agreement object O_L that is equivalent to the (n,k)-set agreement task [David Yu Cheng Chan et al., 2017]: given O_L, it is possible to solve the (n,k)-set agreement task, and given any algorithm that solves the (n,k)-set agreement task (and registers), it is possible to implement O_L. This linearizable object O_L, however, is not deterministic. It turns out that there is also a deterministic (n,k)-set agreement object O_D that is equivalent to the (n,k)-set agreement task, but this deterministic object O_D is not linearizable. This raises the question whether there exists a deterministic and linearizable (n,k)-set agreement object that is equivalent to the (n,k)-set agreement task. Here we show that in general the answer is no: specifically, we prove that for all n ≥ 4, every deterministic linearizable (n,2)-set agreement object is strictly stronger than the (n,2)-set agreement task. We prove this by showing that, for all n ≥ 4, every deterministic and linearizable (n,2)-set agreement object (together with registers) can be used to solve 2-consensus, whereas it is known that the (n,2)-set agreement task cannot do so. For a natural subset of (n,2)-set agreement objects, we prove that this result holds even for n = 3. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Felipe de Azevedo Piovezan and Vassos Hadzilacos and Sam Toueg 2020 Is Part Of LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2019.16 urn:nbn:de:0030-drops-118026 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.16 eng https://creativecommons.org/licenses/by/3.0/legalcode