Please wait a minute...
Journal of ZheJiang University (Engineering Science)  2024, Vol. 58 Issue (3): 501-509    DOI: 10.3785/j.issn.1008-973X.2024.03.007
    
Construction of locally repairable codes based on orthogonal Latin square
Shuaishuai LIU(),Jing WANG*(),Zhe LIU,Zhonghuan XU
1. School of Information Engineering, Chang’an University, Xi’an 710064, China
Download: HTML     PDF(950KB) HTML
Export: BibTeX | EndNote (RIS)      

Abstract  

The construction of binary locally repairable codes based on orthogonal Latin square was proposed, to resolve the problems of low code rate and high computational complexity of locally repairable codes with $ \left( {r,t} \right) $-locality. The incidence matrix was derived according to the corresponding relationship between the orthogonal Latin square elements and the positions of the digital matrix, and then the all symbol-locally repairable codes (AS-LRCs) were constructed based on the incidence matrix above. The AS-LRCs boasted asymptotically boundary conditions in terms of code rate and code length, and desired minimum distance. The single-check locally repairable codes with information $ \left( {r,t = 2} \right) $-locality were constructed by utilizing the incidence matrix concatenated with an identity matrix. The minimum distance and the code rate of the single-check locally repairable codes reached the optimal boundary conditions, making them be optimal locally repairable codes. Considering that there are nodes with high failure rate in practical distributed storage systems, the single-check information symbol-locally repairable codes (IS-LRCs) with high availability were further constructed through the orthogonal Latin square complete groups, of which the availability parameter $ t $ can be selected flexibly, and the robustness and the flexibility of distributed storage systems were improved.



Key wordsdistributed storage system      locally repairable code      orthogonal Latin square      minimum distance      node failure rate     
Received: 22 March 2023      Published: 05 March 2024
CLC:  TN 911.2  
Fund:  国家自然科学基金资助项目(62001059,62072054);陕西省自然科学基金资助项目(2021GY-019).
Corresponding Authors: Jing WANG     E-mail: ssliu@chd.edu.cn;jingwang@chd.edu.cn
Cite this article:

Shuaishuai LIU,Jing WANG,Zhe LIU,Zhonghuan XU. Construction of locally repairable codes based on orthogonal Latin square. Journal of ZheJiang University (Engineering Science), 2024, 58(3): 501-509.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2024.03.007     OR     https://www.zjujournals.com/eng/Y2024/V58/I3/501


基于正交拉丁方的局部修复码构造

针对目前具有$ \left( {r,t} \right) $局部性的局部修复码码率较低且构造过程中计算复杂度过高的问题,提出基于正交拉丁方的二元局部修复码构造方法. 根据正交拉丁方元素与矩阵位置的对应关系构造关联矩阵,得到具有全符号局部性的局部修复码(AS-LRCs),该码的码率和码长渐近边界条件,且最小距离较大. 利用关联矩阵级联单位矩阵构造信息位具有$ \left( {r,t = 2} \right) $局部性的单校验局部修复码,该码的最小距离和码率均满足最优边界条件,为最优局部修复码. 考虑到实际分布式存储系统中存在高故障率节点,利用正交拉丁方完备组构造具有信息位局部性的高可用性单校验局部修复码(IS-LRCs),可以灵活选择可用性$ t $,提高了系统的鲁棒性与灵活性.


