On The Average Locality Of Locally Repairable Codes With Tow Erasures

In recent years,Locally Repairable Codes(LRCs)have been widely used in Distributed Storage System(DSS).LRC that recovers a failure with at most r other symbols has locality r.The average locality of restoring any two erasures of an LRC(r2)directly affects the costly repair bandwidth,disk I/O,and number of nodes involved in the repair process of two missing data blocks.Inspired by the average locality r of LRCs,this thesis is focused on researching r2 the average number of nodes that need to access to recover any two erasures at the same time.This paper mainly studies the bounds of r2 the average number of nodes that LRCs need to access to recover any two erasures at the same time through cooperative approach and the LRCs structures that achieve the bounds.The main innovations and research contents of this paper are as follows:Firstly,the recovery strategy of cooperative mode is introduced to calculate the r2 of LRCs(n,k,d).A general bound of r2 is given.At the same time,the bound of r2 is proposed under a specific structure that LRCs satisfy the Variable Nodes(VNs)covered by any two local Check Groups(CGs)do not overlap.And then a LRC construction algorithm is proposed,through which the LRCs structure achieving the bound can be constructed.Secondly,it is concluded that the CGs in Tanner diagram of LRCs consists of two parts:local CGs and global CGs.When any two VNs are lost,the local CGs are considered firstly and then the global CGs are considered in recovery process.Therefore,optimizing r2 can be divided into two steps.First,constructing optimal local CGs,and then the global CGs are further optimized.The main tasks include the following three aspects.Firstly,the bounds of r2 under three kinds of r-optimal LRCs structure are proved strictly.Secondly,the LRCs structure achieving the corresponding bound is obtained.Thirdly,focusing on the third class of r-optimal LRCs with high code rate,an LRC construction algorithm achieving the bound of r2 is proposed.Subsequently,a Tanner graph of LRC is constructed,and the parity-check matrix H satisfying Tanner graph is found.Finally,we introduce the decoding algorithm with the cooperative strategy in detail.The algorithm can calculate r2 by parity-check matrix H of LRCs.Calculating the r2 of some three kinds of r-optimal LRCs and the r2 of the LRCs constructed in this paper under the same parameters(n,k,d).By comparing the data,it is found that all the r2 of LRCs constructed in this paper are improved in different degrees compared with the r2 of three kinds of r-optimal LRCs.Meanwhile,comparing the bound of r2 under the specific structure with the three kinds of T-optimal LRCs structure,it is found that the bounds o.f r2 under the the specific structure are tighter in different degrees.