Search

Distributed storage systems can provide reliable service of data storage. Lots of scenarios, such as data center, P2P network are all applications of distributed storage systems. There are mainly three storage schemes for distributed storage systems, including replication, erasure codes and regenerating codes. With the same storage space, more reliable data storage is assured by erasure codes than replication. However, replication can save more repair bandwidth (i.e., the communication cost for node repair) than erasure codes. To ensure both high reliability and low repair bandwidth, regenerating codes are intensively investigated. In practical systems, the communication between two nodes may be restricted by physical factors or economic considerations, such as transmission distance or network traffic. In this paper, we propose a novel model considering the connectivity limitations in ring networks. Each node can only connect to or communicate with its neighbors within a given range. Inspired by the concept of regenerating codes, we investigate the theoretical necessary condition for all possible storage codes. Then, a tradeoff between storage space and repair bandwidth is derived by analyzing the information flow graph of our model. Two interesting points on the tradeoff curve are further investigated, corresponding to the ring minimum-storage-regenerating (rMSR) codes, and the ring minimum-bandwidth-regenerating (rMBR) codes. Besides, two types of code constructions are presented. (i) For both rMSR and rMBR codes, we provide code constructions under exact repair models. (ii) Under functional repair models, we derive the size of the coding finite field, based on which the algorithm in can be applied to construct the corresponding codes. And finally, the superiority of our codes is validated by both theoretical and simulation results. Simulations show that our codes outperform baseline schemes, and the reduction on repair bandwidth can be up to 66% of the original data size. [ABSTRACT FROM AUTHOR]

The problem of exact-repair regenerating codes against eavesdropping attack is studied. The eavesdropping model we consider is that the eavesdropper has the capability to observe the data involved in the repair of a subset of $\ell $ nodes. An $(n,k,d,\ell)$ secure exact-repair regenerating code is an $(n,k,d)$ exact-repair regenerating code that is secure under this eavesdropping model. It has been shown that for some parameters $(n,k,d,\ell)$ , the associated optimal storage-bandwidth tradeoff curve, which has one corner point, can be determined. The focus of this paper is on characterizing such parameters. We establish a lower bound $\hat {\ell }$ on the number of wiretap nodes, and show that this bound is tight for the case $k = d = n-1$. [ABSTRACT FROM AUTHOR]

In wireless distributed storage systems, storage nodes are connected by wireless channels, which are broadcast in nature. This paper exploits this unique feature to design an efficient repair mechanism, called broadcast repair, for wireless distributed storage systems in the presence of multiple-node failures. Due to the broadcast nature of wireless transmission, we advocate a new measure on repair performance called repair-transmission bandwidth. In contrast to repair bandwidth, which measures the average number of packets downloaded by a newcomer to replace a failed node, repair-transmission bandwidth measures the average number of packets transmitted by helper nodes per failed node. The storage system we considered can undergo an unlimited number of repair rounds. We obtain an upper bound on the maximum file size that can be supported by a cut analysis of a finite graph. The achievability is shown by codes constructed over a refined information flow graph, which is unbounded. In addition, the optimal storage-bandwidth tradeoff is obtained. The performance of broadcast repair is compared both analytically and numerically with that of cooperative repair, the basic repair method for wired distributed storage systems with multiple-node failures. While cooperative repair is based on the idea of allowing newcomers to exchange packets, broadcast repair is based on the idea of allowing a helper to broadcast packets to all newcomers simultaneously. We show that broadcast repair outperforms cooperative repair, offering a better tradeoff between storage efficiency and repair-transmission bandwidth. [ABSTRACT FROM AUTHOR]

Despite their exceptional error-correcting properties, Reed–Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC’16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures. [ABSTRACT FROM AUTHOR]

Piggybacking is an efficient framework to reduce the repair bandwidth of distributed storage systems, especially, when the systems meet the settings–maximum distance separable (MDS), high code rate, and a small number of substripes. Through an analysis on the repair ratio of a piggybacking construction, this paper reveals that the proportion $p_{p}$ of piggybacking protected stripes is the key to significantly decrease the repair bandwidth. Based on this analysis, this paper proposes a repair efficient coding under piggybacking framework (REPB) by considering various piggybacking protected stripes and MDS only protected stripes. The repair ratio of REPB tends to 0 and is close to theoretical cut-set bound, as the proportion $p_{p}$ is no longer fixed at 1/2. Furthermore, the proposed REPB codes enjoy low computational complexity in repair operation. [ABSTRACT FROM AUTHOR]

