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.2017.9
URN: urn:nbn:de:0030-drops-86290
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8629/
Go to the corresponding LIPIcs Volume Portal

Imbs, Damien ; Kuznetsov, Petr ; Rieutord, Thibault

Progress-Space Tradeoffs in Single-Writer Memory Implementations

pdf-format:
LIPIcs-OPODIS-2017-9.pdf (0.6 MB)

Abstract

Many algorithms designed for shared-memory distributed systems assume the single-writer multi- reader (SWMR) setting where each process is provided with a unique register that can only be written by the process and read by all. In a system where computation is performed by a bounded number n of processes coming from a large (possibly unbounded) set of potential participants, the assumption of an SWMR memory is no longer reasonable. If only a bounded number of multi- writer multi-reader (MWMR) registers are provided, we cannot rely on an a priori assignment of processes to registers. In this setting, implementing an SWMR memory, or equivalently, ensuring stable writes (i.e., every written value persists in the memory), is desirable.
In this paper, we propose an SWMR implementation that adapts the number of MWMR registers used to the desired progress condition. For any given k from 1 to n, we present an algorithm that uses n + k − 1 registers to implement a k-lock-free SWMR memory. In the special case of 2-lock-freedom, we also give a matching lower bound of n + 1 registers, which supports our conjecture that the algorithm is space-optimal. Our lower bound holds for the strictly weaker progress condition of 2-obstruction-freedom, which suggests that the space complexity for k-obstruction-free and k-lock-free SWMR implementations might coincide.

BibTeX - Entry

@InProceedings{imbs_et_al:LIPIcs:2018:8629,
  author =	{Damien Imbs and Petr Kuznetsov and Thibault Rieutord},
  title =	{{Progress-Space Tradeoffs in Single-Writer Memory Implementations}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{James Aspnes and Alysson Bessani and Pascal Felber and Jo{\~a}o Leit{\~a}o},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8629},
  URN =		{urn:nbn:de:0030-drops-86290},
  doi =		{10.4230/LIPIcs.OPODIS.2017.9},
  annote =	{Keywords: Single-writer memory implementation, comparison-based algorithms, space complexity, progress conditions}
}

Keywords: Single-writer memory implementation, comparison-based algorithms, space complexity, progress conditions
Collection: 21st International Conference on Principles of Distributed Systems (OPODIS 2017)
Issue Date: 2018
Date of publication: 28.03.2018

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