Update-Efficient Error-Correcting Regenerating Codes
Yunghsiang Sam Han, Hung-Ta Pai, Rong Zheng, Pramod K. Varshney · arXiv (Cornell University) · 2013
Regenerating codes provide an efficient way to recover data a t failed nodes in distributed storage systems. It has been shown that regenerating codes can be designed to minimize the per-node storage (called MSR) or minimize the communication overhead for regeneration (called MBR). In this work, we propose new encoding schemes for [n,d] error-correcting MSR and MBR codes that generalize our earlier work on error-correcting regenerating codes. We show that by choosing a suitable diagonal matrix, any generator matrix of the [n,�] Reed-Solomon (RS) code can be integrated into the encoding matrix. Hence, MSR codes with the least update complexity can be found. By using the coefficients of generator polynomials of [n,k] and [n,d] RS codes, we present a least-update-complexity encoding scheme for MBR codes. An efficient decoding scheme is propose d that utilizes the [n,�] RS code to perform data reconstruction for MSR codes. The proposed decoding scheme has better error correction capability and incurs the least number of node accesses when errors are present. A new decoding scheme is also proposed for MBR codes that can correct more error-patterns.