License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2019.16
URN: urn:nbn:de:0030-drops-118026
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11802/
de Azevedo Piovezan, Felipe ;
Hadzilacos, Vassos ;
Toueg, Sam
On Deterministic Linearizable Set Agreement Objects
Abstract
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.
BibTeX - Entry
@InProceedings{deazevedopiovezan_et_al:LIPIcs:2020:11802,
author = {Felipe de Azevedo Piovezan and Vassos Hadzilacos and Sam Toueg},
title = {{On Deterministic Linearizable Set Agreement Objects}},
booktitle = {23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
pages = {16:1--16:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-133-7},
ISSN = {1868-8969},
year = {2020},
volume = {153},
editor = {Pascal Felber and Roy Friedman and Seth Gilbert and Avery Miller},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11802},
URN = {urn:nbn:de:0030-drops-118026},
doi = {10.4230/LIPIcs.OPODIS.2019.16},
annote = {Keywords: Asynchronous shared-memory systems, consensus, set agreement, deterministic objects}
}
|
Keywords: |
|
Asynchronous shared-memory systems, consensus, set agreement, deterministic objects |
|
Collection: |
|
23rd International Conference on Principles of Distributed Systems (OPODIS 2019) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
11.02.2020 |
