Recovery and Repair Schemes for Shift-XOR Regenerating Codes

Recovery and repair schemes are proposed for shift-exclusive-or (shift-XOR) product-matrix (PM) regenerating codes, which outperform those of the existing PM codes in terms of both communication and computation costs. In particular, for the minimum bandwidth regenerating (MBR) codes, our recovery and repair schemes have the optimal transmission bandwidth, zero decoding auxiliary data space and lower time complexity; for the minimum storage regenerating (MSR) codes, our recovery and repair schemes have smaller transmission bandwidth, smaller decoding auxiliary data space and lower time complexity. Moreover, our schemes involve only XOR operations in recovery and repair and are practical for system implementation. Technically, a procedure is first proposed for solving a system of shift-XOR equations, which plays a similar fundamental role as Gaussian elimination for solving systems of linear equations, and is of independent interest. The recovery and repair of shift-XOR MBR/MSR codes are then decomposed into a sequence of systems of shift-XOR equations, and hence can be solved by a sequence of calls to the procedure for solving a system of shift-XOR equations. As the decomposition of the recovery and repair depends only on the PM construction, but not the specific shift and XOR operations, our recovery and repair schemes can be extended to other MBR/MSR codes using the PM construction.