2 Search Results for "Berger, Josef"

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}
}
Document
DOI: 10.4230/OASIcs.CCA.2009.2259
A Constructive Study of Landau's Summability Theorem

Authors: Josef Berger and Douglas Bridges

Published in: OASIcs, Volume 11, 6th International Conference on Computability and Complexity in Analysis (CCA'09) (2009)

Abstract
A summability theorem of Landau, which classically is a simple consequence of the uniform boundedness theorem, is examined constructively.
Cite as

Josef Berger and Douglas Bridges. A Constructive Study of Landau's Summability Theorem. In 6th International Conference on Computability and Complexity in Analysis (CCA'09). Open Access Series in Informatics (OASIcs), Volume 11, pp. 61-70, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{berger_et_al:OASIcs.CCA.2009.2259,
  author =	{Berger, Josef and Bridges, Douglas},
  title =	{{A Constructive Study of Landau's Summability Theorem}},
  booktitle =	{6th International Conference on Computability and Complexity in Analysis (CCA'09)},
  pages =	{61--70},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-12-5},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{11},
  editor =	{Bauer, Andrej and Hertling, Peter and Ko, Ker-I},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.CCA.2009.2259},
  URN =		{urn:nbn:de:0030-drops-22595},
  doi =		{10.4230/OASIcs.CCA.2009.2259},
  annote =	{Keywords: Constructive analysis, Landau's theorem, uniform boundedness theorem Constructive analysis, Landau's theorem, uniform boundedness theorem}
}
  • Refine by Author
  • 1 Berger, Alon
  • 1 Berger, Josef
  • 1 Bridges, Douglas
  • 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 Constructive analysis
  • 1 Landau's theorem
  • 1 coding
  • 1 lower bounds
  • 1 register emulations
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2009
  • 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