2026-09-21T08:20:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25177 2026-09-05T19:10:34Z ddc:004 open_access

A Hierarchy of Unrestricted Deterministic Objects with Consensus Number 1 Zhu, Warren Shared Memory Wait-free Set Agreement Consensus Hierarchy The consensus number of a shared object is the maximum number of processes that can solve consensus in a wait-free manner using copies of the object and registers. In 2016, to prove that an object is not fully characterized by its consensus number, Afek, Ellen and Gafni showed that for all integers n ≥ 2, there exists an infinite sequence of deterministic objects of consensus number n with strictly increasing computational power. In 2018, Daian, Losa, Afek, and Gafni constructed an infinite sequence of deterministic objects of consensus number 1 with strictly decreasing computational power, but the single operation that each of these objects supports is restricted in how it can be used during an execution. As restrictions can have an effect on an object’s consensus number, it was left as an open question whether the same result holds without this restriction. In this paper, we construct an infinite sequence of unrestricted deterministic objects with strictly decreasing computational power. All objects in this sequence have consensus number 1. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Warren Zhu 2026 Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2025.4 urn:nbn:de:0030-drops-251778 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.4 eng https://creativecommons.org/licenses/by/4.0/legalcode