SCIENCE CHINA Information Sciences, Volume 61, Issue 10: 100301(2018) https://doi.org/10.1007/s11432-018-9482-6

## Erasure coding for distributed storage: an overview$^\dagger$

• AcceptedJul 7, 2018
• PublishedSep 6, 2018
Share
Rating

### Abstract

In a distributed storage system, code symbols are dispersed across space in nodes or storage units as opposed to time. In settings such as that of a large data center, an important consideration is the efficient repair of a failed node. Efficient repair calls for erasure codes that in the face of node failure, are efficient in terms of minimizing the amount of repair data transferred over the network, the amount of data accessed at a helper node as well as the number of helper nodes contacted. Coding theory has evolved to handle these challenges by introducing two new classes of erasure codes, namely regenerating codes and locally recoverable codes as well as by coming up with novel ways to repair the ubiquitous Reed-Solomon code.This survey provides an overview of the efforts in this direction that have taken place over the past decade.

### References

[1] Rashmi K V, Shah N B, Gu D, et al. A solution to the network challenges of data recovery in erasure-coded distributed storage systems: a study on the facebook warehouse cluster. In: Proceedings of the 5th USENIX Workshop on Hot Topics in Storage and File Systems, San Jose, 2013. Google Scholar

[2] Sathiamoorthy M, Asteris M, Papailiopoulos D. XORing elephants. Proc VLDB Endow, 2013, 6: 325-336 CrossRef Google Scholar

[3] Dimakis A G, Ramchandran K, Wu Y N. A survey on network codes for distributed storage. Proc IEEE, 2011, 99: 476-489 CrossRef Google Scholar

[4] Datta A, Oggier F. An overview of codes tailor-made for better repairability in networked distributed storage systems. SIGACT News, 2013, 44: 89 CrossRef Google Scholar

[5] Li J, Li B. Erasure coding for cloud storage systems: a survey. Tinshhua Sci Technol, 2013, 18: 259-272 CrossRef Google Scholar

[6] Liu S Q, Oggier F. An overview of coding for distributed storage systems. In: Network Coding and Subspace Designs. Berlin: Springer, 2018. 363--383. Google Scholar

[7] Dimakis A G, Godfrey P B, Wu Y. Network coding for distributed storage systems. IEEE Trans Inf Theory, 2010, 56: 4539-4551 CrossRef Google Scholar

[8] Wu Y. Existence and construction of capacity-achieving network codes for distributed storage. IEEE J Sel Areas Commun, 2010, 28: 277-288 CrossRef Google Scholar

[9] Shah N B, Rashmi K V, Kumar P V. Interference alignment in regenerating codes for distributed storage: necessity and code constructions. IEEE Trans Inf Theory, 2012, 58: 2134-2158 CrossRef Google Scholar

[10] Hu Y C, Chen H C H, Lee P P C, et al. NCCloud: applying network coding for the storage repair in a cloud-of-clouds. In: Proceedings of the 10th USENIX Conference on File and Storage Technologies, San Jose, 2012. Google Scholar

[11] Krishnan M N, Kumar P V. On MBR codes with replication. In: Proceedings of IEEE International Symposium on Information Theory, Barcelona, 2016. 71--75. Google Scholar

[13] Rashmi K V, Shah N B, Kumar P V, et al. Explicit construction of optimal exact regenerating codes for distributed storage. In: Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2009. 1243--1249. Google Scholar

[14] Rashmi K V, Shah N B, Kumar P V. Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction. IEEE Trans Inf Theory, 2011, 57: 5227-5239 CrossRef Google Scholar

[15] Lin S J, Chung W H. Novel repair-by-transfer codes and systematic exact-MBR codes with lower complexities and smaller field sizes. IEEE Trans Parallel Distrib Syst, 2014, 25: 3232-3241 CrossRef Google Scholar

[16] Han Y S, Pai H T, Zheng R. Update-efficient error-correcting product-matrix codes. IEEE Trans Commun, 2015, 63: 1925-1938 CrossRef Google Scholar

[17] Raviv N. Asymptotically optimal regenerating codes over any field. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 1416--1420. Google Scholar

[18] Mahdaviani K, Khisti A, Mohajer S. Bandwidth adaptive & error resilient MBR exact repair regenerating codes. 2017,. arXiv Google Scholar

[19] Wu Y, Dimakis A G. Reducing repair traffic for erasure coding-based storage via interference alignment. In: Proceedings of IEEE International Symposium on Information Theory, Seoul, 2009. 2276--2280. Google Scholar

[20] Suh C, Ramchandran K. Exact-repair MDS code construction using interference alignment. IEEE Trans Inf Theory, 2011, 57: 1425-1442 CrossRef Google Scholar

[21] Lin S J, Chung W H, Han Y S. A unified form of exact-MSR codes via product-matrix frameworks. IEEE Trans Inf Theory, 2015, 61: 873-886 CrossRef Google Scholar

