A Layered Architecture for Erasure-Coded Consistent Distributed Storage

DOI10.1145/3087801.3087832zbMATH Open1380.68054arXiv1703.01286OpenAlexW2594733076WikidataQ130889713 ScholiaQ130889713MaRDI QIDQ5368941FDOQ5368941

Authors:

Publication date: 11 October 2017

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

Abstract: Motivated by emerging applications to the edge computing paradigm, we introduce a two-layer erasure-coded fault-tolerant distributed storage system offering atomic access for read and write operations. In edge computing, clients interact with an edge-layer of servers that is geographically near; the edge-layer in turn interacts with a back-end layer of servers. The edge-layer provides low latency access and temporary storage for client operations, and uses the back-end layer for persistent storage. Our algorithm, termed Layered Data Storage (LDS) algorithm, offers several features suitable for edge-computing systems, works under asynchronous message-passing environments, supports multiple readers and writers, and can tolerate $f_1<n_1/2$ and $f_2<n_2/3$ crash failures in the two layers having $n_1$ and $n_2$ servers, respectively. We use a class of erasure codes known as regenerating codes for storage of data in the back-end layer. The choice of regenerating codes, instead of popular choices like Reed-Solomon codes, not only optimizes the cost of back-end storage, but also helps in optimizing communication cost of read operations, when the value needs to be recreated all the way from the back-end. The two-layer architecture permits a modular implementation of atomicity and erasure-code protocols; the implementation of erasure-codes is mostly limited to interaction between the two layers. We prove liveness and atomicity of LDS, and also compute performance costs associated with read and write operations. Further, in a multi-object system running $N$ independent instances of LDS, where only a small fraction of the objects undergo concurrent accesses at any point during the execution, the overall storage cost is dominated by that of persistent storage in the back-end layer, and is given by $Theta(N)$.

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

Recommendations

• Optimistic Erasure-Coded Distributed Storage
• Architecture-aware coding for distributed storage: repairable block failure resilient codes
• Sparsity exploiting erasure coding for distributed storage of versioned data
• Information-Theoretically Secure Erasure Codes for Distributed Storage

zbMATH Keywords

consistencyerasure codesfault toleranceregenerating codeslivenesscommunication coststorage costedge computingasynchronous distributed networkobject storage

Mathematics Subject Classification ID

Reliability, testing and fault tolerance of networks and computer systems (68M15) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Distributed algorithms (68W15) Network design and communication in computer systems (68M10) Distributed systems (68M14)

Cited In (5)

• Radon: repairable atomic data object in networks
• Self-stabilizing and private distributed shared atomic memory in seldomly fair message passing networks
• Optimistic Erasure-Coded Distributed Storage
• Brief Announcement: CausalEC: A Causally Consistent Data Storage Algorithm based on Cross-Object Erasure Coding
• Modeling and optimization of latency in erasure-coded storage systems

This page was built for publication: A Layered Architecture for Erasure-Coded Consistent Distributed Storage

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