SCIENCE CHINA Information Sciences, Volume 63 , Issue 2 : 122304(2020) https://doi.org/10.1007/s11432-019-2649-5

Locally repairable codes from combinatorial designs

Yu ZHANG 1,2,3,4, Haibin KAN 1,2,3,4,*
• AcceptedSep 18, 2019
• PublishedJan 15, 2020
Share
Rating

Abstract

Locally repairable codes (LRCs) were proposed to reduce the repair degree in distributed storage systems. In particular, LRCs with availability are highly desirable for distributed storage systems, since this kind of codes provide the mechanism of local repair for code symbols and parallel reading of hot data. In this paper, we propose four types of $(n,k,r,t)_q$ LRCs from combinatorial designs. We introduce several constructions of LRCs with strict availability and some constructions of distance-optimal LRCs with information-symbol locality. Most of our constructions in this paper are over $\mathbb{F}_2$, i.e., they are suitable for implementation.

Acknowledgment

This work was supported by National Natural Science Foundation of China (Grant No. 61672166), Plan of Shanghai Excellent Academic Leaders (Grant No. 16XD1400200), Innovation Plan of Shanghai Science and Technology (Grant No. 16JC1402700) and Shanghai Leading Talent Programmes.

Appendix A.

References

[1] Balaji S B, Krishnan M N, Vajha M. Erasure coding for distributed storage: an overview. Sci China Inf Sci, 2018, 61: 100301 CrossRef Google Scholar

[2] Dimakis A G, Godfrey P B, Wu Y. Network Coding for Distributed Storage Systems. IEEE Trans Inform Theor, 2010, 56: 4539-4551 CrossRef Google Scholar

[3] Liang S T, Liang W J, Kan H B. Construction of one special minimum storage regenerating code when α=2. Sci China Inf Sci, 2015, 58: 1-10 CrossRef Google Scholar

[4] Gopalan P, Huang C, Simitci H. On the Locality of Codeword Symbols. IEEE Trans Inform Theor, 2012, 58: 6925-6934 CrossRef Google Scholar

[5] Jin L F, Ma L M, Xing C P. Construction of optimal locally repairable codes via automorphism groups of rational function fields. 2017,. arXiv Google Scholar

[6] Jin L. Explicit Construction of Optimal Locally Recoverable Codes of Distance 5 and 6 via Binary Constant Weight Codes. IEEE Trans Inform Theor, 2019, 65: 4658-4663 CrossRef Google Scholar

[7] Prakash N, Kamath G M, Lalitha V, et al. Optimal linear codes with a local-error-correction property. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Cambridge, 2012. 2776--2780. Google Scholar

[8] Anyu Wang , Zhifang Zhang . Repair Locality With Multiple Erasure Tolerance. IEEE Trans Inform Theor, 2014, 60: 6979-6987 CrossRef Google Scholar

[9] Rawat A S, Papailiopoulos D S, Dimakis A G. Locality and Availability in Distributed Storage. IEEE Trans Inform Theor, 2016, 62: 4481-4493 CrossRef Google Scholar

[10] Su Y S. Design of membership matrices for $(r,~t)$-availability in distributed storage. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Barcelona, 2016. 998--1002. Google Scholar

[11] Hao J, Xia S T. Constructions of Optimal Binary Locally Repairable Codes With Multiple Repair Groups. IEEE Commun Lett, 2016, 20: 1060-1063 CrossRef Google Scholar

[12] Balaji S B, Vijay Kumar P. Bounds on the rate and minimum distance of codes with availability. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Aachen, 2017. 3155--3159. Google Scholar

[13] Zhang Y, Kan H. Locally repairable codes with strict availability from linear functions. Sci China Inf Sci, 2018, 61: 109304 CrossRef Google Scholar

[14] Balaji S B, Prasanth K P, Kumar P V. Binary codes with locality for multiple erasures having short block length. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Barcelona, 2016. 655--659. Google Scholar

[15] Tamo I, Barg A, Frolov A. Bounds on the Parameters of Locally Recoverable Codes. IEEE Trans Inform Theor, 2016, 62: 3070-3083 CrossRef Google Scholar

[16] Prakash N, Lalitha V, Kumar P V. Codes with locality for two erasures. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Honolulu, 2014. 1962--1966. Google Scholar

[17] Colbourn C J, Dinitz J H. Handbook of Combinatorial Designs. 2nd ed. Boca Raton: CRC Press, 2006. Google Scholar

[18] Wan Z X. Design Theory. Beijing: Higher Education Press, 2009. Google Scholar

[19] Wang A, Zhang Z, Liu M. Achieving arbitrary locality and availability in binary codes. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Hong Kong, 2015. 1866--1870. Google Scholar

[20] Huang P, Yaakobi E, Uchikawa H, et al. Linear locally repairable codes with availability. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Hong Kong, 2015. 1871--1875. Google Scholar

[21] Olmez O, Ramamoorthy A. Repairable replication-based storage systems using resolvable designs. In: Proceedings of the 50th Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2012. 1174--1181. Google Scholar

Citations

• 0

Altmetric

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有