DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2023.25

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

Authors: Prasad Jayanti, Siddhartha Jayanti, and Sucharita Jayanti

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract

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.

Cite as

Prasad Jayanti, Siddhartha Jayanti, and Sucharita Jayanti. Durable Algorithms for Writable LL/SC and CAS with Dynamic Joining. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 25:1-25:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{jayanti_et_al:LIPIcs.DISC.2023.25,
  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 =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.25},
  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}
}

Document

DOI: 10.4230/LIPIcs.DISC.2021.25

Fast Arrays: Atomic Arrays with Constant Time Initialization

Authors: Siddhartha Jayanti and Julian Shun

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract

Some algorithms require a large array, but only operate on a small fraction of its indices. Examples include adjacency matrices for sparse graphs, hash tables, and van Emde Boas trees. For such algorithms, array initialization can be the most time-consuming operation. Fast arrays were invented to avoid this costly initialization. A fast array is a software implementation of an array, such that the entire array can be initialized in just constant time. While algorithms for sequential fast arrays have been known for a long time, to the best of our knowledge, there are no previous algorithms for concurrent fast arrays. We present the first such algorithms in this paper. Our first algorithm is linearizable and wait-free, uses only linear space, and supports all operations - initialize, read, and write - in constant time. Our second algorithm enhances the first to additionally support all the read-modify-write operations available in hardware (such as compare-and-swap) in constant time.

Cite as

Siddhartha Jayanti and Julian Shun. Fast Arrays: Atomic Arrays with Constant Time Initialization. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{jayanti_et_al:LIPIcs.DISC.2021.25,
  author =	{Jayanti, Siddhartha and Shun, Julian},
  title =	{{Fast Arrays: Atomic Arrays with Constant Time Initialization}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.25},
  URN =		{urn:nbn:de:0030-drops-148278},
  doi =		{10.4230/LIPIcs.DISC.2021.25},
  annote =	{Keywords: fast array, linearizable, wait-free, asynchronous, multiprocessor, constant time, space efficient, data structure}
}

Search Results

Documents authored by Jayanti, Siddhartha

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

Abstract

Cite as

Fast Arrays: Atomic Arrays with Constant Time Initialization

Abstract

Cite as

Thanks for your feedback!

Could not send message