DROPS

Document

DOI: 10.4230/LIPIcs.OPODIS.2021.29

Recoverable and Detectable Fetch&Add

Authors: Liad Nahum, Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)

Abstract

The emergence of systems with non-volatile main memory (NVRAM) increases the need for persistent concurrent objects. Of specific interest are recoverable implementations that, in addition to being robust to crash-failures, are also detectable. Detectability ensures that upon recovery, it is possible to infer whether the failed operation took effect or not and, in the former case, obtain its response. This work presents two recoverable detectable Fetch&Add (FAA) algorithms that are self-implementations, i.e, use only a fetch&add base object, in addition to read/write registers. The algorithms target two different models for recovery: the global-crash model and the individual-crash model. In both algorithms, operations are wait-free when there are no crashes, but the recovery code may block if there are repeated failures. We also prove that in the individual-crash model, there is no implementation of recoverable and detectable FAA using only read, write and fetch&add primitives in which all operations, including recovery, are lock-free.

Cite as

Liad Nahum, Hagit Attiya, Ohad Ben-Baruch, and Danny Hendler. Recoverable and Detectable Fetch&Add. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{nahum_et_al:LIPIcs.OPODIS.2021.29,
  author =	{Nahum, Liad and Attiya, Hagit and Ben-Baruch, Ohad and Hendler, Danny},
  title =	{{Recoverable and Detectable Fetch\&Add}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.29},
  URN =		{urn:nbn:de:0030-drops-158043},
  doi =		{10.4230/LIPIcs.OPODIS.2021.29},
  annote =	{Keywords: Multi-core algorithms, persistent memory, non-volatile memory}
}

Search Results

Documents authored by Ben-Baruch, Ohad

Recoverable and Detectable Fetch&Add

Abstract

Cite as

Thanks for your feedback!

Could not send message