English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The focus of this paper is to understand storage costs of emulating an atomicshared memory over an asynchronous, distributed message passing system.Previous literature has developed several shared memory emulation algorithmsbased on replication and erasure coding techniques. In this paper, we presentinformation-theoretic lower bounds on the storage costs incurred by sharedmemory emulation algorithms. Our storage cost lower bounds are universallyapplicable, that is, we make no assumption on the structure of the algorithm orthe method of encoding the data.  We consider an arbitrary algorithm $A$ that implements an atomic multi-writersingle-reader (MWSR) shared memory variable whose values come from a finite set$\mathcal{V}$ over a system of $N$ servers connected by point-to-pointasynchronous links. We require that in every fair execution of algorithm $A$where the number of server failures is smaller than a parameter $f$, everyoperation invoked at a non-failing client terminates. We define the storagecost of a server in algorithm $A$ as the logarithm (to base 2) of number ofstates it can take on; the total-storage cost of algorithm $A$ is the sum ofthe storage cost of all servers.  Our results are as follows. (i) We show that if algorithm $A$ does not useserver gossip, then the total storage cost is lower bounded by $2\frac{N}{N-f+1}\log_2|\mathcal{V}|-o(\log_2|\mathcal{V}|)$. (ii) The totalstorage cost is at least $2 \frac{N}{N-f+2}\log_{2}|\mathcal{V}|-o(\log_{2}|\mathcal{V}|)$ even if the algorithm usesserver gossip. (iii) We consider algorithms where the write protocol sendsinformation about the value in at most one phase. We show that the totalstorage cost is at least $\nu^* \frac{N}{N-f+\nu^*-1} \log_2( |\mathcal{V}|)-o(\log_2(|\mathcal{V}|),$ where $\nu^*$ is the minimum of $f+1$ and the numberof active write operations of an execution.

Information-Theoretic Lower Bounds on the Storage Cost of Shared Memory Emulation