2024/02/21 by Hagit Attiya, Attiya, Hagit, Armando Castañeda +3 · 1 citation
Computer Science · #Advanced Algebra and Logic #Computability, Logic, AI Algorithms #Distributed #FOS: Computer and information sciences #Logic, Reasoning, and Knowledge #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2402.13618
openalex publication_date 2024/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A powerful tool for designing complex concurrent programs is through composition with object implementations from lower-level primitives. Strongly-linearizable implementations allow to preserve hyper-properties, e.g., probabilistic guarantees of randomized programs. However, the only known wait-free strongly-linearizable implementations for many objects rely on compare&swap, a universal primitive that allows any number of processes to solve consensus. This is despite the fact that these objects have wait-free linearizable implementations from read / write primitives, which do not support consensus. This paper investigates a middle-ground, asking whether there are wait-free strongly-linearizable implementations from realistic primitives such as test&set or fetch&add, whose consensus number is 2. We show that many objects with consensus number 1 have wait-free strongly-linearizable implementations from fetch&add. We also show that several objects with consensus number 2 have wait-free or lock-free implementations from other objects with consensus number 2. In contrast, we prove that even when fetch&add, swap and test&set primitives are used, some objects with consensus number 2 do not have lock-free strongly-linearizable implementations. This includes queues and stacks, as well as relaxed variants thereof.