2026-07-22T18:45:15Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9800 2024-03-06T10:44:57Z ddc:004 open_access

Integrated Bounds for Disintegrated Storage Berger, Alon Keidar, Idit Spiegelman, Alexander storage coding lower bounds space complexity register emulations 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alon Berger and Idit Keidar and Alexander Spiegelman 2018 Is Part Of LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2018.11 urn:nbn:de:0030-drops-98009 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.11 eng https://creativecommons.org/licenses/by/3.0/legalcode