2026-07-22T07:15:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9806 2024-03-06T10:44:58Z ddc:004 open_access

A Wealth of Sub-Consensus Deterministic Objects Daian, Eli Losa, Giuliano Afek, Yehuda Gafni, Eli shared memory distributed algorithms wait-free set consensus The consensus hierarchy classifies shared an object according to its consensus number, which is the maximum number of processes that can solve consensus wait-free using the object. The question of whether this hierarchy is precise enough to fully characterize the synchronization power of deterministic shared objects was open until 2016, when Afek et al. showed that there is an infinite hierarchy of deterministic objects, each weaker than the next, which is strictly between i and i+1-processors consensus, for i >= 2. For i=1, the question whether there exist a deterministic object whose power is strictly between read-write and 2-processors consensus, remained open. We resolve the question positively by exhibiting an infinite hierarchy of simple deterministic objects which are equivalent to set-consensus tasks, and thus are stronger than read-write registers, but they cannot implement consensus for two processes. Still our paper leaves a gap with open questions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eli Daian and Giuliano Losa and Yehuda Afek and Eli Gafni 2018 Is Part Of LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2018.17 urn:nbn:de:0030-drops-98061 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.17 eng https://creativecommons.org/licenses/by/3.0/legalcode