A document by Xing Lin . Click on the document to view its contents.

The use of Reed-Solomon (RS) codes in distributed storage systems is ubiquitous. In recent years, the repair schemes for RS codes with one or multiple failed symbols that can lessen communication cost in the repair (i.e., repair bandwidth) have been presented in literatures. However, the existing distributed repair schemes of RS codes can only repair e = 2, 3 erasures. In this paper, by ingeniously constructing the trace polynomials, two distributed repair schemes for RS codes with e ≥ 4 erasures are proposed for the first time.

In practical data centers,  storage nodes are grouped and distributed in different racks, where the communication cost across racks is much more expensive than that within rack.  The concept of rack-aware maximum distance separable (MDS) codes has been put forward in recent literatures to deal with rack architecture. In this paper, the cross-rack repair bandwidth and sub-packetization size of rack-aware Reed-Solomon (RS) codes are studied. Cross-rack repair bandwidth is defined as the amount of information transmitted between the racks in the repair process of a failed node. RS codes can be regarded as polynomials over a finite field $GF(q^t)$ evaluated at a set of points, where $t$ is referred to as the sub-packetization size. Smaller cross-rack repair bandwidth decreases the network usage in data centers, and smaller sub-packetization size is conducive to the implementation of RS code with lower complexity. Previous RS codes that reach the rack-aware cut-set bound on cross-rack repair bandwidth either have sub-packetization size exponential in the code length or require strictly limited parameter conditions.  In this paper, the lower bound on the cross-rack repair bandwidth related to  sub-packetization size for rack-aware RS codes is given, which is asymptotically reachable under some parameters, and three repair schemes of rack-aware RS codes which provide a tradeoff between the sub-packetization size and the cross-rack repair bandwidth are shown.

Due to the advantage of providing maximum data reliability at a given storage cost, $(k+r,k)$ maximum distance separable (MDS) array codes, in which all data symbols can be obtained by any $k$ of $k+r$ nodes, are extensively used in distributed storage systems. $(k+r,k,\alpha)$ piggybacking codes, which are a particular kind of $(k+r,k)$ MDS array codes, reaches low repair bandwidth for a failed single node and possesses small sub-packetization level $\alpha$. In this paper, by dividing the table formed by some instances of base MDS code into regions and carefully adding the data symbols in some regions as piggybacks to the parity symbols in some other regions, we design a new piggybacking code which has higher repair efficiency than the existing piggybacking codes in repairing each systematic node, where a node is said to be systematic if it keeps  portions of the raw message in reserve without encoding. The sub-packetization level is roughly equal to 2 times the number $r$ of parity nodes when the new piggybacking code attains the highest repair efficiency.

(1+ε)-optimal Maximum Distance Separable ((1+ε)-optimal MDS) codes, which are a special kind of $(n, k)$ MDS codes, can repair a single failed node by downloading slightly sub-optimal amount of data from $d$ helper nodes where $d\in [k, n)$, and have small sub-packetization level. Some (1+ε)-optimal MDS codes have been constructed in the literatures. However, for all the existing (1+ε)-optimal MDS codes with the number of helper nodes $d$ smaller than $n-1$, a few compulsory nodes need to be contacted when repairing a failed node. In this paper, we provide two explicit (1+ε)-optimal MDS codes contacting any set of $d$ helper nodes with $d$ smaller than $n-1$ for the first time.