[22] Papailiopoulos D S, Dimakis A G, Cadambe V R. Repair optimal erasure codes through Hadamard designs. IEEE Trans Inf Theory, 2013, 59: 3021-3037 CrossRef Google Scholar

[23] Cadambe V R, Jafar S A, Maleki H. Asymptotic interference alignment for optimal repair of MDS codes in distributed storage. IEEE Trans Inf Theory, 2013, 59: 2974-2987 CrossRef Google Scholar

[24] Tamo I, Wang Z, Bruck J. Zigzag codes: MDS array codes with optimal rebuilding. IEEE Trans Inf Theory, 2013, 59: 1597-1616 CrossRef Google Scholar

[25] Wang Z Y, Tamo I, Bruck J. On codes for optimal rebuilding access. In: Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2011. 1374--1381. Google Scholar

[26] Cadambe V R, Huang C, Li J, et al. Polynomial length MDS codes with optimal repair in distributed storage. In: Proceedings of the 45th Asilomar Conference on Signals, Systems and Computers, Pacific Grove, 2011. 1850--1854. Google Scholar

[27] Wang Z Y, Tamo I, Bruck J. Long MDS codes for optimal repair bandwidth. In: Proceedings of IEEE International Symposium on Information Theory, Cambridge, 2012. 1182--1186. Google Scholar

[28] Tamo I, Wang Z Y, Bruck J. Access versus bandwidth in codes for storage. IEEE Trans Inf Theory, 2014, 60: 2028-2037 CrossRef Google Scholar

[29] Goparaju S, Tamo I, Calderbank R. An improved sub-packetization bound for minimum storage regenerating codes. IEEE Trans Inf Theory, 2014, 60: 2770-2779 CrossRef Google Scholar

[30] Sasidharan B, Agarwal G K, Kumar P V. A high-rate MSR code with polynomial sub-packetization level. In: Proceedings of IEEE International Symposium on Information Theory, Hong Kong, 2015. 2051--2055. Google Scholar

[31] Rawat A S, Koyluoglu O O, Vishwanath S. Progress on high-rate MSR codes: enabling arbitrary number of helper nodes. In: Proceedings of Information Theory and Applications Workshop, La Jolla, 2016. Google Scholar

[32] Goparaju S, Fazeli A, Vardy A. Minimum storage regenerating codes for all parameters. IEEE Trans Inf Theory, 2017, 63: 6318-6328 CrossRef Google Scholar

[33] Agarwal G K, Sasidharan B, Kumar P V. An alternate construction of an access-optimal regenerating code with optimal sub-packetization level. In: Proceedings of the 21st National Conference on Communications, Mumbai, 2015. Google Scholar

[34] Alon N. Combinatorial nullstellensatz. Combinator Probab Comp, 1999, 8: 7-29 CrossRef Google Scholar

[35] Raviv N, Silberstein N, Etzion T. Constructions of high-rate minimum storage regenerating codes over small fields. IEEE Trans Inf Theory, 2017, 63: 2015-2038 CrossRef Google Scholar

[36] Ye M, Barg A. Explicit constructions of high-rate MDS array codes with optimal repair bandwidth. IEEE Trans Inf Theory, 2017, 63: 2001-2014 CrossRef Google Scholar

[37] Ye M, Barg A. Explicit constructions of optimal-access MDS codes with nearly optimal sub-packetization. IEEE Trans Inf Theory, 2017, 63: 6307-6317 CrossRef Google Scholar

[38] Sasidharan B, Vajha M, Kumar P V. An explicit, coupled-layer construction of a high-rate MSR code with low sub-packetization level, small field size and all-node repair. 2016,. arXiv Google Scholar

[39] Li J, Tang X H, Tian C. A generic transformation for optimal repair bandwidth and rebuilding access in MDS codes. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 1623--1627. Google Scholar

[40] Balaji S B, Kumar P V. A tight lower bound on the sub-packetization level of optimal-access MSR and MDS codes. 2018,. arXiv Google Scholar

[41] Vajha M, Balaji S B, Kumar P V. Explicit MSR codes with optimal access, optimal sub-packetization and small field size for $d~=~k~+~1,~k~+~2,~k~+~3$. 2018,. arXiv Google Scholar

[42] Mahdaviani K, Mohajer S, Khisti A. Product matrix MSR codes with bandwidth adaptive exact repair. IEEE Trans Inf Theory, 2018, 64: 3121-3135 CrossRef Google Scholar

[43] Shah N B, Rashmi K V, Kumar P V. Distributed storage codes with repair-by-transfer and nonachievability of interior points on the storage-bandwidth tradeoff. IEEE Trans Inf Theory, 2012, 58: 1837-1852 CrossRef Google Scholar

[44] Tian C. Characterizing the rate region of the (4,3,3) exact-repair regenerating codes. IEEE J Sel Areas Commun, 2014, 32: 967-975 CrossRef Google Scholar

[45] Information theory inequality prover. 2016. http://user-www.ie.cuhk.edu.hk/~ITIP/. Google Scholar

