Consider that a set of balls of n different colors are thrown into m bins with the assumption that the ball number of each color is constant and the number of balls in each bin is also constant. Our optimal goal is to find a feasible placement such that the distinct colors of remaining balls should be at least c after removing any k bins (k ≤ m) with the minimum number of balls. We present that the optimal colored bins in bins is equivalent to the optimization of Fractional Repetition (FR) codes in distributed storage systems. Here balls correspond to coded packets and bins correspond to storage nodes. This problem can be represented as biregualr graph and then deduced to the Zarankiewicz problem, which is a well-known extremal graph theoretic problem. We present the problem with the relation to combinatorial design theory, especially t-designs and propose the explicit construction algorithm for the optimization problem from t-designs. Some constructions of the optimized FR codes by 2-designs are analyzed to tolerate the desired k fault-tolerance with c = n - 1.

We present a novel secret sharing scheme where the secret is an autotopism (a symmetry) of a Latin square. Previously proposed secret sharing schemes involving Latin squares have many drawbacks: (a) Latin squares contain $$n^2$$ entries, which may be too large, (b) partial information about the secret may be directly revealed, (c) a subsequently discovered subtle “flaw”, (d) difficulty in initialization and reconstruction, (e) difficulty in verification, and (f) difficulty in generalizing to a multi-level scheme. We carefully analyze the security of the proposed scheme, and identify how it overcomes all of these problems.

To maximize the reliability of erasure coded objects in cloud storage, the optimal allocation is a challenging problem constrained with the node heterogeneities and erasure coding budgets. We model the optimal problem from a combinatorial view under multiple constraints and propose an efficient search algorithm to find the most reliable allocation. The experiments are evaluated and analyzed including the optimal reliability, redundancy reduction and allocation pattern.

To ensure high reliability and storage efficiency, erasure codes are preferred in storage systems. With the prevalent of distributed storage systems such as clouds storage, how to design a scalable and efficient erasure-resilient code is challenging. We propose a scalable binary linear code to keep up with data growth which has the following properties. Given the group size k and the code block length n, the proposed code corrects any two bit erasures among the n bits. The redundancy overhead of the code is 2/(k + 2), and each data bit affects exactly 2 parity bits. As results of these properties, if a data bit is changed or added, only two parity bits need to be updated; and the recovery of an erasured bit requires accessing at most k other bits and the recovery of two erasured bits requires at most 2k other bits. We give the construction algorithm by the order expansion of regular graphs; moreover, we optimize the failure resilience during the construction procedure. Compared with existing codes, our proposed code has notable benefits in storage scalability, redundancy overhead and I/O bandwidth. The deployment of the proposed code in distributed storage systems can be simple and practical.

In this paper, we study binary pattern erasure codes, i.e., binary codes that are resiliant to erasures from a family P of possible erasures. We give an algorithmic proof of the existence of a binary linear code with codewords of length n that is resiliant to erasures from P when P satisfies the properties: every pattern p ϵ P has size m and every letter in the alphabet occurs in at most c patterns. The density of the parity matrix is plays a important role in storage applications, so we also introduce a new low density code basing on graph theory.

Most of the modern hard disk drives support Self-Monitoring, Analysis and Reporting Technology (SMART), which can monitor internal attributes of individual drives and predict impending drive failures by a thresholding method. As the prediction performance of the thresholding algorithm is disappointing, some researchers explored various statistical and machine learning methods for predicting drive failures based on SMART attributes. However, the failure detection rates of these methods are only up to 50% ~ 60% with low false alarm rates (FARs). We explore the ability of Backpropagation (BP) neural network model to predict drive failures based on SMART attributes. We also develop an improved Support Vector Machine (SVM) model. A real-world dataset concerning 23,395 drives is used to verify these models. Experimental results show that the prediction accuracy of both models is far higher than previous works. Although the SVM model achieves the lowest FAR (0.03%), the BP neural network model is considerably better in failure detection rate which is up to 95% while keeping a reasonable low FAR.

Heterogeneity is the natural feature in distributed networks. Different from the traditional disk array, the amount of data allocated on heterogenous peers may be not the same. To maximize the reliability of stored data objects in heterogeneous networks, the optimal allocation of erasure-coded fragments is a challenging problem constrained with heterogeneous peer availabilities and redundancy overhead. This paper examines this optimal problem considered MDS erasure codes applied into distributed storage networks. First, we model the reliability of an allocation with the weighted-k-out-of-s model and extend its properties to efficiently calculate the reliability of an allocation; then we reduce the reliability computation of a given allocation to linear computation cost based on the weighted k-out-of-s model. Then, we deduce the problem to integer partition problem and propose two order-based search algorithms. Our experiments show that our proposed algorithms can be applied to find the optimal allocations efficiently in various practical coding cases. Furthermore, we evaluate the performance of our proposed search algorithms with some practical storage settings, and then present experimental results including the reliability, redundancy overheads and allocation pattern for the optimal allocation driven by practical network traces.

