Search Results

Documents authored by Lev Lehman, Tomer

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.24
Recoverable and Detectable Self-Implementations of Swap

Authors: Tomer Lev Lehman, Hagit Attiya, and Danny Hendler

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
Recoverable algorithms tolerate failures and recoveries of processes by using non-volatile memory. Of particular interest are self-implementations of key operations, in which a recoverable operation is implemented from its non-recoverable counterpart (in addition to reads and writes). This paper presents two self-implementations of the swap operation. One works in the system-wide failures model, where all processes fail and recover together, and the other in the independent failures model, where each process crashes and recovers independently of the other processes. Both algorithms are wait-free in crash-free executions, but their recovery code is blocking. We prove that this is inherent for the independent failures model. The impossibility result is proved for implementations of distinguishable operations using interfering functions, and in particular, it applies to a recoverable self-implementation of swap.
Cite as

Tomer Lev Lehman, Hagit Attiya, and Danny Hendler. Recoverable and Detectable Self-Implementations of Swap. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 24:1-24:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{levlehman_et_al:LIPIcs.OPODIS.2023.24,
  author =	{Lev Lehman, Tomer and Attiya, Hagit and Hendler, Danny},
  title =	{{Recoverable and Detectable Self-Implementations of Swap}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{24:1--24:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.24},
  URN =		{urn:nbn:de:0030-drops-195140},
  doi =		{10.4230/LIPIcs.OPODIS.2023.24},
  annote =	{Keywords: Multi-core algorithms, persistent memory, non-volatile memory, recoverable objects, detectablitly}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.44
Brief Announcement: Recoverable and Detectable Self-Implementations of Swap

Authors: Tomer Lev Lehman, Hagit Attiya, and Danny Hendler

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

Abstract
Recoverable algorithms tolerate failures and recoveries of processes by using non-volatile memory. Of particular interest are self-implementations of key operations, in which a recoverable operation is implemented from its non-recoverable counterpart (in addition to reads and writes). This paper presents two self-implementations of the SWAP operation. One works in the system-wide failures model, where all processes fail and recover together, and the other in the independent failures model, where each process crashes and recovers independently of the other processes. Both algorithms are wait-free in crash-free executions, but their recovery code is blocking. We prove that this is inherent for the independent failures model. The impossibility result is proved for implementations of distinguishable operations using interfering functions, and in particular, it applies to a recoverable self-implementation of swap.
Cite as

Tomer Lev Lehman, Hagit Attiya, and Danny Hendler. Brief Announcement: Recoverable and Detectable Self-Implementations of Swap. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 44:1-44:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{levlehman_et_al:LIPIcs.DISC.2023.44,
  author =	{Lev Lehman, Tomer and Attiya, Hagit and Hendler, Danny},
  title =	{{Brief Announcement: Recoverable and Detectable Self-Implementations of Swap}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{44:1--44:7},
  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.44},
  URN =		{urn:nbn:de:0030-drops-191704},
  doi =		{10.4230/LIPIcs.DISC.2023.44},
  annote =	{Keywords: Persistent memory, non-volatile memory, recoverable objects, detectablitly}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact