Metraipolis › archive › dc_86de15fe6bdd
Efficient Randomized LL/SC that Preserves History Independence — arXiv:2608.12946
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2608.12946
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-19T04:24:46.439Z
- SHA-256 of the archived text
7f5c05db040919c8159ea03b86ce696518fc4d3d1a26d564d08b10a517781488- Stable URL of this page
https://metraipolis.com/documento/dc_86de15fe6bdd
How to cite
Efficient Randomized LL/SC that Preserves History Independence — arXiv:2608.12946 — arXiv (en), https://arxiv.org/abs/2608.12946 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_86de15fe6bdd (Metraipolis archive dc_86de15fe6bdd, sha256 7f5c05db040919c8159ea03b86ce696518fc4d3d1a26d564d08b10a517781488)
BibTeX
@misc{dc86de15fe6bdd,
title = {Efficient Randomized LL/SC that Preserves History Independence — arXiv:2608.12946},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2608.12946},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_86de15fe6bdd; sha256 7f5c05db040919c8159ea03b86ce696518fc4d3d1a26d564d08b10a517781488},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.12946. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study the fundamental problem of implementing $m$ linearizable LL/SC objects with constant expected step complexity in a system of $n$ processes, using bounded base objects commonly available in hardware. Assuming that each process may have at most $\tau$ outstanding LL() operations, the best known deterministic algorithm requires $\Omega(n^2\tau + m)$ base objects (CAS objects and registers) [Blelloch and Wei, DISC 2020]. Previously, no comparable randomized algorithm was known. By employing randomization and FADD objects in addition to CAS objects, we obtain a space bound of $O(n\tau+m)$ against the weak adaptive adversary. For $m=O(1)$ this matches a lower bound for algorithms using CAS objects and registers [Aghazadeh and Woelfel, PODC 2015]. In addition, our object can be employed by quiescently history-independent (QHI) algorithms: Whenever no operation on the object is pending and no process has an outstanding LL() operation, its internal memory state is uniquely determined by the values of the $m$ LL/SC objects. An important application is a recent QHI dynamic hashing algorithm, which uses $\Theta(m)$ hardware LL/SC objects to maintain a hash table of size $m$ [Attiya, Bender, Farach-Colton, Oshman, and Schiller, STOC 2025]. But LL/SC is not available in hardware, and prior to our work no wait-free or efficient lock-free software implementation of LL/SC with similar properties was known. Our work demonstrates that one can actually implement the hashing algorithm on available hardware, without an asymptotic increase in step and space complexity, under the reasonable assumption that $m=\Omega(n)$. Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-08-14 in cs.DC). Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Data Structures and Algorithms (cs.DS). Pagina del lavoro: https://arxiv.org/abs/2608.12946 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-19T04:17:59.924Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-08-14?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).