2 Search Results for "Marathe, Virendra"

Document
DOI: 10.4230/LIPIcs.DISC.2020.4
Efficient Multi-Word Compare and Swap

Authors: Rachid Guerraoui, Alex Kogan, Virendra J. Marathe, and Igor Zablotchi

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Atomic lock-free multi-word compare-and-swap (MCAS) is a powerful tool for designing concurrent algorithms. Yet, its widespread usage has been limited because lock-free implementations of MCAS make heavy use of expensive compare-and-swap (CAS) instructions. Existing MCAS implementations indeed use at least 2k+1 CASes per k-CAS. This leads to the natural desire to minimize the number of CASes required to implement MCAS. We first prove in this paper that it is impossible to "pack" the information required to perform a k-word CAS (k-CAS) in less than k locations to be CASed. Then we present the first algorithm that requires k+1 CASes per call to k-CAS in the common uncontended case. We implement our algorithm and show that it outperforms a state-of-the-art baseline in a variety of benchmarks in most considered workloads. We also present a durably linearizable (persistent memory friendly) version of our MCAS algorithm using only 2 persistence fences per call, while still only requiring k+1 CASes per k-CAS.
Cite as

Rachid Guerraoui, Alex Kogan, Virendra J. Marathe, and Igor Zablotchi. Efficient Multi-Word Compare and Swap. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{guerraoui_et_al:LIPIcs.DISC.2020.4,
  author =	{Guerraoui, Rachid and Kogan, Alex and Marathe, Virendra J. and Zablotchi, Igor},
  title =	{{Efficient Multi-Word Compare and Swap}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{4:1--4:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.4},
  URN =		{urn:nbn:de:0030-drops-130827},
  doi =		{10.4230/LIPIcs.DISC.2020.4},
  annote =	{Keywords: lock-free, multi-word compare-and-swap, persistent memory}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2017.50
Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory

Authors: Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank

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

Abstract
Non-volatile memory is expected to coexist with (or even displace) volatile DRAM for main memory in upcoming architectures. As a result, there is increasing interest in the problem of designing and specifying durable data structures that can recover from system crashes. Data-structures may be designed to satisfy stricter or weaker durability guarantees to provide a balance between the strength of the provided guarantees and performance overhead. This paper proposes three novel implementations of a concurrent lock-free queue. These implementations illustrate the algorithmic challenges in building persistent lock-free data structures with different levels of durability guarantees. We believe that by presenting these challenges, along with the proposed algorithmic designs, and the possible levels of durability guarantees, we can shed light on avenues for building a wide variety of durable data structures. We implemented the various designs and evaluate their performance overhead compared to a simple queue design for standard (volatile) memory.
Cite as

Michal Friedman, Maurice Herlihy, Virendra Marathe, and Erez Petrank. Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 50:1-50:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{friedman_et_al:LIPIcs.DISC.2017.50,
  author =	{Friedman, Michal and Herlihy, Maurice and Marathe, Virendra and Petrank, Erez},
  title =	{{Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{50:1--50:4},
  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.50},
  URN =		{urn:nbn:de:0030-drops-79689},
  doi =		{10.4230/LIPIcs.DISC.2017.50},
  annote =	{Keywords: Non-volatile Memory, Concurrent Data Structures, Non-blocking, Lock-free}
}
  • Refine by Author
  • 1 Friedman, Michal
  • 1 Guerraoui, Rachid
  • 1 Herlihy, Maurice
  • 1 Kogan, Alex
  • 1 Marathe, Virendra
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Concurrent algorithms

  • Refine by Keyword
  • 1 Concurrent Data Structures
  • 1 Lock-free
  • 1 Non-blocking
  • 1 Non-volatile Memory
  • 1 lock-free
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2017
  • 1 2020

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 Imprint Privacy Contact