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: https://drops.dagstuhl.de/opus/volltexte/2018/9800/
Berger, Alon ; Keidar, Idit ; Spiegelman, Alexander
Integrated Bounds for Disintegrated Storage
| pdf-format: |
|
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 | |
| Seminar: | 32nd International Symposium on Distributed Computing (DISC 2018) | |
| Issue date: | 2018 | |
| Date of publication: | 04.10.2018 |
