1 Search Results for "Berger, Alon"

Document
DOI: 10.4230/LIPIcs.DISC.2018.11
Integrated Bounds for Disintegrated Storage

Authors: Alon Berger, Idit Keidar, and Alexander Spiegelman

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

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.
Cite as

Alon Berger, Idit Keidar, and Alexander Spiegelman. Integrated Bounds for Disintegrated Storage. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 11:1-11:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:LIPIcs.DISC.2018.11,
  author =	{Berger, Alon and Keidar, Idit and Spiegelman, Alexander},
  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 =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.11},
  URN =		{urn:nbn:de:0030-drops-98009},
  doi =		{10.4230/LIPIcs.DISC.2018.11},
  annote =	{Keywords: storage, coding, lower bounds, space complexity, register emulations}
}
  • Refine by Author
  • 1 Berger, Alon
  • 1 Keidar, Idit
  • 1 Spiegelman, Alexander

  • Refine by Classification
  • 1 Computing methodologies → Distributed algorithms
  • 1 Theory of computation → Distributed computing models

  • Refine by Keyword
  • 1 coding
  • 1 lower bounds
  • 1 register emulations
  • 1 space complexity
  • 1 storage

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact