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.30
URN: urn:nbn:de:0030-drops-80005
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8000/
Go to the corresponding LIPIcs Volume Portal

Jayanti, Prasad ; Joshi, Anup

Recoverable FCFS Mutual Exclusion with Wait-Free Recovery

pdf-format:
LIPIcs-DISC-2017-30.pdf (0.5 MB)

Abstract

Traditional mutual exclusion locks are not resilient to failures: if there is a power outage, the memory is wiped out. Thus, when the system comes back on, the lock will have to be restored to the initial state, i.e., all processes are rolled back to the Remainder section and all variables are reset to their initial values. Recently, Golab and Ramaraju showed that we can improve this state of the art by exploiting the Non-Volatile RAM (NVRAM). They designed algorithms that, by maintaining shared variables in NVRAM, allow processes to recover from crashes on their own without a need for a global reset, even though a crash can wipe out the local memory of a process.

We present a Recoverable Mutual Exclusion algorithm using the commonly supported CAS primitive. The main features of our algorithm are that it satisfies FCFS, it ensures that each process recovers in a wait-free manner, and in the absence of failures, it guarantees a worst-case Remote Memory Reference (RMR) complexity of O(lg n) on both Cache Coherent (CC) and Distributed Shared Memory (DSM) machines, where n is the number of processes for which the algorithm is designed. This bound matches the Omega(lg n) RMR lower bound by Attiya, Hendler, and Woelfel for Mutual Exclusion algorithms that use comparison primitives.

BibTeX - Entry

@InProceedings{jayanti_et_al:LIPIcs:2017:8000,
  author =	{Prasad Jayanti and Anup Joshi},
  title =	{{Recoverable FCFS Mutual Exclusion with Wait-Free Recovery}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{30:1--30:15},
  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/8000},
  URN =		{urn:nbn:de:0030-drops-80005},
  doi =		{10.4230/LIPIcs.DISC.2017.30},
  annote =	{Keywords: concurrent algorithm, synchronization, mutual exclusion, recovery, fault tolerance, non-volatile main memory, shared memory, multi-core algorithms}
}

Keywords: concurrent algorithm, synchronization, mutual exclusion, recovery, fault tolerance, non-volatile main memory, shared memory, multi-core algorithms
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