A linear block code with dimension $k$ , length $n$ , and minimum distance $d$ is called a locally repairable code (LRC) with locality $r$ , if it can retrieve any coded symbol by at most $r$ other coded symbols. LRCs have been recently proposed and used in practice in distributed storage systems, such as Windows Azure Storage and Facebook HDFS-RAID. Theoretical bounds on the maximum locality of LRCs ( $r$ ) have been established. The average locality of an LRC ( $\overline {r}$ ) directly affects the costly repair bandwidth, disk I/O, and the number of nodes involved in the repair process of a missing data block. There is a gap in the literature studying $\overline {r}$. In this paper, we establish a lower bound on $\overline {r}$ of arbitrary $(n,k,d)$ LRCs. Furthermore, we obtain a tight lower bound on $\overline {r}$ for a practical case where the code rate $(R=({k}/{n}))$ is greater than $(1-({1}/{\sqrt {n}}))^{2}$. Finally, we design three classes of LRCs that achieve the obtained bounds on $\overline {r}$. Comparing with the existing LRCs, our proposed codes improve the average locality without sacrificing such crucial parameters as the code rate or minimum distance. [ABSTRACT FROM AUTHOR]

Fractional repetition (FR) codes are introduced with the aim of facilitating node repairs in distributed storage systems, i.e., they enable uncoded exact repairs at the minimum bandwidth regenerating (MBR) point. In this letter, we investigate universally good FR (UGFR) codes, which can achieve the storage capacity of MBR codes. We show that UGFR codes are optimal with respect to a bound on the reconstruction degree, which is the number of nodes required for data retrieval. We also present a construction of UGFR codes by establishing a relation with regular packings. [ABSTRACT FROM PUBLISHER]

Cooperative regenerating codes are a kind of erasure codes, which are optimal in terms of minimizing the repair bandwidth. An $(n,k,d,r)$ -cooperative regenerating code has $n$ storage nodes, where $k$ arbitrary nodes are enough to reconstruct original data, and $r$ failed nodes can be repaired cooperatively with the help of $d$ arbitrary surviving nodes. In the regenerating-code framework, there exists a tradeoff between the storage capacity of each node $\alpha $ and the repair bandwidth $\gamma $ , but the problem of specifying the optimal storage-bandwidth tradeoff of the exact-repair cooperative regenerating codes remains open. A key contribution of this paper is that an outer bound on the storage-bandwidth tradeoff of exact-repair linear cooperative regenerating codes is proposed. This result can be regarded as a generalization of the outer bound proposed by Prakash et al., which specifies the optimal tradeoff of exact-repair regenerating codes for the case of $d=k=n-1$ . The proposed outer bound suggests the $(\alpha ,\gamma )$ pairs that no exact-repair codes can achieve but only functional-repair codes can. By observing the size of the set of such $(\alpha ,\gamma )$ pairs, the performance of the proposed outer bound is evaluated under various parameter settings. [ABSTRACT FROM PUBLISHER]

The problem of characterizing the fundamental tradeoff between storage and repair bandwidth of exact-repair regenerating codes against a passive eavesdropper is studied. The eavesdropper is assumed to be capable of observing the data stored in a fixed number of nodes and the data involved in the repair of these nodes. In this paper, the tradeoff for regenerating codes with small parameters is characterized, and then, the results are extended to some general settings. [ABSTRACT FROM PUBLISHER]

