Space Complexity of Fault-Tolerant Register Emulations. / Chockler, Gregory; Spiegelman, Alexander.

The 36th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2017)). ACM, 2017. p. 83-92.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Published

Documents

Abstract

Driven by the rising popularity of cloud storage, the costs associated with implementing reliable storage services from a collection of fault-prone servers have recently become an actively studied question. The well-known ABD result shows that an f-tolerant register can be emulated using a collection of 2f +1 fault-prone servers each storing a single read-modify- write object, which is known to be optimal. In this paper we generalize this bound: we investigate the inherent space complexity of emulating reliable multi-writer registers as a function of the type of the base objects exposed by the underlying servers, the number of writers to the emulated register, the number of available servers, and the failure threshold.

We establish a sharp separation between registers, and both max-registers (the base object type assumed by ABD) and CAS in terms of the resources (i.e., the number of base objects of the respective types) required to support the emulation; we show that no such separation exists between max-registers and CAS. Our main technical contribution is lower and upper bounds on the resources required in case the underlying base objects are fault-prone read/write registers. We show that the number of required registers is directly proportional to the number of writers and inversely proportional to the number of servers.
Original languageEnglish
Title of host publicationThe 36th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC 2017))
Place of PublicationACM
Pages83-92
Number of pages10
DOIs
Publication statusPublished - 25 Jul 2017
EventThe 36th ACM Symposium on Principles of Distributed Computing - Washington, DC, United States
Duration: 25 Jul 201727 Jul 2017
https://www.podc.org/

Conference

ConferenceThe 36th ACM Symposium on Principles of Distributed Computing
Abbreviated titlePODC 2017
CountryUnited States
CityWashington, DC
Period25/07/1727/07/17
Internet address
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 28317142