Optimal Rebuilding of Multiple Erasures in MDS Codes

DOI10.1109/TIT.2016.2633411zbMATH Open1364.94634arXiv1603.01213MaRDI QIDQ2989643FDOQ2989643

Authors: Zhiying Wang, Itzhak Tamo, Jehoshua Bruck

Publication date: 8 June 2017

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

Abstract: MDS array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with

r

redundancy nodes can correct any

r

node erasures by accessing all the remaining information in the surviving nodes. However, in practice,

e

erasures is a more likely failure event, for

1 l e e < r

. Hence, a natural question is how much information do we need to access in order to rebuild

e

storage nodes? We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of

e

erasures. In our previous work we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of

1 / r

for the rebuilding of any systematic node when

e = 1

, however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any

r

erasures can be corrected by accessing some of the remaining information, and any

e = 1

erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this work, we study 3 questions on rebuilding of codes: (i) We show a fundamental trade-off between the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of

e / r

for MDS codes, for any

1 l e e l e r

. (ii) We construct systematic codes that achieve optimal rebuilding ratio of

1 / r

, for any systematic or parity node erasure. (iii) We present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances.

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

Mathematics Subject Classification ID

Linear codes (general theory) (94B05)

Cited In (2)

This page was built for publication: Optimal Rebuilding of Multiple Erasures in MDS Codes

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