License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2023.25
URN: urn:nbn:de:0030-drops-191510
Go to the corresponding LIPIcs Volume Portal

Jayanti, Prasad ; Jayanti, Siddhartha ; Jayanti, Sucharita

Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining

LIPIcs-DISC-2023-25.pdf (0.8 MB)


We present durable implementations for two well known universal primitives - CAS (compare-and-swap), and its ABA-free counter-part LLSC (load-linked, store-conditional). Our implementations satisfy method-based recoverable linearizability (MRL) and method-based detectability (M-detectability) - novel correctness conditions that require only a simple usage pattern to guarantee resilience to individual process crashes (and system-wide crashes), including in implementations with nesting. Additionally, our implementations are: writable, meaning they support a Write() operation; have constant time complexity per operation; allow for dynamic joining, meaning newly created processes (a.k.a. threads) of arbitrary names can join a protocol and access our implementations; and have adaptive space complexity, meaning the space use scales in the number of processes n that actually use the objects, as opposed to previous protocols whose space complexity depends on N, the maximum number of processes that the protocol is designed for. Our durable Writable-CAS implementation, DuraCAS, requires O(m + n) space to support m objects that get accessed by n processes, improving on the state-of-the-art O(m + N²). By definition, LLSC objects must store "contexts" in addition to object values. Our Writable-LLSC implementation, DuraLL, requires O(m + n + C) space, where C is the number of "contexts" stored across all the objects. While LLSC has an advantage over CAS due to being ABA-free, the object definition seems to require additional space usage. To address this trade-off, we define an External Context (EC) variant of LLSC. Our EC Writable-LLSC implementation is ABA-free and has a space complexity of just O(m + n).

To our knowledge, our algorithms are the first durable CAS algorithms that allow for dynamic joining, and are the first to exhibit adaptive space complexity. To our knowledge, we are the first to implement any type of durable LLSC objects.

BibTeX - Entry

  author =	{Jayanti, Prasad and Jayanti, Siddhartha and Jayanti, Sucharita},
  title =	{{Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{25:1--25:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-191510},
  doi =		{10.4230/LIPIcs.DISC.2023.25},
  annote =	{Keywords: durable, recoverable, detectable, persistent memory, dynamic joining, LL/SC, CAS}

Keywords: durable, recoverable, detectable, persistent memory, dynamic joining, LL/SC, CAS
Collection: 37th International Symposium on Distributed Computing (DISC 2023)
Issue Date: 2023
Date of publication: 05.10.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI