Strong Linearizability using Primitives with Consensus Number 2
<|reference_start|>Strong Linearizability using Primitives with Consensus Number 2: 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.<|reference_end|>
@article{attiya2024strong,
    title={Strong Linearizability using Primitives with Consensus Number 2},
    author={Hagit Attiya, Armando Casta~neda, Constantin Enea},
    journal={arXiv preprint arXiv:2402.13618},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.13618},
    primaryClass={cs.DC}
}