We introduce a new family of erasure codes, called group decodable code (GDC), for distributed storage system. Given a set of design parameters ; ; k; t , where k is the number of information symbols, each codeword of an ( ; ; k; t)-group decodable code is a t-tuple of strings, called buckets, such that each bucket is a string of symbols that is a codeword of a [ ; ] MDS code (which is encoded from information symbols). Such codes have the following two properties: (P1) Locally Repairable: Each code symbol has locality ( ; - + 1). (P2) Group decodable: From each bucket we can decode information symbols. We establish an upper bound of the minimum distance of ( ; ; k; t)-group decodable code for any given set of ; ; k; t ; We also prove that the bound is achievable when the coding field F has size |F| > n-1 k-1.
In @cite_12 , the concept of @math -locality was defined, which captures the property that there exist @math pairwise disjoint local repair sets for a code symbol. An upper bound on the minimum distance for @math linear codes with information @math -locality was derived, and codes that attain this bound was constructed for the length @math . However, for @math , it is not known whether there exist codes attaining this bound. Upper bounds on the rate and minimum distance of codes with all-symbol @math -locality was proved in @cite_13 . However, no explicit construction of codes that achieve this bound was presented. It is still an open question whether the distance bound in @cite_13 is achievable.
@cite_13 @cite_12
2963120590 2018102393
A locally recoverable code (LRC code) is a code over a finite alphabet such that every symbol in the encoding is a function of a small number of other symbols that form a recovering set. Bounds on the rate and distance of such codes have been extensively studied in the literature. In this paper we derive upper bounds on the rate and distance of codes in which every symbol has t ≥ 1 disjoint recovering sets. In distributed storage systems, erasure codes with locality (r ) are preferred because a coordinate can be locally repaired by accessing at most (r ) other coordinates which in turn greatly reduces the disk I O complexity for small (r ) . However, the local repair may not be performed when some of the (r ) coordinates are also erased. To overcome this problem, we propose the ((r, )_ c ) -locality providing ( -1 ) nonoverlapping local repair groups of size no more than (r ) for a coordinate. Consequently, the repair locality (r ) can tolerate ( -1 ) erasures in total. We derive an upper bound on the minimum distance for any linear ([n,k] ) code with information ((r, )_ c ) -locality. Then, we prove existence of the codes that attain this bound when (n k(r( -1)+1) ) . Although the locality ((r, ) ) defined by provides the same level of locality and local repair tolerance as our definition, codes with ((r, )_ c ) -locality attaining the bound are proved to have more advantage in the minimum distance. In particular, we construct a class of codes with all symbol ((r, )_ c ) -locality where the gain in minimum distance is ( ( r ) ) and the information rate is close to 1.