[46] Yeung R W. A framework for linear information inequalities. IEEE Trans Inf Theory, 1997, 43: 1924-1934 CrossRef Google Scholar

[47] Tian C, Sasidharan B, Aggarwal V. Layered exact-repair regenerating codes via embedded error correction and block designs. IEEE Trans Inf Theory, 2015, 61: 1933-1947 CrossRef Google Scholar

[48] Senthoor K, Sasidharan B, Kumar P V. Improved layered regenerating codes characterizing the exact-repair storage-repair bandwidth tradeoff for certain parameter sets. In: Proceedings of IEEE Information Theory Workshop, Jerusalem, 2015. Google Scholar

[49] Sasidharan B, Senthoor K, Kumar P V. An improved outer bound on the storage repair-bandwidth tradeoff of exact-repair regenerating codes. In: Proceedings of IEEE International Symposium on Information Theory, Honolulu, 2014. 2430--2434. Google Scholar

[50] Duursma I M. Outer bounds for exact repair codes. 2014,. arXiv Google Scholar

[51] Duursma I M. Shortened regenerating codes. IEEE Trans Inf Theory (Early Access), 2018. doi: 10.1109/TIT.2018. 2840995. Google Scholar

[52] Mohajer S, Tandon R. New bounds on the $(n,~k,~d)$ storage systems with exact repair. In: Proceedings of IEEE International Symposium on Information Theory, Hong Kong, 2015. 2056--2060. Google Scholar

[53] Sasidharan B, Prakash N, Krishnan M N. Outer bounds on the storage-repair bandwidth trade-off of exact-repair regenerating codes. Int J Inf Coding Theory, 2016, 3: 255-298 CrossRef Google Scholar

[54] Elyasi M, Mohajer S. Determinant coding: a novel framework for exact-repair regenerating codes. IEEE Trans Inf Theory, 2016, 62: 6683-6697 CrossRef Google Scholar

[55] Elyasi M, Mohajer S. Exact-repair trade-off for $(n,~k~=~d~-~1,~d)$ regenerating codes. In: Proceedings of the 55th Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2017. 934--941. Google Scholar

[56] Prakash N, Krishnan M N. The storage-repair-bandwidth trade-off of exact repair linear regenerating codes for the case $d=k=n-1$. In: Proceedings of IEEE International Symposium on Information Theory, Hong Kong, 2015. 859--863. Google Scholar

[57] Elyasi M, Mohajer S, Tandon R. Linear exact repair rate region of $(k~+~1,~k,~k)$ distributed storage systems: a new approach. In: Proceedings of IEEE International Symposium on Information Theory (ISIT), Hong Kong, 2015. 2061--2065. Google Scholar

[58] Hu Y, Xu Y, Wang X. Cooperative recovery of distributed storage systems from multiple losses with network coding. IEEE J Sel Areas Commun, 2010, 28: 268-276 CrossRef Google Scholar

[59] Kermarrec A M, Scouarnec N L, Straub G. Repairing multiple failures with coordinated and adaptive regenerating codes. In: Proceedings of International Symposium on Networking Coding, Beijing, 2011. Google Scholar

[60] Shum K W, Hu Y. Cooperative regenerating codes. IEEE Trans Inf Theory, 2013, 59: 7229-7258 CrossRef Google Scholar

[61] Wang A Y, Zhang Z F. Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage. In: Proceedings of IEEE INFOCOM, Turin, 2013. 400--404. Google Scholar

[62] Shum K W, Chen J. Cooperative repair of multiple node failures in distributed storage systems. Int J Inf Coding Theory, 2016, 3: 299-323 CrossRef Google Scholar

[63] Scouarnec N L. Exact scalar minimum storage coordinated regenerating codes. In: Proceedings of IEEE International Symposium on Information Theory, Cambridge, 2012. 1197--1201. Google Scholar

[64] Ye M, Barg A. Optimal MDS codes for cooperative repair. 2018,. arXiv Google Scholar

[65] Liu S Q, Oggier F E. On storage codes allowing partially collaborative repairs. In: Proceedings of IEEE International Symposium on Information Theory Proceedings, Honolulu, 2014. 2440--2444. Google Scholar

[66] Liu S Q, Oggier F E. Two storage code constructions allowing partially collaborative repairs. In: Proceedings of International Symposium on Information Theory and its Applications, Melbourne, 2014. 378--382. Google Scholar

[67] Koyluoglu O O, Rawat A S, Vishwanath S. Secure cooperative regenerating codes for distributed storage systems. IEEE Trans Inf Theory, 2014, 60: 5228-5244 CrossRef Google Scholar

[68] Huang K, Parampalli U, Xian M. Security concerns in minimum storage cooperative regenerating codes. IEEE Trans Inf Theory, 2016, 62: 6218-6232 CrossRef Google Scholar

[69] Rashmi K V, Shah N B, Ramchandran K. A piggybacking design framework for read-and download-efficient distributed storage codes. IEEE Trans Inf Theory, 2017, 63: 5802--5820. Google Scholar

