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.OPODIS.2015.20
URN: urn:nbn:de:0030-drops-66116
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6611/
Go to the corresponding LIPIcs Volume Portal

Berryhill, Ryan ; Golab, Wojciech ; Tripunitara, Mahesh

Robust Shared Objects for Non-Volatile Main Memory

pdf-format:
LIPIcs-OPODIS-2015-20.pdf (0.8 MB)

Abstract

Research in concurrent in-memory data structures has focused almost exclusively on models where processes are either reliable, or may fail by crashing permanently. The case where processes may recover from failures has received little attention because recovery from conventional volatile memory is impossible in the event of a system crash, during which both the state of main memory and the private states of processes are lost. Future hardware architectures are likely to include various forms of non-volatile random access memory (NVRAM), creating new opportunities to design robust main memory data structures that can recover from system crashes. In this paper we advance the theoretical foundations of such data structures in two ways. First, we review several known variations of Herlihy and Wing's linearizability property that were proposed in the context of message passing systems but also apply in our NVRAM-based model, we discuss the limitations of these properties with respect to our specific goals, and we propose an alternative correctness condition called recoverable linearizability. Second, we discuss techniques for implementing shared objects that satisfy such properties with a focus on wait-free implementations. Specifically, we demonstrate how to achieve different variations of linearizability in our model by transforming two classic wait-free constructions.

BibTeX - Entry

@InProceedings{berryhill_et_al:LIPIcs:2016:6611,
  author =	{Ryan Berryhill and Wojciech Golab and Mahesh Tripunitara},
  title =	{{Robust Shared Objects for Non-Volatile Main Memory}},
  booktitle =	{19th International Conference on Principles of Distributed Systems (OPODIS 2015)},
  pages =	{1--17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-98-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{46},
  editor =	{Emmanuelle Anceaume and Christian Cachin and Maria Potop-Butucaru},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6611},
  URN =		{urn:nbn:de:0030-drops-66116},
  doi =		{10.4230/LIPIcs.OPODIS.2015.20},
  annote =	{Keywords: non-volatile main memory, concurrency, recovery, data structures}
}

Keywords: non-volatile main memory, concurrency, recovery, data structures
Collection: 19th International Conference on Principles of Distributed Systems (OPODIS 2015)
Issue Date: 2016
Date of publication: 13.10.2016

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