Design And Analysis Of Minimum Storage Regenerating Codes With The Optimal Access/Update Property For Distributed Storage Systems

With the explosive growth of data volume, traditional centralized storage systems can not meet the ever-growing storage requirements. Distributed storage systems with high re-liability, scalability, cheap, and other advantages have attracted a wide range of applications in large data centers, peer-to-peer storage systems, etc. To ensure reliability, the redundancy is crucial for these systems. A popular option to add redundancy is to employ erasure codes which can efficiently store data and protect against node failures. However, traditional era-sure codes such as RS (Reed-Solomon) codes and other MDS codes require a large repair bandwidth. To characterize the storage and the repair bandwidth, Dimakis et al. established a trade-off between them under functional-repair, which gives the smallest (optimal) repair bandwidth under a given node capacity, and introduced MSR (Minimum Storage Regener-ating) codes, i.e., MDS storage codes with the optimal repair property. Up to now, only the systematic nodes of most known high-rate MDS storage codes can be optimally repaired, and some high-rate MDS codes have some deficiency in other aspects such as the update property,the access property, the number of systematic nodes, while known high-rate MSR codes (i.e.,MDS storage codes with all nodes can be optimally repaired) are very rare. In this disserta-tion, we give several constructions of high-rate MDS storage codes with the minimum repair bandwidth for systematic nodes and other good properties, and propose the optimal repair strategy for the parity nodes of some known high-rate MDS storage codes.Firstly, based on a kind of partitions of a basis set, we propose a framework of construc-tions of high-rate MDS storage codes, under which four known high-rate MDS storage codes such as the Hadamard design code are reinterpreted.Secondly, five classes of (k + 2, k) MDS storage codes with the optimal access/update property and more systematic nodes are proposed, the field sizes required are also determined.Under a given node capacity, the first class of MDS storage code possesses the largest number of systematic nodes in literature, the third and fourth classes of MDS storage codes possess the largest number of systematic nodes among all known MDS storage codes with the optimal update property, for the fifth class of MDS storage code, the size of the finite filed required is the smallest among all known MDS codes with the optimal access property, and the number of systematic nodes attains the theoretical upper bound.Thirdly, we provide a generic transformation that is able to convert any non-binary linear MDS storage codes with optimal repair property for systematic nodes into MSR codes, the parity nodes of the resultant MSR codes have the optimal access property, and the new codes can maintain other good properties of the base MDS codes, such as the size of the finite field, the optimal access property for systematic nodes. In addition, the transformation can also be applied to other MDS storage codes without optimal repair property for systematic nodes. After applying the transformation, some know MDS storage codes will have clear advantages when compared to the known Piggyback codes and the Ye-barg codes,that is 1)optimal repair property for parity nodes, whereas the known Piggyback codes do not possess the optimal repair property for parity nodes; 2) smaller field size and node capacity when compared to Ye-Barg codes in some cases.Finally, we discuss the repair strategy for the parity nodes of the (k + 2, k) Zigzag code.We give a method to modify the (k + 2, k) Zigzag code such that the parity nodes of the resultant code can also be optimally repaired and possess the optimal access property, and maintain the optimal access property for systematic nodes. The modification only need to double the node capacity of the (k + 2, k) Zigzag code, therefore has clear advantage com-pared to the modification proposed by Wang et. al, which need to increase the node capacity of the (k + 2, k) Zigzag code three times. Besides, by iteration we give the construction of the (k + 2, k) Zigzag code in the form of matrices, based on which we provide an optimal repair strategy for the parity nodes of the (k + 2, k) Zigzag code.