2026-07-23T04:32:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25194 2026-03-19T12:59:27Z ddc:004 open_access

Solving Tasks with Fewer Registers Than Processes Gafni, Eli Losa, Giuliano Raynal, Michel Taubenfeld, Gadi Asynchrony Read/write registers Wait-freedom Tasks Covering argument Lower bound Space complexity Anonymous Processes Anonymous Memory This paper studies distributed-computing tasks through the lens of space complexity in the read/write wait-free model, defined as the number of multi-reader-multi-writer atomic read/write registers needed to solve a task using a wait-free algorithm. Surprisingly, even though the read/write wait-free model is at the foundation of distributed computing, previous work on space complexity has focused on synchronization primitives stronger than read/write registers or on weaker progress conditions. The paper reveals that the read/write wait-free model offers a rich space-complexity landscape: (1) assuming non-anonymous processes, it shows that there is an infinite hierarchy of tasks of increasing space complexity; (2) it shows that space complexity separates anonymous from non-anonymous memory; (3) regardless of process or register anonymity, it exhibits a task of space complexity two, which is the minimal non-trivial space complexity; (4) finally, it shows that subcases of the adopt-commit task have different space complexity in non-anonymous memory under bounded wait-freedom. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Eli Gafni and Giuliano Losa and Michel Raynal and Gadi Taubenfeld 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.21 urn:nbn:de:0030-drops-251947 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.21 eng https://creativecommons.org/licenses/by/4.0/legalcode