On the maximal code length of optimal linear LRC codes with availability

On the maximal code length of optimal linear LRC codes with availability

Kruglik S.; Nazirkhanova K.; Frolov A.

Abstract — A code over finite alphabet is said to be locally recoverable (LRC) if each code symbol is function of small number of other symbols forming the recovering set [1], [2], [3], [4], [5]. These codes were first proposed in [1] and immediate become popular due to obvious applications in distributed and cloud storage systems. Natural generalization of LRC codes is LRC codes with availability in which each code symbol has more than one disjoint recovering set. A LRC codes with availability is said to be optimal if its minimum distance achieves the Singleton- like bound developed by Kruglik et. al in this paper we study the maximum code length of q-ary optimal LRC with availability and then derive some structural properties.

I. INTRODUCTION

Data coding with locality is a rapidly developing area in coding theory that was initially motivated by applications in distributed storage but since has expanded to applications in databases, with links to other parts of information theory (e.g., index coding and network coding) as well as to computer science in general. Temporary and permanent server failures in storage systems require new coding schemes that support efficient and fast data recovery without overloading system re- sources such as the number of reads, repair bandwidth, latency and others. Coding solutions relied on Reed-Solomon (RS) codes have been implemented in the file systems of Facebook and Google. These codes have been also standardized as a part of the well-known RAID 6 data protection technology. At the same time, RS does not meet the requirements for these applications due to big amount of inter-server communications during the procedure of one symbol recovery. This problem give rise to area of active research called codes with locality. Let us define it more formally. A locally recoverable code (LRC) is a code over finite alphabet such that each symbol is a function of small number of other symbols that form a recovering set [1], [2], [3], [4], [5], [6], [7], [8]. LRC codes are well-investigated in the literature. The bounds on the rate and minimum code distance are given in [1], [3] for the case of large alphabet size. The alphabet-dependent shortening bound (see [9] for the method explanation) is proposed in [10]. Optimal code constructions are given in [11] based on rank- metric codes (for large alphabet size, which is an exponential function of the code length) and in [12] based on Reed- Solomon codes (for small alphabet, which is a linear function of the code length).
The natural generalization of an LRC code is an LRC code with availability (or multiple disjoint recovering sets). Availability allows us to handle multiple simultaneous requests to erased symbols in parallel. This property is very important for hot data that is simultaneously requested by a large number of users. Bounds on parameters of such codes and constructions are given in [4], [6], [13], [14], [15]. In what follows we are interested in all-symbol locality and availability.
LRC codes with availability that attain bound on the min- mum distance proved in [6] are called optimal LRC codeswith availability. This bound is in fact generalization of the classical Singleton bound for linear codes with locality and availability constraints.
In this paper we continue research started in [16] and extend it to the case of LRC codes with availability. Our contribution is as follows. New upper bound on code length of optimal LRC codes with availability are derived and structural properties of them are investigated.

Читать статью On the maximal code length of optimal linear LRC codes with availability

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *