An @math maximum distance separable (MDS) code has optimal repair access if the minimum number of symbols accessed from @math surviving nodes is achieved, where @math . Existing results show that the sub-packetization @math of an @math high code rate (i.e., @math ) MDS code with optimal repair access is at least @math . In this paper, we propose a class of multi-layer transformed MDS codes such that the sub-packetization is @math , where @math , and the repair access is optimal for any single node. We show that the sub-packetization of the proposed multi-layer transformed MDS codes is strictly less than the existing known lower bound when @math , achieving by restricting the choice of @math specific helper nodes in repairing a failed node. We further propose multi-layer transformed EVENODD codes that have optimal repair access for any single node and lower sub-packetization than the existing binary MDS array codes with optimal repair access for any single node. With our multi-layer transformation, we can design new MDS codes that have the properties of low computational complexity, optimal repair access for any single node, and relatively small sub-packetization, all of which are critical for maintaining the reliability of distributed storage systems.
There are other practical concerns in distributed storage systems, such as how to mitigate the computational complexity. Binary MDS array codes are a special class of MDS codes that have low computational complexity, since the encoding and decoding procedures only involve XOR operations. Typical examples of binary MDS array codes are EVENODD @cite_8 @cite_6 , X-code @cite_12 and RDP @cite_33 @cite_10 . Some efficient decoding methods of binary MDS array codes are given in @cite_9 @cite_19 @cite_14 @cite_23 @cite_24 . There have been also many studies @cite_29 @cite_0 @cite_30 @cite_9 @cite_26 on the optimal repair bandwidth of binary MDS array codes.
@cite_30 @cite_14 @cite_26 @cite_33 @cite_8 @cite_9 @cite_29 @cite_6 @cite_24 @cite_19 @cite_0 @cite_23 @cite_10 @cite_12
2963502306 2794738250 1622719107 2147343704 2890964310 2744811977 201688508 2963877468 2337263547 2886748290 2765335304 2115552168 2137291643
EVENODD codes are binary array codes for correcting double disk failures in RAID-6 with asymptotically optimal encoding and decoding complexities. However, the update complexity of EVENODD is sub-optimal. We propose a new construction of binary maximum distance separable array codes, namely EVENODD+, such that the encoding, decoding, and update complexities of EVENODD+ are less than those of EVENODD in general. Moreover, EVENODD+ achieves asymptotically optimal update complexity. Row-Diagonal Parity (RDP) is a new algorithm for protecting against double disk failures. It stores all data unencoded, and uses only exclusive-or operations to compute parity. RDP is provably optimal in computational complexity, both during construction and reconstruction. Like other algorithms, it is optimal in the amount of redundant information stored and accessed. RDP works within a single stripe of blocks of sizes normally used by file systems, databases and disk arrays. It can be utilized in a fixed (RAID-4) or rotated (RAID-5) parity placement style. It is possible to extend the algorithm to encompass multiple RAID-4 or RAID-5 disk arrays in a single RDP disk array. It is possible to add disks to an existing RDP array without recalculating parity or moving data. Implementation results show that RDP performance can be made nearly equal to single parity RAID-4 and RAID-5 performance. We present a novel method, that we call EVENODD, for tolerating up to two disk failures in RAID architectures. EVENODD employs the addition of only two redundant disks and consists of simple exclusive-OR computations. This redundant storage is optimal, in the sense that two failed disks cannot be retrieved with less than two redundant disks. A major advantage of EVENODD is that it only requires parity hardware, which is typically present in standard RAID-5 controllers. Hence, EVENODD can be implemented on standard RAID-5 controllers without any hardware changes. The most commonly used scheme that employes optimal redundant storage (i.e., two extra disks) is based on Reed-Solomon (RS) error-correcting codes. This scheme requires computation over finite fields and results in a more complex implementation. For example, we show that the complexity of implementing EVENODD in a disk array with 15 disks is about 50 of the one required when using the RS scheme. The new scheme is not limited to RAID architectures: it can be used in any system requiring large symbols and relatively short codes, for instance, in multitrack magnetic recording. To this end, we also present a decoding algorithm for one column (track) in error. > Consider a binary maximum distance separate (MDS) array code composed of an @math array of bits with @math information columns and @math parity columns, such that any @math out of @math columns suffice to reconstruct the @math information columns. Our goal is to provide optimal repair access for binary MDS array codes, meaning that the bandwidth triggered to repair any single failed information or parity column is minimized. In this paper, we propose a generic transformation framework for binary MDS array codes, using EVENODD codes as a motivating example, to support optimal repair access for @math , where @math denotes the number of non-failed columns that are connected for repair. In addition, we show that the efficient decoding property of the original EVENODD codes is maintained after transformation. Furthermore, we show how our transformation framework applies to general binary MDS array codes and enables them to support optimal repair access. Binary maximum distance separable (MDS) array codes are a special class of erasure codes for distributed storage that not only provide fault tolerance with minimum storage redundancy, but also achieve low computational complexity. They are constructed by encoding k information columns into r parity columns, in which each element in a column is a bit, such that any k out of the k + r columns suffice to recover all information bits. In addition to providing fault tolerance, it is critical to improve repair performance. Specifically, if a single column fails, our goal is to minimize the repair bandwidth by downloading the least amount of bits from d non-failed columns, where k ≤ d ≤ k + r − 1. However, existing binary MDS codes that achieve high data rates (i.e., k (k + r) > 1 2) and minimum repair bandwidth only support double fault tolerance (i.e., r = 2), which is insufficient for failure-prone distributed storage environments in practice. This paper fills the void by proposing an explicit construction of triple-fault-tolerant (i.e., r = 3) binary MDS array codes that achieve asymptotically minimum repair bandwidth for d = k + 1. An improved musical instrument strap attaching, holding, and supporting device and method for supporting, for example, guitars by slitted straps utilizing uniquely shaped and designed retaining devices. The novel attaching, holding and supporting device is usually located at the bottom end of the guitar body for all types of guitars and also near the neck of the guitar for electic guitars (FIG. 1). The device includes an attachment wedge, usually a screw for electric guitars or wooden wedge for either "F hole" or folk or classic guitars, and a central stem portion which is cylindrical in shape which mates with the attachment wedge on one end and a strap retaining head on the other end. The strap retaining head is elongated at one end, forming a generally isosceles triangular shape with curved corners, similar to that of a plectrum, and has a hemispherical projection on its inner side facing the guitar body the combination being used to support the body of the guitar by a shoulder strap or sling placed between the guitar body and the strap retainer and connected by friction and weight to the shoulder of the person playing the guitar and, in the case of "F Hole" or folk or classic guitars, to the neck of the guitar by other means such as a string (FIG. 2). The elongated tip of the retaining head is initially inserted into the slit of the strap in a lateral direction and then rotated 90 DEG . The longest dimension of the retainer head is preferrably greater than the length of the slit, and the distance between the tip of the hemispherical projection and the bottom of the central stem is preferrably less than the thickness of the strap. Array codes are used widely in data storage systems such as redundant array of independent disks. The row-diagonal parity (RDP) codes and EVENODD codes are two popular double-parity array codes. The increasing capacity of hard disks demands better fault tolerance by using array codes with three or more parity disks. Although many extensions of RDP and EVENODD codes have been proposed, their main drawback is high decoding complexity. In this paper, we propose a unified form of RDP and EVENODD codes under which RDP codes can be treated as shortened EVENODD codes. Moreover, an efficient decoding algorithm based on an LU factorization of a Vandermonde matrix is proposed. The LU decoding method is applicable to all the erasure patterns of RDP and EVENODD codes with three parity columns. It is also applicable to the erasure decoding of RDP and EVENODD codes with more than three parity columns when the number of continuous surviving parity columns is no less than the number of erased information columns and the first parity column has not failed. The proposed efficient decoding algorithm is also applicable to other Vandermonde array codes, with less decoding complexity than that of the existing method. The generalized RDP codes are identified as the most practical and efficient triple-erasure correcting MDS (maximum-distance separable) codes, since they can encode optimally and support arbitrary code length. However, none of the existing decoding algorithms for these codes is adequate in that their decoding complexity leaves a relatively large room for improvement. In this letter, we present an improved decoding algorithm for the generalized RDP codes. Compared with the existing decoding algorithms, the proposed algorithm has a much lower decoding complexity, which is very close to the theoretical lower bound. Binary maximum distance separable (MDS) array codes contain @math information columns and @math parity columns in which each entry is a bit that can tolerate @math arbitrary erasures. When a column in an MDS code fails, it has been proven that we must download at least half of the content from each helper column if @math columns are selected as the helper columns. If the lower bound is achieved such that the @math helper columns can be selected from any @math surviving columns, then the repair is an optimal repair. Otherwise, if the lower bound is achieved with @math specific helper columns, the repair is a weak-optimal repair. This paper proposes a class of binary MDS array codes with @math and @math that asymptotically achieve weak-optimal repair of an information column with @math helper columns. We show that there exist many encoding matrices such that the corresponding binary MDS array codes can asymptotically achieve weak-optimal repair for repairing any information column. Array codes have been widely used in communication and storage systems. To reduce computational complexity, one important property of the array codes is that only exclusive OR operations are used in the encoding and decoding processes. Cauchy Reed–Solomon codes, Rabin-like codes, and circulant Cauchy codes are existing Cauchy maximum-distance separable (MDS) array codes that employ Cauchy matrices over finite fields, circular permutation matrices, and circulant Cauchy matrices, respectively. All these codes can correct any number of failures; however, a critical drawback of existing codes is the high decoding complexity. In this paper, we propose a new construction of Rabin-like codes based on a quotient ring with a cyclic structure. The newly constructed Rabin-like codes have more supported parameters (prime @math is extended to an odd number), such that the world sizes of them are more flexible than the existing Cauchy MDS array codes. An efficient decoding method using LU factorization of the Cauchy matrix can be applied to the newly constructed Rabin-like codes. It is shown that the decoding complexity of the proposed approach is less than that of existing Cauchy MDS array codes. Hence, the Rabin-like codes based on the new construction are attractive to distributed storage systems. In P. Corbett et a. (2004), the authors present a row-diagonal parity scheme with two parity columns for a (p - 1) times (p + 1) array, p a prime, that recovers any two erased columns. The code minimizes the number of XORs at the encoding. It was left as an open problem generalizing this scheme to multiple parities. In this paper, we present such a generalization. In particular, when we have three parity columns, the new code recovers any three erased columns. Efficient encoding and decoding algorithms are presented We present a new class of MDS (maximum distance separable) array codes of size n spl times n (n a prime number) called X-code. The X-codes are of minimum column distance 3, namely, they can correct either one column error or two column erasures. The key novelty in X-code is that it has a simple geometrical construction which achieves encoding update optimal complexity, i.e., a change of any single information bit affects exactly two parity bits. The key idea in our constructions is that all parity symbols are placed in rows rather than columns.