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.2017.30

Recoverable FCFS Mutual Exclusion with Wait-Free Recovery

Authors: Prasad Jayanti and Anup Joshi

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract

Traditional mutual exclusion locks are not resilient to failures: if there is a power outage, the memory is wiped out. Thus, when the system comes back on, the lock will have to be restored to the initial state, i.e., all processes are rolled back to the Remainder section and all variables are reset to their initial values. Recently, Golab and Ramaraju showed that we can improve this state of the art by exploiting the Non-Volatile RAM (NVRAM). They designed algorithms that, by maintaining shared variables in NVRAM, allow processes to recover from crashes on their own without a need for a global reset, even though a crash can wipe out the local memory of a process. We present a Recoverable Mutual Exclusion algorithm using the commonly supported CAS primitive. The main features of our algorithm are that it satisfies FCFS, it ensures that each process recovers in a wait-free manner, and in the absence of failures, it guarantees a worst-case Remote Memory Reference (RMR) complexity of O(lg n) on both Cache Coherent (CC) and Distributed Shared Memory (DSM) machines, where n is the number of processes for which the algorithm is designed. This bound matches the Omega(lg n) RMR lower bound by Attiya, Hendler, and Woelfel for Mutual Exclusion algorithms that use comparison primitives.

Cite as

Prasad Jayanti and Anup Joshi. Recoverable FCFS Mutual Exclusion with Wait-Free Recovery. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jayanti_et_al:LIPIcs.DISC.2017.30,
  author =	{Jayanti, Prasad and Joshi, Anup},
  title =	{{Recoverable FCFS Mutual Exclusion with Wait-Free Recovery}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.30},
  URN =		{urn:nbn:de:0030-drops-80005},
  doi =		{10.4230/LIPIcs.DISC.2017.30},
  annote =	{Keywords: concurrent algorithm, synchronization, mutual exclusion, recovery, fault tolerance, non-volatile main memory, shared memory, multi-core algorithms}
}

Search Results

Documents authored by Jayanti, Prasad

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

Abstract

Cite as

Recoverable FCFS Mutual Exclusion with Wait-Free Recovery

Abstract

Cite as

Thanks for your feedback!

Could not send message