Space Complexity of Fault-Tolerant Register Emulations

DOI10.1145/3087801.3087824zbMATH Open1380.68220arXiv1705.07212OpenAlexW2617735599MaRDI QIDQ5368945FDOQ5368945

Authors: Gregory Chockler, Alexander Spiegelman 

Publication date: 11 October 2017

Published in: Proceedings of the ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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 type, 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 fucntion 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 types 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.

Full work available at URL: https://arxiv.org/abs/1705.07212

Recommendations

• scientific article; zbMATH DE number 3850476
• Automatic verification of fault-tolerant register emulations
• The complexity of register allocation
• Bounds on the Costs of Multivalued Register Implementations
• scientific article; zbMATH DE number 4195880
• On the linear complexity of feedback registers
• The complexity of bounded register and skew arithmetic computation
• Machines, Computations, and Universality
• Time and space optimal implementations of atomic multi-writer register

zbMATH Keywords

space complexityfaulty shared memoryreliable emulations

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Analysis of algorithms and problem complexity (68Q25) Reliability, testing and fault tolerance of networks and computer systems (68M15) Distributed systems (68M14)

Cited In (3)

• Title not available (Why is that?)
• The cost of graceful degradation for omission failures
• Automatic verification of fault-tolerant register emulations

This page was built for publication: Space Complexity of Fault-Tolerant Register Emulations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5368945)