MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth

DOI10.1109/TIT.2018.2810095MaRDI QIDQ4682932zbMATH OpenFDO

Authors A. S. Rawat, Itzhak Tamo, Klim Efremenko, Venkatesan Guruswami

Publication date 19 September 2018

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

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

Mathematics Subject Classification ID

Source coding (94A29)

Abstract: This paper addresses the problem of constructing MDS codes that enable exact repair of each code block with small repair bandwidth, which refers to the total amount of information flow from the remaining code blocks during the repair process. This problem naturally arises in the context of distributed storage systems as the node repair problem [7]. The constructions of exact-repairable MDS codes with optimal repair-bandwidth require working with large sub-packetization levels, which restricts their employment in practice. This paper presents constructions for MDS codes that simultaneously provide both small repair bandwidth and small sub-packetization level. In particular, this paper presents two general approaches to construct exact-repairable MDS codes that aim at significantly reducing the required sub-packetization level at the cost of slightly sub-optimal repair bandwidth. The first approach gives MDS codes that have repair bandwidth at most twice the optimal repair-bandwidth. Additionally, these codes also have the smallest possible sub-packetization level $ell=O(r)$, where $r$ denotes the number of parity blocks. This approach is then generalized to design codes that have their repair bandwidth approaching the optimal repair-bandwidth at the cost of graceful increment in the required sub-packetization level. The second approach transforms an MDS code with optimal repair-bandwidth and large sub-packetization level into a longer MDS code with small sub-packetization level and near-optimal repair bandwidth. For a given $r$, the obtained codes have their sub-packetization level scaling logarithmically with the code length. In addition, the obtained codes require field size only linear in the code length and ensure load balancing among the intact code blocks in terms of the information downloaded from these blocks during the exact reconstruction of a code block.

Cited in

(9)

• Codes for Distributed Storage
• Binary MDS Array Codes With Optimal Repair
• A new repair-efficient piggybacking design for systematic nodes
• MDS and near-MDS codes via twisted Reed-Solomon codes
• Explicit constructions of optimal vector locally repairable codes
• (1+)-optimal MDS codes: contacting any set of helper nodes smaller than n-1
• MDS array codes with efficient repair and small sub-packetization level
• New centralized multi-node repair schemes for distributed storage
• A new hybrid coding scheme: homomorphic minimum bandwidth repairing codes

This page was built for publication: MDS Code Constructions With Small Sub-Packetization and Near-Optimal Repair Bandwidth

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