A new piggybacking design for systematic MDS storage codes

DOI10.1007/S10623-019-00650-9zbMATH Open1489.94149arXiv1610.08223OpenAlexW2964070496WikidataQ127756471 ScholiaQ127756471MaRDI QIDQ2334436FDOQ2334436

Authors: Chong Shangguan, Gennian Ge 

Publication date: 7 November 2019

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

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.

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

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

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)

Cites Work

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

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
• MDS code constructions with small sub-packetization and near-optimal repair bandwidth
• Partially collaborative storage codes in the presence of an eavesdropper

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)