[70] Guruswami V, Rawat A S. MDS code constructions with small sub-packetization and near-optimal repair bandwidth. In: Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, Barcelona, 2017. 2109--2122. Google Scholar

[71] Kralevska K, Gligoroski D, Overby H. General sub-packetized access-optimal regenerating codes. IEEE Commun Lett, 2016, 20: 1281-1284 CrossRef Google Scholar

[72] Rawat A S, Tamo I, Guruswami V, et al. $\epsilon$-MSR codes with small sub-packetization. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 2043--2047. Google Scholar

[73] Rouayheb S Y E, Ramchandran K. Fractional repetition codes for repair in distributed storage systems. In: Proceedings of the 48th Annual Allerton Conference on Communication, Control, and Computing, Allerton, 2010. Google Scholar

[74] Pawar S, Noorshams N, Rouayheb S Y E, et al. DRESS codes for the storage cloud: simple randomized constructions. In: Proceedings of IEEE International Symposium on Information Theory Proceedings, St. Petersburg, 2011.łinebreak 2338--2342. Google Scholar

[75] Silberstein N, Etzion T. Optimal fractional repetition codes based on graphs and designs. IEEE Trans Inf Theory, 2015, 61: 4164-4180 CrossRef Google Scholar

[76] Olmez O, Ramamoorthy A. Fractional repetition codes with flexible repair from combinatorial designs. IEEE Trans Inf Theory, 2016, 62: 1565-1591 CrossRef Google Scholar

[77] Koo J C, Gill J T. Scalable constructions of fractional repetition codes in distributed storage systems. In: Proceedings of the 49th Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2011. 1366--1373. Google Scholar

[78] Ernvall T. The existence of fractional repetition codes. 2012,. arXiv Google Scholar

[79] Pawar S, Rouayheb S Y E, Ramchandran K. Securing dynamic distributed storage systems against eavesdropping and adversarial attacks. IEEE Trans Inf Theory, 2011, 57: 6734-6753 CrossRef Google Scholar

[80] Rashmi K V, Shah N B, Ramchandran K, et al. Regenerating codes for errors and erasures in distributed storage. In: Proceeding of IEEE International Symposium on Information Theory Proceedings, Cambridge, 2012. 1202--1206. Google Scholar

[81] Rashmi K V, Shah N B, Ramchandran K. Information-theoretically secure erasure codes for distributed storage. IEEE Trans Inf Theory, 2018, 64: 1621-1646 CrossRef Google Scholar

[82] Tandon R, Amuru S D, Clancy T C. Toward optimal secure distributed storage systems with exact repair. IEEE Trans Inf Theory, 2016, 62: 3477-3492 CrossRef Google Scholar

[83] Rawat A S, Koyluoglu O O, Silberstein N. Optimal locally repairable and secure codes for distributed storage systems. IEEE Trans Inf Theory, 2014, 60: 212-236 CrossRef Google Scholar

[84] Goparaju S, Rouayheb S Y E, Calderbank R, et al. Data secrecy in distributed storage systems under exact repair. In: Proceedings of International Symposium on Network Coding, Calgary, 2013. Google Scholar

[85] Huang K, Parampalli U, Xian M. On secrecy capacity of minimum storage regenerating codes. IEEE Trans Inf Theory, 2017, 63: 1510-1524 CrossRef Google Scholar

[86] Rawat A S. Secrecy capacity of minimum storage regenerating codes. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 1406--1410. Google Scholar

[87] Kadhe S, Sprintson A. Security for minimum storage regenerating codes and locally repairable codes. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 1028--1032. Google Scholar

[88] Ye F, Shum K W, Yeung R W. The rate region for secure distributed storage systems. IEEE Trans Inf Theory, 2017, 63: 7038-7051 CrossRef Google Scholar

[89] Shao S, Liu T, Tian C. On the tradeoff region of secure exact-repair regenerating codes. IEEE Trans Inf Theory, 2017, 63: 7253-7266 CrossRef Google Scholar

[90] Han J, Lastras-Montano L A. Reliable memories with subline accesses. In: Proceedings of IEEE International Symposium on Information Theory, Nice, 2007. 2531--2535. Google Scholar

[91] Huang C, Chen M H, Li J. Pyramid codes: flexible schemes to trade space for access efficiency in reliable data storage systems. In: Proceedings of the 6th IEEE International Symposium on Network Computing and Applications, Cambridge, 2007. 79--86. Google Scholar

[92] Oggier F, Datta A. Self-repairing homomorphic codes for distributed storage systems. In: Proceedings of IEEE INFOCOM, Shanghai, 2011. 1215--1223. Google Scholar

[93] Gopalan P, Huang C, Simitci H. On the locality of codeword symbols. IEEE Trans Inf Theory, 2012, 58: 6925-6934 CrossRef Google Scholar

[94] Papailiopoulos D, Dimakis A. Locally repairable codes. In: Proceedings of IEEE International Symposium on Information Theory, Cambridge, 2012. 2771--2775. Google Scholar

