Regular ( k , R , 1)-packings with max ( R ) = 3 $\max \limits {(R)}=3$ and their locally repairable codes
- PDF / 343,419 Bytes
- 19 Pages / 439.642 x 666.49 pts Page_size
- 80 Downloads / 145 Views
Regular (k , R , 1)-packings with max (R ) = 3 and their locally repairable codes Jing Jiang1
· Minquan Cheng1
Received: 20 May 2019 / Accepted: 26 January 2020 / © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The concept of a locally repairable code (LRC) was introduced to protect the data from disk failures in large-scale storage systems. In this paper, we consider the LRCs with multiple disjoint repair sets and each repair set contains exactly one check symbol. By using several structures from combinatorial design theory, such as balanced incomplete block design, cyclic packing, group divisible design, near-Skolem sequence and Langford sequence, we construct several infinite classes of LRCs with the size of each repair set at most 3, which are optimal with respect to the bound proposed by Rawat et al. in 2016. Keywords Locally repairable code · Packing · Cyclic packing Mathematics Subject Classification (2010) 94B25 · 68P30
1 Introduction Right now, large-scale cloud storage and distributed file systems such as Amazon Elastic Block Store and Google File System have reached such a massive scale that the disk failures are the norm. In order to protect the data from disk failures, one can make replication of data packets. However, it suffers a larger storage overhead. So new techniques for such a problem is desired. In a storage system, an [n, k] storage code encodes k information symbols to n symbols and stores them across n disks. In order to reduce the number of symbols connecting during the repair process, the concept of locally repairable code was introduced in [5] to protect the data from disk failures in these systems. The authors showed that, by using a linear [n, k, d] code with locally repairable property, an erasure of a codeword can be recovered by only accessing other r k symbols. Jing Jiang
[email protected] Minquan Cheng [email protected] 1
Guangxi Key Lab of Multi-source Information Mining & Security, Guangxi Normal University, Guilin, China
Cryptography and Communications
In this paper, we focus on a linear [n, k, d] code with (r, δ; 1)c -locality, which provides the code symbol with δ − 1 multiple disjoint repair sets of size at most r and each repair set contains exactly one check symbol. Such a code was introduced by Rawat et al. in [9], and was constructed blue by evaluations of specially constructed polynomials over a finite filed [15], resolvable designs [10], partial geometries [4, 8], resolvable configurations [13], and packings [1], respectively. Recently, Tan et al. [16] gave some constructions of such codes by using linear algebra and combinatorial designs and summarized Table 1 where some known results of optimal LRCs were listed. In this paper, based on the results in [1], by using several structures from combinatorial design theory, such as balanced incomplete block design, cyclic packing, group divisible design, near-Skolem sequence and Langford sequence, we construct linear [n, k, d] codes with (3, δ, 1)c -locality (Theorem 2), w
Data Loading...
