2026-07-22T16:58:52Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6679 2024-03-06T10:36:52Z ddc:004 open_access

Poly-Logarithmic Adaptive Algorithms Require Unconditional Primitives Attiya, Hagit Fouren, Arie collect atomic snapshot renaming fetch&inc compare&swap This paper studies the step complexity of adaptive algorithms using primitives stronger than reads and writes. We first consider unconditional primitives, like fetch&inc, which modify the value of the register to which they are applied, regardless of its current value. Unconditional primitives admit snapshot algorithms with O(log(k)) step complexity, where k is the total or the point contention. These algorithms combine a renaming algorithm with a mechanism for propagating values so they can be quickly collected. When only conditional primitives, e.g., compare&swap or LL/SC, are used (in addition to reads and writes), we show that any collect algorithm must perform Omega(k) steps, in an execution with total contention k in O(log(log(n))). The lower bound applies for snapshot and renaming, both one-shot and long-lived. Note that there are snapshot algorithms whose step complexity is polylogarithmic in n using only reads and writes, but there are no adaptive algorithms whose step complexity is polylogarithmic in the contention, even when compare&swap and LL/SC are used. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hagit Attiya and Arie Fouren 2016 Is Part Of LIPIcs, Volume 46, 19th International Conference on Principles of Distributed Systems (OPODIS 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2015.36 urn:nbn:de:0030-drops-66793 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2015.36 eng https://creativecommons.org/licenses/by/3.0/legalcode