[95] Forbes M, Yekhanin S. On the locality of codeword symbols in non-linear codes. Discrete Math, 2014, 324: 78-84 CrossRef Google Scholar

[96] 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 Proceedings, Cambridge, 2012. 2776--2780. Google Scholar

[97] Silberstein N, Rawat A S, Koyluoglu O O, et al. Optimal locally repairable codes via rank-metric codes. In: Proceedings of IEEE International Symposium on Information Theory, Istanbul, 2013. 1819--1823. Google Scholar

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

[99] Wang A, Zhang Z. An integer programming-based bound for locally repairable codes. IEEE Trans Inf Theory, 2015, 61: 5280-5294 CrossRef Google Scholar

[100] Zhang J, Wang X, Ge G N. Some improvements on locally repairable codes. 2015,. arXiv Google Scholar

[101] Mehrabi M, Ardakani M. On minimum distance of locally repairable codes. In: Proceedings of the 15th Canadian Workshop on Information Theory, Quebec, 2017. Google Scholar

[102] Tamo I, Barg A. A family of optimal locally recoverable codes. IEEE Trans Inf Theory, 2014, 60: 4661-4676 CrossRef Google Scholar

[103] Ernvall T, Westerback T, Hollanti C. Constructions of optimal and almost optimal locally repairable codes. In: Proceedings of the 4th International Conference on Wireless Communications, Vehicular Technology, Information Theory and Aerospace Electronic Systems, Aalborg, 2014. Google Scholar

[104] Liu J, Mesnager S, Chen L. New constructions of optimal locally recoverable codes via good polynomials. IEEE Trans Inf Theory, 2018, 64: 889-899 CrossRef Google Scholar

[105] Kolosov O, Barg A, Tamo I, et al. Optimal LRC codes for all lenghts $n~\leq~q$. 2018,. arXiv Google Scholar

[106] 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

[107] Balaji S B, Kumar P V. On partial maximally-recoverable and maximally-recoverable codes. In: Proceedings of IEEE International Symposium on Information Theory, Hong Kong, 2015. 1881--1885. Google Scholar

[108] Cadambe V R, Mazumdar A. Bounds on the size of locally recoverable codes. IEEE Trans Inf Theory, 2015, 61: 5787-5794 CrossRef Google Scholar

[109] Huang P, Yaakobi E, Uchikawa H. Binary linear locally repairable codes. IEEE Trans Inf Theory, 2016, 62: 6268-6283 CrossRef Google Scholar

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

[111] Wei V K. Generalized Hamming weights for linear codes. IEEE Trans Inf Theory, 1991, 37: 1412-1418 CrossRef Google Scholar

[112] Wang A Y, Zhang Z F, Lin D D. Bounds and constructions for linear locally repairable codes over binary fields. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 2033--2037. Google Scholar

[113] Ma J X, Ge G N. Optimal binary linear locally repairable codes with disjoint repair groups. 2017,. arXiv Google Scholar

[114] Agarwal A, Barg A, Hu S. Combinatorial Alphabet-Dependent Bounds for Locally Recoverable Codes. IEEE Trans Inform Theor, 2018, 64: 3481-3492 CrossRef Google Scholar

[115] Tamo I, Barg A, Goparaju S, et al. Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes. 2016,. arXiv Google Scholar

[116] Goparaju S, Calderbank R. Binary cyclic codes that are locally repairable. In: Proceedings of IEEE International Symposium on Information Theory, Honolulu, 2014. 676--680. Google Scholar

[117] Zeh A, Yaakobi E. Optimal linear and cyclic locally repairable codes over small fields. In: Proceedings of IEEE Information Theory Workshop, Jerusalem, 2015. Google Scholar

[118] Tamo I, Barg A, Frolov A. Bounds on the parameters of locally recoverable codes. IEEE Trans Inf Theory, 2016, 62: 3070-3083 CrossRef Google Scholar

[119] Barg A, Tamo I, Vladut S. Locally recoverable codes on algebraic curves. IEEE Trans Inf Theory, 2017, 63: 4928-4939 CrossRef Google Scholar

[120] Li X D, Ma L M, Xing C P. Construction of asymptotically good locally repairable codes via automorphism groups of function fields. 2017,. arXiv Google Scholar

[121] Nam M Y, Song H Y. Binary locally repairable codes with minimum distance at least six based on partial $t$-spreads. IEEE Commun Lett, 2017, 21: 1683-1686 CrossRef Google Scholar

[122] Silberstein N, Zeh A. Optimal binary locally repairable codes via anticodes. In: Proceedings of IEEE International Symposium on Information Theory, Hong Kong, 2015. 1247--1251. Google Scholar

[123] Hao J, Xia S T, Chen B. Some results on optimal locally repairable codes. In: Proceedings of IEEE International Symposium on Information Theory, Barcelona, 2016. 440--444. Google Scholar

[124] Shahabinejad M, Khabbazian M, Ardakani M. A class of binary locally repairable codes. IEEE Trans Commun, 2016, 64: 3182-3193 CrossRef Google Scholar

[125] Hao J, Xia S T, Chen B. On optimal ternary locally repairable codes. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 171--175. Google Scholar

[126] Hao J, Xia S. Bounds and constructions of locally repairable codes: parity-check matrix approach. 2016,. arXiv Google Scholar

[127] Li X D, Ma L M, Xing C P. Optimal locally repairable codes via elliptic curves. 2017,. arXiv Google Scholar

[128] Kim C, No J S. New constructions of binary and ternary locally repairable codes using cyclic codes. IEEE Commun Lett, 2018, 22: 228-231 CrossRef Google Scholar

[129] Luo Y, Xing C P, Yuan C. Optimal locally repairable codes of distance 3 and 4 via cyclic codes. 2018,. arXiv Google Scholar

[130] Krishnan M N, Puranik B, Kumar P V. Exploiting Locality for Improved Decoding of Binary Cyclic Codes. IEEE Trans Commun, 2018, 66: 2346-2358 CrossRef Google Scholar

[131] Vardy A, Be'ery Y. Maximum-likelihood soft decision decoding of BCH codes. IEEE Trans Inf Theory, 1994, 40: 546-554 CrossRef Google Scholar

[132] Huang P, Yaakobi E, Uchikawa H, et al. Cyclic linear binary locally repairable codes. In: Proceedings of IEEE Information Theory Workshop, Jerusalem, 2015. Google Scholar

[133] Chen M H, Huang C, Li J. On the maximally recoverable property for multi-protection group codes. In: Proceedings of IEEE International Symposium on Information Theory, Nice, 2007. 486--490. Google Scholar

[134] Blaum M, Hafner J L, Hetzler S. Partial-MDS codes and their application to RAID type of architectures. IEEE Trans Inf Theory, 2013, 59: 4510-4519 CrossRef Google Scholar

[135] Calis G, Koyluoglu O O. A general construction for PMDS codes. IEEE Commun Lett, 2017, 21: 452-455 CrossRef Google Scholar

[136] Gabrys R, Yaakobi E, Blaum M, et al. Constructions of partial MDS codes over small fields. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. Google Scholar

[137] Gopalan P, Huang C, Jenkins B. Explicit maximally recoverable codes with locality. IEEE Trans Inf Theory, 2014, 60: 5245-5256 CrossRef Google Scholar

[138] Hu G, Yekhanin S. New constructions of SD and MR codes over small finite fields. In: Proceedings of IEEE International Symposium on Information Theory, Barcelona, 2016. 1591--1595. Google Scholar

[139] Chen J Y, Shum K W, Yu Q, et al. Sector-disk codes and partial MDS codes with up to three global parities. In: Proceedings of IEEE International Symposium on Information Theory, Hong Kong, 2015. 1876--1880. Google Scholar

[140] Blaum M. Construction of PMDS and SD codes extending RAID 5. 2013,. arXiv Google Scholar

[141] Blaum M, Plank J S, Schwartz M. Construction of partial MDS and sector-disk codes with two global parity symbols. IEEE Trans Inf Theory, 2016, 62: 2673-2681 CrossRef Google Scholar

[142] Lalitha V, Lokam S V. Weight enumerators and higher support weights of maximally recoverable codes. In: Proceedings of the 53rd Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2015. 835--842. Google Scholar

[143] Kadhe S, Calderbank R. Rate optimal binary linear locally repairable codes with small availability. 2017,. arXiv Google Scholar

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

[145] Wang A Y, Zhang Z F. Repair locality with multiple erasure tolerance. IEEE Trans Inf Theory, 2014, 60: 6979-6987 CrossRef Google Scholar

[146] Song W T, Yuen C. Locally repairable codes with functional repair and multiple erasure tolerance. 2015,. arXiv Google Scholar

[147] Balaji S B, Kini G R, Kumar P V. A tight rate bound and a matching construction for locally recoverable codes with sequential recovery from any number of multiple erasures. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 1778--1782. Google Scholar

[148] Balaji S B, Kini G R, Kumar P V. A bound on rate of codes with locality with sequential recovery from multiple erasures. 2016,. arXiv Google Scholar

[149] Song W, Cai K, Yuen C. On Sequential Locally Repairable Codes. IEEE Trans Inform Theor, 2018, 64: 3513-3527 CrossRef Google Scholar

[150] Balaji S B, Kini G R, Kumar P V. A rate-optimal construction of codes with sequential recovery with low block length. In: Proceedings of National Conference on Communications, Hyderabad, 2018. Google Scholar

[151] Rawat A S, Mazumdar A, Vishwanath S. Cooperative local repair in distributed storage. 2014,. arXiv Google Scholar

[152] Exoo G, Jajcay R. Dynamic cage survey. The Electronic Journal Combinatorics, 2013. http://pdfs.semanticscholar.org/43b8/2016a2ef8f394f2cb1954439248198d2c274.pdf. Google Scholar

[153] Song W, Dau S H, Yuen C. Optimal locally repairable linear codes. IEEE J Sel Areas Commun, 2014, 32: 1019-1036 CrossRef Google Scholar

