Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth

DOI10.1109/TIT.2017.2661313MaRDI QIDQ5280881zbMATH OpenOpenAlexFDO

Authors Min Ye, Alexander Barg

Publication date 27 July 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Burst-correcting codes (94B20)

Abstract: Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure-tolerance for a given number of parity nodes. Suppose that an MDS code with $k$ information nodes and $r=n-k$ parity nodes is used to encode data in a distributed storage system. It is known that if $h$ out of the $n$ nodes are inaccessible and $d$ surviving (helper) nodes are used to recover the lost data, then we need to download at least $h/(d+h-k)$ fraction of the data stored in each of the helper nodes (Dimakis et. al., 2010 and Cadambe et al., 2013). If this lower bound is achieved for the repair of any $h$ erased nodes from any $d$ helper nodes, we say that the MDS code has the $(h,d)$-optimal repair property. We study high-rate MDS array codes with the optimal repair property. Explicit constructions of such codes in the literature are only available for the cases where there are at most 3 parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any $r$ and $n$, we present two explicit constructions of MDS array codes with the $(h,d)$-optimal repair property for all $hler$ and $kledlen-h$ simultaneously. Codes in the first family can be constructed over any base field $F$ as long as $|F|gesn,$ where $s=extlcm(1,2,dots,r).$ The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field $F$ as long as $|F|gen+1.$ Moreover, both code families have the optimal error resilience capability when repairing failed nodes. We also construct several other related families of MDS codes with the optimal repair property.

Cited in

(19)

• A new hybrid coding scheme: homomorphic minimum bandwidth repairing codes
• A new piggybacking design for systematic MDS storage codes
• A survey and refinement of repairable threshold schemes
• Multi-criteria decision-making method based on a cross-entropy with interval neutrosophic sets
• A multi-valued neutrosophic qualitative flexible approach based on likelihood for multi-criteria decision-making problems
• Zigzag Codes: MDS Array Codes With Optimal Rebuilding
• Binary MDS Array Codes With Optimal Repair
• Codes for Distributed Storage
• A class of minimum storage cooperative regenerating codes with low access property
• Clay and product-matrix MSR codes with locality
• MDS array codes with efficient repair and small sub-packetization level
• Constructing leakage-resilient Shamir's secret sharing: over composite order fields
• Towards breaking the half-barrier of local leakage-resilient Shamir's secret sharing
• Physical-bit leakage resilience of linear code-based secret sharing
• New centralized multi-node repair schemes for distributed storage
• A new repair-efficient piggybacking design for systematic nodes
• Explicit constructions of optimal vector locally repairable codes
• Distributed repairing multiple erasures in Reed-Solomon codes
• (1+)-optimal MDS codes: contacting any set of helper nodes smaller than n-1

This page was built for publication: Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth

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