Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
Locally Repairable Codes with Multiple Repair Alternatives  [PDF]
Lluis Pamies-Juarez,Henk D. L. Hollmann,Frédérique Oggier
Computer Science , 2013,
Abstract: Distributed storage systems need to store data redundantly in order to provide some fault-tolerance and guarantee system reliability. Different coding techniques have been proposed to provide the required redundancy more efficiently than traditional replication schemes. However, compared to replication, coding techniques are less efficient for repairing lost redundancy, as they require retrieval of larger amounts of data from larger subsets of storage nodes. To mitigate these problems, several recent works have presented locally repairable codes designed to minimize the repair traffic and the number of nodes involved per repair. Unfortunately, existing methods often lead to codes where there is only one subset of nodes able to repair a piece of lost data, limiting the local repairability to the availability of the nodes in this subset. In this paper, we present a new family of locally repairable codes that allows different trade-offs between the number of contacted nodes per repair, and the number of different subsets of nodes that enable this repair. We show that slightly increasing the number of contacted nodes per repair allows to have repair alternatives, which in turn increases the probability of being able to perform efficient repairs. Finally, we present pg-BLRC, an explicit construction of locally repairable codes with multiple repair alternatives, constructed from partial geometries, in particular from Generalized Quadrangles. We show how these codes can achieve practical lengths and high rates, while requiring a small number of nodes per repair, and providing multiple repair alternatives.
Locally Repairable Codes with Functional Repair and Multiple Erasure Tolerance  [PDF]
Wentu Song,Chau Yuen
Mathematics , 2015,
Abstract: We consider the problem of designing [n; k] linear codes for distributed storage systems (DSS) that satisfy the (r, t)-Local Repair Property, where any t'(<=t) simultaneously failed nodes can be locally repaired, each with locality r. The parameters n, k, r, t are positive integers such that r
Locally Repairable Codes  [PDF]
Dimitris S. Papailiopoulos,Alexandros G. Dimakis
Mathematics , 2012,
Abstract: Distributed storage systems for large-scale applications typically use replication for reliability. Recently, erasure codes were used to reduce the large storage overhead, while increasing data reliability. A main limitation of off-the-shelf erasure codes is their high-repair cost during single node failure events. A major open problem in this area has been the design of codes that {\it i)} are repair efficient and {\it ii)} achieve arbitrarily high data rates. In this paper, we explore the repair metric of {\it locality}, which corresponds to the number of disk accesses required during a {\color{black}single} node repair. Under this metric we characterize an information theoretic trade-off that binds together locality, code distance, and the storage capacity of each node. We show the existence of optimal {\it locally repairable codes} (LRCs) that achieve this trade-off. The achievability proof uses a locality aware flow-graph gadget which leads to a randomized code construction. Finally, we present an optimal and explicit LRC that achieves arbitrarily high data-rates. Our locality optimal construction is based on simple combinations of Reed-Solomon blocks.
Some Improvements on Locally Repairable Codes  [PDF]
Jun Zhang,Xin Wang,Gennian Ge
Mathematics , 2015,
Abstract: The locally repairable codes (LRCs) were introduced to correct erasures efficiently in distributed storage systems. LRCs are extensively studied recently. In this paper, we first deal with the open case remained in \cite{q} and derive an improved upper bound for the minimum distances of LRCs. We also give an explicit construction for LRCs attaining this bound. Secondly, we consider the constructions of LRCs with any locality and availability which have high code rate and minimum distance as large as possible. We give a graphical model for LRCs. By using the deep results from graph theory, we construct a family of LRCs with any locality $r$ and availability $2$ with code rate $\frac{r-1}{r+1}$ and optimal minimum distance $O(\log n)$ where $n$ is the length of the code.
Binary Linear Locally Repairable Codes  [PDF]
Pengfei Huang,Eitan Yaakobi,Hironori Uchikawa,Paul H. Siegel
Mathematics , 2015,
Abstract: Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed storage. Most existing results on LRCs do not explicitly take into consideration the field size $q$, i.e., the size of the code alphabet. In particular, for the binary case, only a few results are known. In this work, we present an upper bound on the minimum distance $d$ of linear LRCs with availability, based on the work of Cadambe and Mazumdar. The bound takes into account the code length $n$, dimension $k$, locality $r$, availability $t$, and field size $q$. Then, we study binary linear LRCs in three aspects. First, we focus on analyzing the locality of some classical codes, i.e., cyclic codes and Reed-Muller codes, and their modified versions, which are obtained by applying the operations of extend, shorten, expurgate, augment, and lengthen. Next, we construct LRCs using phantom parity-check symbols and multi-level tensor product structure, respectively. Compared to other previous constructions of binary LRCs with fixed locality or minimum distance, our construction is much more flexible in terms of code parameters, and gives various families of high-rate LRCs, some of which are shown to be optimal with respect to their minimum distance. Finally, availability of LRCs is studied. We investigate the locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and $4$-cycle free regular low-density parity-check (LDPC) codes. We also show the construction of a long LRC with availability from a short one-step majority-logic decodable code.
Optimal Locally Repairable and Secure Codes for Distributed Storage Systems  [PDF]
Ankit Singh Rawat,O. Ozan Koyluoglu,Natalia Silberstein,Sriram Vishwanath
Mathematics , 2012,
Abstract: This paper aims to go beyond resilience into the study of security and local-repairability for distributed storage systems (DSS). Security and local-repairability are both important as features of an efficient storage system, and this paper aims to understand the trade-offs between resilience, security, and local-repairability in these systems. In particular, this paper first investigates security in the presence of colluding eavesdroppers, where eavesdroppers are assumed to work together in decoding stored information. Second, the paper focuses on coding schemes that enable optimal local repairs. It further brings these two concepts together, to develop locally repairable coding schemes for DSS that are secure against eavesdroppers. The main results of this paper include: a. An improved bound on the secrecy capacity for minimum storage regenerating codes, b. secure coding schemes that achieve the bound for some special cases, c. a new bound on minimum distance for locally repairable codes, d. code construction for locally repairable codes that attain the minimum distance bound, and e. repair-bandwidth-efficient locally repairable codes with and without security constraints.
Security in Locally Repairable Storage  [PDF]
Abhishek Agarwal,Arya Mazumdar
Mathematics , 2015,
Abstract: In this paper we extend the notion of {\em locally repairable} codes to {\em secret sharing} schemes. The main problem that we consider is to find optimal ways to distribute shares of a secret among a set of storage-nodes (participants) such that the content of each node (share) can be recovered by using contents of only few other nodes, and at the same time the secret can be reconstructed by only some allowable subsets of nodes. As a special case, an eavesdropper observing some set of specific nodes (such as less than certain number of nodes) does not get any information. In other words, we propose to study a locally repairable distributed storage system that is secure against a {\em passive eavesdropper} that can observe some subsets of nodes. We provide a number of results related to such systems including upper-bounds and achievability results on the number of bits that can be securely stored with these constraints.
Optimal Locally Repairable Codes via Rank-Metric Codes  [PDF]
Natalia Silberstein,Ankit Singh Rawat,O. Ozan Koyluoglu,Sriram Vishwanath
Mathematics , 2013,
Abstract: This paper presents a new explicit construction for locally repairable codes (LRCs) for distributed storage systems which possess all-symbols locality and maximal possible minimum distance, or equivalently, can tolerate the maximal number of node failures. This construction, based on maximum rank distance (MRD) Gabidulin codes, provides new optimal vector and scalar LRCs. In addition, the paper also discusses mechanisms by which codes obtained using this construction can be used to construct LRCs with efficient repair of failed nodes by combination of LRC with regenerating codes.
Optimal Locally Repairable Codes and Connections to Matroid Theory  [PDF]
Itzhak Tamo,Dimitris S. Papailiopoulos,Alexandros G. Dimakis
Mathematics , 2013,
Abstract: Petabyte-scale distributed storage systems are currently transitioning to erasure codes to achieve higher storage efficiency. Classical codes like Reed-Solomon are highly sub-optimal for distributed environments due to their high overhead in single-failure events. Locally Repairable Codes (LRCs) form a new family of codes that are repair efficient. In particular, LRCs minimize the number of nodes participating in single node repairs during which they generate small network traffic. Two large-scale distributed storage systems have already implemented different types of LRCs: Windows Azure Storage and the Hadoop Distributed File System RAID used by Facebook. The fundamental bounds for LRCs, namely the best possible distance for a given code locality, were recently discovered, but few explicit constructions exist. In this work, we present an explicit and optimal LRCs that are simple to construct. Our construction is based on grouping Reed-Solomon (RS) coded symbols to obtain RS coded symbols over a larger finite field. We then partition these RS symbols in small groups, and re-encode them using a simple local code that offers low repair locality. For the analysis of the optimality of the code, we derive a new result on the matroid represented by the code generator matrix.
On the Combinatorics of Locally Repairable Codes via Matroid Theory  [PDF]
Thomas Westerb?ck,Ragnar Freij,Toni Ernvall,Camilla Hollanti
Mathematics , 2014,
Abstract: This paper provides a link between matroid theory and locally repairable codes (LRCs) that are either linear or more generally almost affine. Using this link, new results on both LRCs and matroid theory are derived. The parameters $(n,k,d,r,\delta)$ of LRCs are generalized to matroids, and the matroid analogue of the generalized Singleton bound in [P. Gopalan et al., "On the locality of codeword symbols," IEEE Trans. Inf. Theory] for linear LRCs is given for the parameters $(n,k,d,r,\delta)$ of a matroid. It is shown that the given bound is not tight for certain classes of parameters, which implies a non-existence result for the corresponding optimal locally repairable almost affine codes. Constructions of classes of matroids with a large span of different properties on the parameters $(n,k,d,r,\delta)$ and the corresponding local repair sets are given. With the aid of these matroid constructions, new methods for constructing linear LRCs are provided. The constructions are based on a collection of subsets of a finite set with an associated function on these subsets, or a graph with associated functions on the vertices and edges, and finally result in several classes of optimal linear LRCs. The existence results on linear LRCs and the non-existence results on almost affine LRCs given in this paper strengthen the non-existence and existence results on optimal linear LRCs given in [W. Song et al., "Optimal locally repairable codes," IEEE Sel. Areas Commun.].
Page 1 /100
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.