Kruglik S.; Dudina M.; Potapova V.; Frolov A.
Abstract — We investigate one possible generalization of locallyrecoverable codes (LRC) with all-symbol locality and availabilitywhen recovering sets can intersect in a small number of coor-dinates. This feature allows us to increase the achievable coderate and still meet load balancing requirements. In this paper wederive an upper bound for the rate of such codes and give explicitconstructions of codes with such a property. These constructionsutilize LRC codes developed by Wang et al.
I. INTRODUCTION
A locally recoverable code (LRC) is a code over finitealphabet such that each symbol is a function of small numberof other symbols that form a recovering set [1], [2], [3], [4],[5]. These codes are important due to their applications indistributed and cloud storage systems. LRC codes are well-investigated in the literature. The bounds on the rate andminimum code distance are given in [1], [3] for the caseof large alphabet size. The alphabet-dependent shorteningbound (see [6] for the method explanation) is proposed in [7].Optimal code constructions are given in [8] based on rank-metric codes (for large alphabet size, which is an exponentialfunction of the code length) and in [9] based on Reed-Solomoncodes (for small alphabet, which is a linear function of thecode length).
The natural generalization of an LRC code is an LRCcode with availability (or multiple disjoint recovering sets).Availability allows us to handle multiple simultaneous requeststo erased symbol in parallel. This property is very importantfor hot data that is simultaneously requested by a large numberof users. The case of LRC codes with availability is muchless investigated. Bounds on parameters of such codes andconstructions are given in [4], [10], [11], [12], [13]. Mostof the papers focused on information-symbol locality andavailability. In what follows we are interested in all-symbollocality and availability that is preferable in applications as itpermits a uniform approach to system design.
The property of availability decreases maximum achievablecode rate [10]. In this paper we propose a new generalizationof LRC codes with availability. Namely, we assume thatrecovering sets can intersect in a small number of coordinates.This feature allows us to increase the achievable code rate andstill meet load balancing requirements. It must be mentionedthat some examples of such codes can be obtained from (r, δ)a codes from [14]. Unfortunately, for the case of small overlap(which is the topic of our work) the code rate of such codesis smaller than the code rate of our codes.
Our contribution is as follows. We investigate one possiblegeneralization of locally recoverable codes (LRC) with all-symbol locality and availability when recovering sets canintersect in a small number of coordinates. We derive an upperbound for the rate of such codes and give explicit constructionsof codes with such a property. These constructions utilize LRC codes developed in [15].
Читать статью On one generalization of LRC codes with availability