[154] Chen B, Xia S T, Hao J. Constructions of optimal cyclic $({r},{\delta~})$ locally repairable codes. IEEE Trans Inf Theory, 2018, 64: 2499-2511 CrossRef Google Scholar

[155] Hao J, Xia S T, Chen B. On the linear codes with $(r,~\delta)$-locality for distributed storage. In: Proceedings of IEEE International Conference on Communications, Paris, 2017. Google Scholar

[156] Sasidharan B, Agarwal G K, Kumar P V. Codes with hierarchical locality. In: Proceedings of International Symposium on Information Theory (ISIT), Hong Kong, 2015. 1257--1261. Google Scholar

[157] Ballentine S, Barg A. Codes on curves with hierarchical locality. In: Proceedings of IEEE International Symposium on Information Theory (accepted), Hong Kong, 2018. Google Scholar

[158] Duminuco A, Biersack E. Hierarchical codes: how to make erasure codes attractive for peer-to-peer storage systems. In: Proceedings of the 8th International Conference on Peer-to-Peer Computing, Aachen, 2008. 89--98. Google Scholar

[159] Kamath G M, Prakash N, Lalitha V. Codes with local regeneration and erasure correction. IEEE Trans Inf Theory, 2014, 60: 4637-4660 CrossRef Google Scholar

[160] Gligoroski D, Kralevska K, Jensen R E, et al. Repair duality with locally repairable and locally regenerating codes. 2017,. arXiv Google Scholar

[161] Hollmann H D L. On the minimum storage overhead of distributed storage codes with a given repair locality. In: Proceedings of IEEE International Symposium on Information Theory, Honolulu, 2014. 1041--1045. Google Scholar

[162] Ahmad I, Wang C C. When locally repairable codes meet regenerating codes — what if some helpers are unavailable. In: Proceedings of IEEE International Symposium on Information Theory, Hong Kong, 2015. 849--853. Google Scholar

[163] Krishnan M N, Anantha N R, Kumar P V. Codes with combined locality and regeneration having optimal Rate, $d_{\text{min}}$ and linear field size. 2018,. arXiv Google Scholar

[164] Shanmugam K, Papailiopoulos D S, Dimakis A G. A repair framework for scalar MDS codes. IEEE J Sel Areas Commun, 2014, 32: 998-1007 CrossRef Google Scholar

[165] Guruswami V, Wootters M. Repairing Reed-Solomon codes. IEEE Trans Inf Theory, 2017, 63: 5684-5698 CrossRef Google Scholar

[166] MacWilliams F J, Sloane N J A. The theory of error-correcting codes. Elsevier, 1977, 68: 185--186. Google Scholar

[167] Dau H, Milenkovic O. Optimal repair schemes for some families of full-length Reed-Solomon codes. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 346--350. Google Scholar

[168] Ye M, Barg A. Explicit constructions of MDS array codes and RS codes with optimal repair bandwidth. In: Proceedings of IEEE International Symposium on Information Theory, Barcelona, 2016. 1202--1206. Google Scholar

[169] Chowdhury A, Vardy A. Improved schemes for asymptotically optimal repair of MDS codes. In: Proceedings of the 55th Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2017. 950--957. Google Scholar

[170] Tamo I, Ye M, Barg A. Optimal repair of reed-solomon codes: achieving the cut-set bound. In: Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, Berkeley, 2017. 216--227. Google Scholar

[171] Dau S H, Duursma I M, Kiah H M, et al. Repairing Reed-Solomon codes with multiple erasures. 2016,. arXiv Google Scholar

[172] Bartan B, Wootters M. Repairing multiple failures for scalar MDS codes. In: Proceedings of the 55th Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2017. 1145--1152. Google Scholar

[173] Ye M, Barg A. Repairing Reed-Solomon codes: universally achieving the cut-set bound for any number of erasures. 2017,. arXiv Google Scholar

[174] Luby M. Capacity bounds for distributed storage. 2016,. arXiv Google Scholar

[175] Luby M, Padovani R, Richardson T J, et al. Liquid cloud storage. 2017,. arXiv Google Scholar

[176] Huang C, Simitci H, Xu Y, et al. Erasure coding in windows azure storage. In: Proceedings of USENIX Annual Technical Conference, Boston, 2012. 15--26. Google Scholar

[177] Gantenbein D. A better way to store data. Microsoft research blog. https://www.microsoft.com/en-us/research/blog/better-way-store-data/. Google Scholar

[179] Rashmi K V, Shah N B, Gu D, et al. A “hitchhiker's" guide to fast and efficient data reconstruction in erasure-coded data centers. In: Proceedings of ACM SIGCOMM Conference, Chicago, 2014. 331--342. Google Scholar

[180] Kralevska K, Gligoroski D, Jensen R E. HashTag Erasure Codes: From Theory to Practice. IEEE Trans Big Data, 2017, : 1-1 CrossRef Google Scholar