关键词: 分布式存储系统,  局部修复码,  正交拉丁方,  最小距离,  节点故障率 
构造方法$ n $$ k $$ r $$ d $
基于完全图构造的
AS-LRCs[15]
$ C^2_{r+2} $$ C^2_{r+1} $$ \forall r $3
基于区组设计构造
的AS-LRCs[18]
$ C^2_{r+2} $$ C^2_{r+1} $$ \forall r $3
基于奇偶校验矩阵构造的
AS-LRCs[19]
$ \left( {r+2} \right)w $$ rw $$ \forall r $3
基于定理4构造的
AS-LRCs
$ {m^2} $$ {\left( {m - 1} \right)^2} $$ m - 1 $4
Tab.1 Comparison of structural parameters of several typical AS-LRCs
Fig.1 Code rate comparison with availability $ t = 2 $
构造方法$ n $$ k $$ R $
基于定理9构造的IS-LRCs$ tr+{r^2} $$ {r^2} $$ r/\left( {r+t} \right) $
基于阵列LDPC码构造的
IS-LRCs[21]
$ {r^2}+rt+1 $$ {r^2} $$ {r^2}/\left( {{r^2}+rt+1} \right) $
基于正则矩阵构造的
IS-LRCs(其中$ \delta = 3 $)[10]
$ v+2vt/r $$ v $$ r/\left( {r+2t} \right) $
Tab.2 Comparison of structural parameters of several typical IS-LRCs
Fig.2 Code rate comparison with locality $ r = 11 $
[1]   SIDDIQA A, KARIM A, GANI A Big data storage technologies: a survey[J]. Frontiers of Information Technology and Electronic Engineering, 2017, 18 (8): 1040- 1070
doi: 10.1631/FITEE.1500441
[2]   LI J, LI B C Demand-aware erasure coding for distributed storage systems[J]. IEEE Transactions on Cloud Computing, 2021, 9 (2): 532- 545
doi: 10.1109/TCC.2018.2885306
[3]   李鑫, 孙蓉, 刘景伟 分布式存储系统中容错技术综述[J]. 无线电通信技术, 2019, 45 (5): 463- 475
LI Xin, SUN Rong, LIU Jingwei Overview of fault-tolerant techniques in distributed storage system[J]. Radio Communication Technology, 2019, 45 (5): 463- 475
doi: 10.3969/j.issn.1003-3114.2019.05.002
[4]   GOPALAN P, HUANG C, SIMITCI H, et al On the locality of codeword symbols[J]. IEEE Transactions on Information Theory, 2012, 58 (11): 6925- 6934
doi: 10.1109/TIT.2012.2208937
[5]   TAMO I, PAPAILIOPOULOS D S, DIMAKIS A G Optimal locally repairable codes and connections to matroid theory[J]. IEEE Transactions on Information Theory, 2016, 62 (12): 6661- 6671
doi: 10.1109/TIT.2016.2555813
[6]   JIN L F, MA L M, XING C P Construction of optimal locally repairable codes via automorphism groups of rational function fields[J]. IEEE Transactions on Information Theory, 2020, 66 (1): 210- 221
doi: 10.1109/TIT.2019.2946637
[7]   LUO Y, XING C P, YUAN C Optimal locally repairable codes of distance 3 and 4 via cyclic codes[J]. IEEE Transactions on Information Theory, 2019, 65 (2): 1048- 1053
doi: 10.1109/TIT.2018.2854717
[8]   RAWAT A S, PAPAILIOPOULOS D S, DIMAKIS A G, et al Locality and availability in distributed storage[J]. IEEE Transactions on Information Theory, 2016, 62 (8): 4481- 4493
doi: 10.1109/TIT.2016.2524510
[9]   JIN L F, KAN H B, ZHANG Y Constructions of locally repairable codes with multiple recovering sets via rational function fields[J]. IEEE Transactions on Information Theory, 2020, 66 (1): 202- 209
doi: 10.1109/TIT.2019.2946627
[10]   HAO J, SHUM K W, XIA S T, et al Optimal locally repairable codes for parallel reading[J]. IEEE Access, 2020, 8: 80447- 80453
doi: 10.1109/ACCESS.2020.2992188
[11]   MA J X, GE G N Optimal binary linear locally repairable codes with disjoint repair groups[J]. SIAM Journal on Discrete Mathematics, 2019, 33 (4): 2509- 2529
doi: 10.1137/19M1248443
[12]   TAN P, ZHOU Z C, SIDORENKO V, et al Two classes of optimal LRCs with information (r, t)-locality[J]. Designs Codes and Cryptography, 2020, 88 (11): 1741- 1757
[13]   HAO J, XIA S T Constructions of optimal binary locally repairable codes with multiple repair groups[J]. IEEE Communications Letters, 2016, 20 (6): 1060- 1063
doi: 10.1109/LCOMM.2016.2539160
[14]   TAMO I, BARG A, FROLOV A Bounds on the parameters of locally recoverable codes[J]. IEEE Transactions on Information Theory, 2016, 62 (6): 3070- 3083
doi: 10.1109/TIT.2016.2518663
[15]   PRAKASH N, LALITHA V, BALAJI S B, et al Codes with locality for two erasures[J]. IEEE Transactions on Information Theory, 2019, 65 (12): 7771- 7789
doi: 10.1109/TIT.2019.2934124
[16]   COLBOURN C J, DINITZ J H. Handbook of combinatorial designs [M]. 2nd ed. Boca Raton: CRC Press, 2006.
[17]   HAO J, SHUM K W, XIA S T, et al. On optimal quaternary locally repairable Codes [C]// 2021 IEEE International Symposium on Information Theory . Melbourne: ISIT, 2021: 3267−3272.
[18]   WANG A Y, ZHANG Z F, LIU M L. Achieving arbitrary locality and availability in binary codes [C]// 2015 IEEE International Symposium on Information Theory . Hong Kong: ISIT, 2015: 1866−1870.
[19]   JING Z, SONG H Y. A construction of 2-sequential-recovery locally repairable codes [C]// 2021 IEEE International Conference on Information and Communication Technology Convergence . Jeju Island: ICTC, 2021: 1431−1433.
[20]   HU Y P, LIU Y H, LI W J, et al Unequal failure protection coding technique for cloud storage systems[J]. IEEE Transactions on Cloud Computing, 2021, 9 (1): 386- 400
doi: 10.1109/TCC.2017.2785396
[1] TU Li-Hua, CHEN Gang, WANG Wei, CHEN Ke, DONG Jin-Xiang. Containerbased self-organizing storage model[J]. Journal of ZheJiang University (Engineering Science), 2010, 44(5): 915-922.