ON SOME CONSTRUCTIONS OF LOCALLY RECOVERABLE CODES

Abstract

In this thesis, we have worked on a class of erasure codes called locally recoverable (LRC) codes, and they are designed specifically to address the problem of node failures in distributed storage systems. These codes were formally introduced by Gopalan et al. (Gopalan et al., 2012) and have been widely studied by many researchers in recent years due to their applications in distributed storage systems. LRC codes have the ability to quickly recover the erased data, which reduces the time and cost of data recovery. In distributed storage systems, the data handlers use many different approaches to maintain data reliability such as replication and error-correcting codes. The replication of data provides good local recovery of nodes in the event of a node failure, but when the data is large, this technique is not a good solution to this problem as it causes a big overhead. Another approach to address the problem of node failures is to use errorcorrecting codes, such as Reed-Solomon (RS) codes, to recover the erased symbols. This approach reduces the data overhead, but it does not provide an efficient solution to single node failures. For example, in an [n;k] RS code of length n and dimension k, the reconstruction of any node needs k other nodes, and therefore in this case, k times more data is required for recovering a single node. Locally recoverable codes efficiently address the problem of single node failures, and the focus of these codes is on minimizing the number of nodes needed to recover a failed node. The smallest number of nodes used to recover a failed node is called the locality of that node. If every coordinate in a code C has locality less than on equal to an integer r, then C is said to have locality r. LRC codes have been generalized in many ways according to the requirements of storage systems. For instance, storages have some part of the data which is in more demand than the other parts. Such data is accessed by a large number of users at the same time and is called hot data. One generalization of LRC codes suitable for such a scenario is LRC codes with availability. In these codes, every node has more than one disjoint recovering sets. Therefore, several users can access the same data at the same time by using its different recovering sets. This class of codes has been further generalized by Kruglik et al. (2017), in which the recovering sets of a coordinate need not be disjoint. These codes still satisfy the load balancing problem and provide repair alternatives. We have proposed a construction of such codes in this thesis. There are other generalizations of LRC codes that allow local recovery of more than one coordinate value. Several approaches have been introduced in the literature to handle multiple erasures such as sequential recovery, parallel recovery, cooperative recovery etc. One such generalization is codes with (r;d) locality. A code with (r;d) locality can locally recover d 􀀀1 erasures with the help of at most r other coordinate values. These codes are further generalized for the codes with hierarchical locality in which recovery of failed nodes can be made at different levels of hierarchy. We have worked on some of these generalizations of LRC codes. There are many constructions of LRC codes in the literature; one such construction was given by Tamo and Barg (Tamo & Barg, 2014b), which is based on the classical construction of Reed-Solomon (RS) codes. The codes so constructed are called RS-like LRC codes. In this construction, a subset A Fq of size n (called the base set) is used, and the encoding polynomial for a message block is evaluated at every point of A to get the corresponding codeword of length n. The set A is partitioned in such a manner that the sets of the partitions form the local sets of coordinates (any element of a local set can be reconstructed with the help of other members of that local set). In reference (Tamo & Barg, 2014b), the authors have constructed optimal LRC codes and further extended this construction to LRC codes with availability. In this thesis, we have given a construction for optimal RS-like LRC codes over a finite field Fq for any length n q. The construction of RS-like LRC codes given in (Tamo & Barg, 2014b) gives a class of optimal LRC codes over Fq with length n, dimension k and locality r. This construction is flexible in terms of parameters, but it also imposes a restriction on the code length n that it should be divisible by r +1. Later, in the same paper, this condition was lifted to a condition in which n must satisfy n 6= 1 mod (r+1). Another explicit construction of optimal LRC codes with this lifted condition has been given by Kolosov et al. (Kolosov et al., 2018). In this thesis, we have given a construction of RS-like LRC codes which completely removes any such restriction on the length of the code, i.e., an LRC code of any length n q can be constructed with the help of the given construction. All lengths of the codes are covered by this construction, together with the cases n mod (r+1) = 0 and n mod (r+1) = r already covered by (Tamo & Barg, 2014b) and (Kolosov et al., 2018). Moreover, it is proved that the constructed codes are optimal for their parameters. Further, we have extended the construction of RS-like LRC codes to LRC codes with multiple recovering sets in which the recovering sets of a coordinate position can have a small number of elements in common. To construct an LRC code with t intersecting recovering sets, we need t different partitions of the base set which satisfy the condition that the intersection of any two sets from the different partitions has less than or equal to x+1 elements, where x is a small, fixed non-negative integer. Then the constructed code has t recovering sets for every coordinate position, and no two recovering sets have more than x elements in common. To find such partitions, we use the coset partitions of the subgroups of the multiplicative group F q and the additive group F+ q . Further, we give a result that ensures the existence of a certain number of such partitions (coset partitions of the subgroups of F+ q ). We have also determined a bound on the minimum distance of such codes. Moreover, we have obtained a condition for the cyclic LRC codes to have intersecting recovering sets. We have established a connection between LRC codes and linear complementary dual (LCD) codes. In (Carlet & Guilley, 2015), authors have proved that LCD codes are useful against certain attacks like side-channel attacks. In distributed storage systems, communication between the nodes and basic computation on data take place during the recovering process of failed nodes. During these communications, the security of the data is also an important factor. As both families of codes have their advantages in distributed storage systems, this connection is beneficial for these systems considering both node failure and security aspects. In this thesis, we have given constructions of cyclic LRC codes that are also LCD codes, and we call them LRC-LCD codes. We first present a construction of binary LRC-LCD codes, and then a construction of LRC-LCD codes over an arbitrary finite field Fq. Next, we present a construction for cyclic LRC codes with (r;d) locality that are also LCD codes. We generalize this connection for LRC codes with hierarchical locality. The cases when constructed LRC-LCD codes are optimal LRC codes are also studied in this thesis. We have studied the locality of quasi-cyclic codes and found some interesting results about their locality properties. The class of QC codes is a natural generalization of cyclic codes, and they have been studied extensively in the literature. The generator matrix of a QC code can be written in terms of circulant matrices, and every circulant matrix is associated with a polynomial. In this thesis, we have obtained some bounds on the locality of a QC code in terms of the weights of the polynomials associated with these circulant matrices. We have presented an algorithm to find the locality of a QC code. Further, we have studied the locality of 1-generator QC codes and presented a construction of LRC codes from this class using the zeros of their generator polynomials.