Major web search engines answer thousands of queries per second requesting information about billions of web pages. The data sizes and query loads are growing at an exponential rate. To manage the heavy workload, we consider techniques for utilizing a Graphics Processing Unit (GPU). We investigate new approaches to improve two important operations of search engines -- lists intersection and index compression. For lists intersection, we develop techniques for efficient implementation of the binary search algorithm for parallel computation. We inspect some representative real-world datasets and find that a sufficiently long inverted list has an overall linear rate of increase. Based on this observation, we propose Linear Regression and Hash Segmentation techniques for contracting the search range. For index compression, the traditional d-gap based compression schemata are not well-suited for parallel computation, so we propose a Linear Regression Compression schema which has an inherent parallel structure. We further discuss how to efficiently intersect the compressed lists on a GPU. Our experimental results show significant improvements in the query processing throughput on several datasets.

In this paper, we study longest lowest-density MDS codes, a simple kind of multi-erasure array code with optimal redundancy and minimum update penalty. We prove some basic structure properties for longest lowest-density MDS codes. We define a "perfect" property for near-resolvable block designs (NRBs) and establish a bijection between 3-erasure longest lowest-density MDS codes (T-Codes) and perfect NRB(3¿ + 1, 3, 2)s. We present a class of NRB(3¿+1, 3, 2)s, and prove that it produces a family of T-Codes. This family is infinite assuming Artin¿s Conjecture. We also test some other NRBs and find some T-Code instances outside of this family.

X-code is an important 2-erasure correcting vertical array code. In this paper, we present a combinatorial representation for X-code. It is based on graph representation of binary linear/array codes. We represent X-code by Cayley tables of the cyclic groups of prime order - a special column-Hamiltonian Latin squares (CHLS). This representation is helpful to comprehend X-code's 2-erasure correcting ability. We also show the inner relationship between X-code and the liberation codes though the former is a vertical code and the latter is a horizontal code. A possible way to construct the 2-erasure vertical codes like X-code using common CHLS is also proposed.

Storage applications are in urgent need of multi-erasure codes. But there is no consensus on the best coding technique. Hafner has presented a class of multi-erasure codes named HoVer codes [1]. This kind of codes has a unique data/parity layout which provides a range of implementation options that cover a large portion of the performance/efficiency trade-off space. Thus it can be applied to many scenarios by simple tuning. In this paper, we give a combinatorial representation of a family of double-erasure HoVer codes - create a mapping between this family of codes and Latin squares. We also present two families of double-erasure HoVer codes respectively based on the column-Hamiltonian Latin squares (of odd order) and a family of Latin squares of even order. Compared with the double-erasure HoVer codes presented in [1], the new codes enable greater flexibility in performance and efficiency trade-off.

In this paper, we present PDH Latin - a new class of 2-erasure horizontal codes with dependent parity symbols based on column-Hamiltonian Latin squares (CHLS). We prove that PDH Latin codes are MDS codes. We also present a new class of 2-erasure parity independent mixed codes based on CHLS - PIMLatin. We show that the performance of the new codes is comparable to or better than other codes of this kind. They have perfect parameter flexibility and structure variety that benefit performance. We also discuss code shortening technologies that can improve parameter flexibility, structure variety and reliability. Borrowing ideas from vertical shortening, we develop a 2-erasure array code construction method using non-Hamiltonian Latin squares.

In recent years, multi-erasure correcting coding systems have become more pervasive. RAID6 is an important 2-erasure correcting code specification. But there is no consensus on the best concrete RAID6 coding scheme. Plank developed a brand new class of RAID6 codes called the Liberation codes that achieves good encoding, updating and decoding performance. In this paper, we present a chained decoding algorithm for the Liberation codes. Its performance is comparable with the bit matrix scheduling algorithm developed by Plank, but is more intuitive and reveals the essence better. In the process, we present a new class of Liberation codes called the Latin Liberation codes. These codes are based on column-hamiltonian Latin squares, hence the name. They are superior to the Liberation codes in parameter flexibility and structure flexibility. Finally, we analyze the performance of several XOR-based RAID6 codes and give some suggestion on their application.

With the rapid progress of the capacity and slow pace of the speed/MTTF of hard disks, and increasing size of storage systems, the reliability and availability of storage systems become more and more serious. This paper discusses the method of constructing double- and triple-erasure-correcting codes via combining mirroring and parity approaches in details, and presents a double-erasure code MPDC and a triple-erasure code MPPDC based on one-factorizations of complete graphs. The two codes are simple, easy to implement, and have no disk number limitation. They achieve perfect fault-free load balance and approximately optimal reconstruction load balance. The simulation results show that, compared with other double- and triple-erasure codes, MPDC and MPPDC have comparative light-load and moderate-load performance and better heavy-load performance in fault-free mode. Because parity declustering is used, the two codes are far superior to the other double- and triple-erasure codes in degraded- and reconstruction-mode performance.

In this paper, we present a new class of t-erasure horizontal codes with independent parity symbols based on Column-Hamiltonian Latin squares (CHLS). We call the codes PIHLatin (parity independent horizontal Latin) codes. We prove the necessary and sufficient condition of the existence of PIHLatin codes for t=2. For tges3, we prove some necessary conditions of the existence of PIHLatin codes. We also prove the bijection between 2-erasure PIHLatin-like codes and CHLSs and prove the mapping from t-erasure PIHLatin-like codes to t-1 mutually orthogonal CHLSs for t>2. The performance analysis shows that PIHLatin codes are superior to other multi-erasure array codes in flexibility and variety. Moreover, PIHLatin codes are suitable for both traditional disk arrays and distributed storage systems.