Regenerating codes for distributed storage have attracted much research interest in the past decade. Such codes trade the bandwidth needed to repair a failed node with the overall amount of data stored in the network. Minimum storage regenerating (MSR) codes are an important class of optimal regenerating codes that minimize (first) the amount of data stored per node and (then) the repair bandwidth. Specifically, an [n,k,d] - (\alpha ) MSR code \mathbb C over \smash \mathbb F\!q stores a file \mathcal F consisting of \alpha k symbols over \smash {\mathbb {F}_{\!q}} among n$ nodes, each storing \alpha $ symbols, in such a way that: 1) the file k$ of the n$ nodes and 2) the content of any failed node can be reconstructed by accessing any d$ of the remaining symbols from each of these nodes. In practice, the file \mathcal F is typically available in uncoded form on some $k$ of the $n$ nodes, known as systematic nodes, and the defining node-repair condition above can be relaxed to requiring the optimal repair bandwidth for systematic nodes only. Such codes are called systematic–repair MSR codes. Unfortunately, finite– $\alpha $ constructions of $[n,k,d]$ MSR codes are known only for certain special cases: either low rate, namely $k/n \leqslant 0.5$ , or high repair connectivity, namely $d = n-1$ . Our main result in this paper is a finite– $\alpha $ construction of systematic-repair $[n,k,d]$ MSR codes for all possible values of parameters $n,k,d$ . We also introduce a generalized construction for $[n,k]$ MSR codes to achieve the optimal repair bandwidth for all values of $d$ simultaneously. [ABSTRACT FROM PUBLISHER]

To balance performance and storage efficiency, modern clustered file systems often first store data with replication, followed by encoding the replicated data with erasure coding. We argue that the commonly used random replication does not take into account erasure coding in its design, thereby raising both performance and availability issues in the subsequent encoding operation. We propose encoding-aware replication, which carefully places the replicas so as to (i) eliminate cross-rack downloads of data blocks during the encoding operation, (ii) preserve availability without data relocation after the encoding operation, and (iii) maintain load balancing across replicas as in random replication before the encoding operation. We conduct extensive HDFS-based testbed experiments and discrete-event simulations, and demonstrate the performance gains of encoding-aware replication over random replication. [ABSTRACT FROM AUTHOR]

Regenerating codes focus on the efficient repair of node failures. In an [ n , k , d ] regenerating code system, any k nodes can retrieve the original data and any d nodes can repair a failed node by giving out has been proved. However, as far as we know, there is no construction of exact-repair MSR codes with {d= 2 k - 3} and {\beta = 1} at present. In this letter, we give the first construction of [6, 4, 5] MSR codes with \beta = 1 , which can perform exact repair of all nodes. Employing the technique of linearly dependent vectors, our codes can be constructed over a small finite field F4 . [ABSTRACT FROM PUBLISHER]

In this letter, we focus on fractional repetition (FR) codes, which enable uncoded exact node repair with the minimum disk reads and network bandwidth. We investigate the problem of designing FR codes that also incorporate the preferable property of local repair, i.e., the nodes participating in the repair operation are less than those required for data reconstruction. We propose explicit code constructions based on the combinatorial structure called symmetric design. The benefits of the proposed construction include: 1) each contacted helper node transfers the same amount of data in the repair process, and 2) each failed storage node can have multiple local repair alternatives. [ABSTRACT FROM PUBLISHER]

An (n,k) erasure code that can recover any coded symbol by at most r other coded symbols is called a locally repairable code (LRC) with locality r . LRCs have been recently implemented in distributed storage systems. Coding complexity reduction can be significantly decreased by using binary LRCs (BLRCs) as they eliminate costly multiplication calculation. In this paper, motivated by the recently erasure codes with d=4 used in practice, we propose BLRCs when (r+1)\mid n and , meaning that neither their locality nor their minimum distance can be improved by non-binary codes. For r\geq 4 , our proposed binary codes offer near-optimal code rate, with a rate gap of \mathcal O(\log r/n) compared with optimal non-binary codes. While keeping the bulk of code structure binary, we eliminate this rate gap by using fields with sizes as small as r+2 for only two redundant symbols. These non-binary codes still eliminate the need for costly multiplications in many operations including a single failure repair (a dominant repair scenario). Using the construction of spanning BLRC with $d=4$ as a backbone, we also construct LRCs with minimum distance $d\geq 6$ . Furthermore, we obtain a closed-form equation for the mean-time to data-loss of arbitrary erasure codes. [ABSTRACT FROM AUTHOR]