[181] Krishnan M N, Prakash N, Lalitha V, et al. Evaluation of codes with inherent double replication for Hadoop. In: Proceedings of the 6th USENIX Workshop on Hot Topics in Storage and File Systems, Philadelphia, 2014. Google Scholar

[182] Rashmi K V, Nakkiran P, Wang J, et al. Having your cake and eating it too: jointly optimal erasure codes for I/O, storage, and network-bandwidth. In: Proceedings of the 13th USENIX Conference on File and Storage Technologies, Santa Clara, 2015. 81--94. Google Scholar

[183] Li J, Li B. Beehive: erasure codes for fixing multiple failures in distributed storage systems. IEEE Trans Parallel Distrib Syst, 2017, 28: 1257-1270 CrossRef Google Scholar

[184] Pamies-Juarez L, Blagojevic F, Mateescu R, et al. Opening the chrysalis: on the real repair performance of MSR codes. In: Proceedings of the 14th USENIX Conference on File and Storage Technologies, Santa Clara, 2016. 81--94. Google Scholar

[185] Gad E E, Mateescu R, Blagojevic F, et al. Repair-optimal MDS array codes over GF(2). In: Proceedings of IEEE International Symposium on Information Theory, Istanbul, 2013. 887--891. Google Scholar

[186] Vajha M, Ramkumar V, Puranik B, et al. Clay codes: moulding MDS codes to yield an MSR code. In: Proceedings of the 16th USENIX Conference on File and Storage Technologies, Oakland, 2018. 139--154. Google Scholar

• Figure 1

(Color online) An overview of the different classes of codes for distributed storage discussed in this survey article.

• Figure 2

(Color online) An illustration of the data collection and node repair properties of an RG code.

• Figure 3

(Color online) The graph behind the cut-set file size bound.

• Figure 4

(Color online) Storage-repair bandwidth tradeoff. Here, $n~=~60$, $k~=~51$, $d=58$, $B~=~33660$.

• Figure 5

(Color online) An example RBT MBR code for the parameters $n=5$, $k=3$, $d=4$. Here file size is $9$.

• Figure 6

(Color online) Uncoupled data cube for $s=2$, $t=3$. The red dots represent plane-index $\uz$.

• Figure 7

(Color online) Paired symbols are shown using yellow rectangles connected by dotted lines. Uncoupled symbols are transformed using PFT to get the coupled symbols in the coupled data cube.

• Figure 8

(Color online) The repair matrix.

• Figure 9

(Color online) The (4,3,3) normalized tradeoff.

• Figure 10

(Color online) An $(n=5$, $k=4$, $d=4)$ canonical layered code.

• Figure 11

(Color online) Here two codewords of a [4,2] MDS code are piggybacked. The first systematic node can be repaired by reading $~b_2$, $b_1+b_2$ and $b_1+2b_2+a_1$, whereas the second systematic node repair requires $b_1$, $b_1+b_2$ and $2a_2-2b_2-b_1$.

• Figure 12

(Color online) Each of the seven lines in the Fano plane indicates a node and points within a line denote the code symbols stored in the corresponding node. For instance, $N_1=\{c_1,c_2,c_3\}$.

• Figure 13

(Color online) In the T-B construction, code symbols in the local codes of length $(r+1)$ correspond to the evaluations of polynomials of degree $\leq~(r-1)$. Here, $r=2$ implying evaluation at $3$ points of a linear polynomial.

• Figure 14

Zeros of the generator polynomial $g(x)=\frac{g_1(x)g_2(x)}{(x+1)}$ of the cyclic code in Example eg:zero_trainare identified by circles. The unshaded circles along with the shaded circle corresponding to $\alpha^0=1$ indicate the zeros $\{1,\alpha,\alpha^2,\alpha^4,\alpha^8\}$ of $g_1(x)$ selected to impart the code with $d_{\min}\geq~4$. The shaded circles indicate the periodic train of zeros $\{1,\alpha^5,\alpha^{10}\}$ introduced to cause the code to be locally recoverable with parameter $(r+1)=5$. The common element $1$ is helpful both to impart increased minimum distance as well as locality.

• Figure 15

The various code classes corresponding to different approaches to recovery from multiple erasures.

• Figure 16

The general form [147,148]of the parity-check matrix $H$ of a rate-optimal S-LR code for $t=8$.

• Figure 17

(Color online) Comparison of rate bounds on codes with sequential recovery eq:seq_rate_boundand codes with availability TamoBargRatefor $t=10$.

• Figure 18

(Color online) Illustration of a code with hierarchical locality. Each code symbol is protected by a $[4,3,2]$ local code. Each local code is contained in a $[12,8,3]$ middle code.

• Figure 19

(Color online) An $[[n=15,K=20,d_{\text{min}}=5,\alpha=4]]$ LRG code $\mathcal{C}$ where local codes are MBR codes. Here the local codes are $((n_\ell=5,r=3,d=4),(\alpha=4,\beta=1),K_\ell=9)$ MBR codes.

Citations

• #### 0

Altmetric

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