Distributed storage plays a crucial role in the current cloud computing framework. After the theoretical bound for distributed storage was derived by the pioneer work of the regenerating code, Reed-Solomon code based regenerating codes were developed. The RS code based minimum storage regeneration code (RS-MSR) and the minimum bandwidth regeneration code (RS-MBR) can achieve theoretical bounds on the MSR point and the MBR point respectively in code regeneration. They can also maintain the MDS property in code reconstruction. However, in the hostile network where the storage nodes can be compromised and the packets can be tampered with, the storage capacity of the network can be significantly affected. In this paper, we propose a Hermitian code based minimum storage regenerating (H-MSR) code and a minimum bandwidth regenerating (H-MBR) code. We first prove that our proposed Hermitian code based regenerating codes can achieve the theoretical bounds for MSR point and MBR point respectively. We then propose data regeneration and reconstruction algorithms for the H-MSR code and the H-MBR code in both error-free network and hostile network. Theoretical evaluation shows that our proposed schemes can detect the erroneous decodings and correct more errors in hostile network than the RS-MSR code and the RS-MBR code with the same code rate. Our analysis also demonstrates that the proposed H-MSR and H-MBR codes have lower computational complexity than the RS-MSR RS-MBR codes in both code regeneration and code reconstruction.
When a storage node in the distributed storage network that employing the conventional @math RS code (such as OceanStore @cite_0 and Total Recall @cite_2 ) fails, the replacement node connects to @math nodes and downloads the whole file to recover the symbols stored in the failed node. This approach is a waste of bandwidth because the whole file has to be downloaded to recover a fraction of it. To overcome this drawback, Dimakis @cite_3 introduced the concept of @math regenerating code. In the context of regenerating code, the replacement node can regenerate the contents stored in a failed node by downloading @math help symbols from @math helper nodes. The bandwidth consumption to regenerate a failed node could be far less than the whole file. A data collector (DC) can reconstruct the original file stored in the network by downloading @math symbols from each of the @math storage nodes. @cite_3 , the authors proved that there is a tradeoff between bandwidth @math and per node storage @math . They find two optimal points: minimum storage regeneration (MSR) and minimum bandwidth regeneration (MBR) points.
@cite_0 @cite_3 @cite_2
2017643135 2105185344
Explores mechanisms for storage-level management in OceanStore, a global-scale distributed storage utility infrastructure, designed to scale to billions of users and exabytes of data. OceanStore automatically recovers from server and network failures, incorporates new resources and adjusts to usage patterns. It provides its storage platform through adaptation, fault tolerance and repair. The only role of human administrators in the system is to physically attach or remove server hardware. Of course, an open question is how to scale a research prototype in such a way to demonstrate the basic thesis of this article - that OceanStore is self-maintaining. The allure of connecting millions or billions of components together is the hope that aggregate systems can provide scalability and predictable behavior under a wide variety of failures. The OceanStore architecture is a step towards this goal. Distributed storage systems provide reliable access to data through redundancy spread over individually unreliable nodes. Application scenarios include data centers, peer-to-peer storage systems, and storage in wireless networks. Storing data using an erasure code, in fragments spread across nodes, requires less redundancy than simple replication for the same level of reliability. However, since fragments must be periodically replaced as nodes fail, a key question is how to generate encoded fragments in a distributed way while transferring as little data as possible across the network. For an erasure coded system, a common practice to repair from a single node failure is for a new node to reconstruct the whole encoded data object to generate just one encoded block. We show that this procedure is sub-optimal. We introduce the notion of regenerating codes, which allow a new node to communicate functions of the stored data from the surviving nodes. We show that regenerating codes can significantly reduce the repair bandwidth. Further, we show that there is a fundamental tradeoff between storage and repair bandwidth which we theoretically characterize using flow arguments on an appropriately constructed graph. By invoking constructive results in network coding, we introduce regenerating codes that can achieve any point in this optimal tradeoff.