2026-07-26T02:42:33Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11804 2024-03-06T10:48:49Z ddc:004 open_access

An Efficient Universal Construction for Large Objects Fatourou, Panagiota Kallimanis, Nikolaos D. Kanellou, Eleni universal construction concurrent object shared memory simulation wait-freedom large object This paper presents L-UC, a universal construction that efficiently implements dynamic objects of large state in a wait-free manner. The step complexity of L-UC is O(n+kw), where n is the number of processes, k is the interval contention (i.e., the maximum number of active processes during the execution interval of an operation), and w is the worst-case time complexity to perform an operation on the sequential implementation of the simulated object. L-UC efficiently implements objects whose size can change dynamically. It improves upon previous universal constructions either by efficiently handling objects whose state is large and can change dynamically, or by achieving better step complexity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Panagiota Fatourou and Nikolaos D. Kallimanis and Eleni Kanellou 2020 Is Part Of LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2019.18 urn:nbn:de:0030-drops-118049 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.18 eng https://creativecommons.org/licenses/by/3.0/legalcode