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

Berger, Alon ; Keidar, Idit ; Spiegelman, Alexander

Integrated Bounds for Disintegrated Storage

pdf-format:
LIPIcs-DISC-2018-11.pdf (0.5 MB)

Abstract

We point out a somewhat surprising similarity between non-authenticated Byzantine storage, coded storage, and certain emulations of shared registers from smaller ones. A common characteristic in all of these is the inability of reads to safely return a value obtained in a single atomic access to shared storage. We collectively refer to such systems as disintegrated storage, and show integrated space lower bounds for asynchronous regular wait-free emulations in all of them. In a nutshell, if readers are invisible, then the storage cost of such systems is inherently exponential in the size of written values; otherwise, it is at least linear in the number of readers. Our bounds are asymptotically tight to known algorithms, and thus justify their high costs.

BibTeX - Entry

@InProceedings{berger_et_al:LIPIcs:2018:9800,
  author =	{Alon Berger and Idit Keidar and Alexander Spiegelman},
  title =	{{Integrated Bounds for Disintegrated Storage}},
  booktitle =	{32nd International Symposium on Distributed Computing  (DISC 2018)},
  pages =	{11:1--11:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Ulrich Schmid and Josef Widder},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9800},
  URN =		{urn:nbn:de:0030-drops-98009},
  doi =		{10.4230/LIPIcs.DISC.2018.11},
  annote =	{Keywords: storage, coding, lower bounds, space complexity, register emulations}
}

Keywords: storage, coding, lower bounds, space complexity, register emulations
Collection: 32nd International Symposium on Distributed Computing (DISC 2018)
Issue Date: 2018
Date of publication: 04.10.2018

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