pith. sign in

arxiv: 1805.06265 · v2 · pith:H6EFM5NJnew · submitted 2018-05-16 · 💻 cs.DC · cs.DS

Integrated Bounds for Disintegrated Storage

classification 💻 cs.DC cs.DS
keywords storageboundsdisintegratedemulationsintegratedreaderssharedsystems
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.