Two-parity maximum distance separable (MDS) array codes achieve the lowest storage overhead for tolerating two erasures. In this letter, we propose two new classes of two-parity MDS array codes over finite field \mathbb F2 , with which each single node failure can be recovered by reading the minimum amount of data from each surviving node. [ABSTRACT FROM PUBLISHER]

In distributed storage systems, regenerating codes can achieve the optimal tradeoff between storage capacity and repair bandwidth. However, a critical drawback of existing regenerating codes, in general, is the high coding and repair complexity, since the coding and repair processes involve expensive multiplication operations in finite field. In this paper, we present a design framework of regenerating codes, which employ binary addition and bitwise cyclic shift as the elemental operations, named BASIC regenerating codes. The proposed BASIC regenerating codes can be regarded as a concatenated code with the outer code being a binary parity-check code, and the inner code being a regenerating code utilizing the binary parity-check code as the alphabet. We show that the proposed functional-repair BASIC regenerating codes can achieve the fundamental tradeoff curve between the storage and repair bandwidth asymptotically of functional-repair regenerating codes with less computational complexity. Furthermore, we demonstrate that the existing exact-repair product-matrix construction of regenerating codes can be modified to exact-repair BASIC product-matrix regenerating codes with much less encoding, repair, and decoding complexity from the theoretical analysis, and with less encoding time, repair time, and decoding time from the implementation results. [ABSTRACT FROM AUTHOR]

Modern storage systems are increasingly employing erasure codes to protect data against disk failures. Various codes have been elaborately constructed to achieve the desirable storage performance. In this letter, we consider fractional repetition (FR) codes, which provide uncoded exact repairs with minimum repair bandwidth. We present a novel code construction framework that is built on existing codes to generate new FR codes. The proposed framework extends the construction of FR codes to a larger set of parameters, and is applicable to heterogeneous storage networks. Moreover, we characterize a general expression for the minimum distance of FR codes, which is derived from a simple analysis and depends on the size of stored file. We further present closed-form expressions on the minimum distance for some special scenarios. [ABSTRACT FROM PUBLISHER]

Node recovery is a challenging task in erasure-coded storage systems, which involves a considerable amount of network resources. The efficacy of failure recovery is measured by various metrics, such as repair bandwidth and computational complexity. This letter focuses on fractional repetition (FR) codes, which are a family of codes that provide uncoded exact repairs with minimum repair bandwidth. We consider the usage of FR codes in dynamic storage systems, where the system parameters can vary over time. Specifically, we introduce adaptive fractional repetition codes that can effectively adapt to system changes. The proposed codes allow update of systems without the need for frequent reconfigurations. Moreover, explicit code constructions for both homogeneous and heterogeneous storage systems are presented. [ABSTRACT FROM PUBLISHER]

In practical large-scale distributed storage systems, node failures are unavoidable. It is therefore desirable to quickly recreate the failed nodes in order to maintain the system integrity. In this letter, we consider a family of erasure codes that provide uncoded repair, where the failed node is regenerated by transfer of data without extra arithmetic operations. We introduce flexible fractional repetition (FFR) code, of which the coding scheme is a concatenation of an outer MDS code and an inner repetition code. Our proposed codes are applicable to the heterogeneous network environment where node storage capacities and packet repetition degrees vary in a wide range. We present explicit constructions of FFR codes by utilizing combinatorial designs. We further propose a heuristic code construction. Evaluation results show that FFR codes outperform regenerating codes in node repair efficiency. [ABSTRACT FROM PUBLISHER]

In order to provide fault-tolerance and guarantee reliability, data redundancy should be introduced in distributed storage systems. The emerging coding techniques for storage such as fractional repetition codes, provide the required redundancy more efficiently than the conventional replication scheme. In this letter, we extend the construction of fractional repetition codes and present a new coding scheme, termed general fractional repetition codes. The proposed codes can be applied to storage systems in which the storage capacities of nodes may be different. Based on a combinatorial structure known as group divisible design, the new code construction is available for a large set of parameters. The performance of the proposed codes is evaluated by a metric called node repair alternativity, which measures the number of different subsets of nodes that enable the repair of a specific failed node. [ABSTRACT FROM PUBLISHER]