2026-07-21T14:19:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11310 2024-03-06T10:47:54Z ddc:004 open_access

Long-Lived Counters with Polylogarithmic Amortized Step Complexity Baig, Mirza Ahad Hendler, Danny Milani, Alessia Travers, Corentin Shared Memory Wait-freedom Counter Amortized Complexity Concurrent Objects A shared-memory counter is a well-studied and widely-used concurrent object. It supports two operations: An Inc operation that increases its value by 1 and a Read operation that returns its current value. Jayanti, Tan and Toueg [Jayanti et al., 2000] proved a linear lower bound on the worst-case step complexity of obstruction-free implementations, from read and write operations, of a large class of shared objects that includes counters. The lower bound leaves open the question of finding counter implementations with sub-linear amortized step complexity. In this paper, we address this gap. We present the first wait-free n-process counter, implemented using only read and write operations, whose amortized operation step complexity is O(log^2 n) in all executions. This is the first non-blocking read/write counter algorithm that provides sub-linear amortized step complexity in executions of arbitrary length. Since a logarithmic lower bound on the amortized step complexity of obstruction-free counter implementations exists, our upper bound is optimal up to a logarithmic factor. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mirza Ahad Baig and Danny Hendler and Alessia Milani and Corentin Travers 2019 Is Part Of LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2019.3 urn:nbn:de:0030-drops-113108 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.3 eng https://creativecommons.org/licenses/by/3.0/legalcode