A new piggybacking design for systematic MDS storage codes

DOI10.1007/S10623-019-00650-9MaRDI QIDQ2334436zbMATH OpenOpenAlexWikidataFDO

Authors Chong Shangguan, Gennian Ge

Publication date 7 November 2019

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

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

zbMATH Keywords

distributed storage systempiggybacked codesystematic MDS code

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Linear codes (general theory) (94B05)

Abstract: Distributed storage codes have important applications in the design of modern storage systems. In a distributed storage system, every storage node has a probability to fail and once an individual storage node fails, it must be reconstructed using data stored in the surviving nodes. Computation load and network bandwidth are two important issues we need to concern when repairing a failed node. The traditional maximal distance separable (MDS) storage codes have low repair complexity but high repair bandwidth. On the contrary, minimal storage regenerating (MSR) codes have low repair bandwidth but high repair complexity. Fortunately, the newly introduced piggyback codes combine the advantages of both ones. In this paper, by introducing a novel piggybacking design framework for systematic MDS codes, we construct a storage code whose average repair bandwidth rate, i.e., the ratio of average repair bandwidth and the amount of the original data, can be as low as $fracsqrt2r-1r$, which significantly improves the ratio $fracr-12r-1$ of the previous result. In the meanwhile, every failed systematic node of the new code can be reconstructed quickly using the decoding algorithm of an MDS code, only with some additional additions over the underlying finite field. This is very fast compared with the complex matrix multiplications needed in the repair of a failed node of an MSR code.

Recommendations

• Network Coding for Distributed Storage Systems
• Editorial
• MDS code constructions with small sub-packetization and near-optimal repair bandwidth
• A new \((k+2,k)\) Hadamard minimum storage regenerating code
• Explicit constructions of MSR codes for clustered distributed storage: the rack-aware storage model

Cites work

• A Family of Optimal Locally Recoverable Codes
• A Piggybacking Design Framework for Read-and Download-efficient Distributed Storage Codes
• A Systematic Piggybacking Design for Minimum Storage Regenerating Codes
• An Improved Sub-Packetization Bound for Minimum Storage Regenerating Codes
• Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth
• Maximum distance<tex>q</tex>-nary codes
• Minimum Storage Regenerating Codes for All Parameters
• Network Coding for Distributed Storage Systems
• On the Locality of Codeword Symbols
• Zigzag Codes: MDS Array Codes With Optimal Rebuilding

Cited in

(8)

• Modified Low-Density MDS Array Codes for Tolerating Double Disk Failures in Disk Arrays
• A class of minimum storage cooperative regenerating codes with low access property
• Trade-off for heterogeneous distributed storage systems between storage and repair cost
• A new \((k+2,k)\) Hadamard minimum storage regenerating code
• A new minimize matrix computation coding method for distributed storage systems
• New Efficient MDS Array Codes for RAID Part II: Rabin-Like Codes for Tolerating Multiple (greater than or equal to 4) Disk Failures
• Partially collaborative storage codes in the presence of an eavesdropper
• MDS code constructions with small sub-packetization and near-optimal repair bandwidth

This page was built for publication: A new piggybacking design for systematic MDS storage codes

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