Multi-version Storage: Code Design and Repair in Distributed Storage Systems

Abstract: With the rapid growth of data volume, data storage has attracted more and more researchinterests in recent years. Distributed storage systems play important roles ofmeeting the demand for data storage in large amounts. That is, data are stored bymultiple storage nodes which are connected together with various network topologies.The main merits of such distributed storage are faster response, higher reliability andbetter scalability. However, due to network failure, link outage or bu↵er overflow, theupdated data might not be received by all storage nodes, resulting in the coexistenceof multiple versions of the file in the system. Thus, the major challenge is consistency,which means that the latest version of the file is accessible to any read request. We aimto study multi-version storage and code design in distributed storage systems, where thelatest version of the file or a version close to the latest version is recoverable. Moreover,compared to previous studies, higher availability can be achieved in our system model,namely, at least one version of the file can be obtained.On the other hand, both storage nodes and links are vulnerable to fail in storage systems.For the sake of reliability demand, the lost data is supposed to be reconstructed.In this thesis, additional storage nodes dedicated to repair (DR storage nodes) are introducedin the repair process. The results show that optimal repair bandwidth withminimal additional storage space can be achieved by introducing a certain number ofDR storage nodes. Subsequently, linear combinations are provided to reduce the communicationcost of repair where the link cost is high. Last but not the least, we showthat the cooperation among surviving nodes and DR storage nodes suffices to completethe repair process successfully even with link failure.