Zigzag-Decodable Reconstruction Codes With Asymptotically Optimal Repair for All Nodes
Hanxu Hou, Patrick P. C. Lee, Yunghsiang Sam Han · IEEE Transactions on Communications · 2020
Zigzag-decodable codes have been proposed for distributed storage systems to achieve fast decoding of uncoded data packets through the iterative decoding of data bits from coded packets. To maintain high data availability, it is critical to minimize the repair bandwidth by downloading the least amount of bits for repairing any lost packet. In this work, we propose zigzag-decodable reconstruction (ZDR) codes which achieve asymptotically minimum repair bandwidth for repairing a single node, while preserving the high computational efficiency due to zigzag decoding. We present two explicit constructions of ZDR codes such that any node of ZDR codes can be repaired with asymptotically minimum repair bandwidth. The first construction is based on the well-designed encoding matrix and a generic transformation, while the second construction is designed by recursively employing the proposed generic transformation for any existing zigzag-decodable code. Moreover, we show that the proposed two classes of ZDR codes can be decoded by the zigzag decoding algorithm and have less computational complexity than the existing codes with asymptotically or exactly minimum repair bandwidth.