License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2017.50
URN: urn:nbn:de:0030-drops-79689
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7968/
Go to the corresponding LIPIcs Volume Portal

Friedman, Michal ; Herlihy, Maurice ; Marathe, Virendra ; Petrank, Erez

Brief Announcement: A Persistent Lock-Free Queue for Non-Volatile Memory

pdf-format:
LIPIcs-DISC-2017-50.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{friedman_et_al:LIPIcs:2017:7968,
  author =	{Michal Friedman and Maurice Herlihy and Virendra Marathe and Erez Petrank},
  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 =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7968},
  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}
}

Keywords: Non-volatile Memory, Concurrent Data Structures, Non-blocking, Lock-free
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI