Cyclic Structure in Regenerating Codes

Abstract:

Regenerating codes are a class of erasure codes for distributed storage. The use of regenerating codes not only improves reliability of distributed storage systems, but also minimizes repairing bandwidth when storage nodes failed and need to be repaired. In this paper, we investigate the cyclic structure of hybrid regenerating codes which each node has two fragments with the first fragment stores original message and the second fragment stores parity message. A fast repairing algorithm is also proposed.

• Periodical: Applied Mechanics and Materials (Volume 539)
• Pages: 416-419
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.539.416
• Online since: July 2014
• Authors: Wen Juan Liang*, Ying Du
• Keywords: Linear Exact-Repair Construction, MDS-Property, MSR Codes, Network Coding, Network Flow, Regenerating Codes

References

[1] Dimakis A G, Ramchandran K, Wu Y, et al. A survey on network codes for distributed storage[J]. Proceedings of the IEEE, 2011, 99(3): 476-489.

DOI: 10.1109/jproc.2010.2096170

[2] Gastón B, Pujol J, Villanueva M. Quasi-cyclic Minimum Bandwidth Regenerating Codes⋆[C]/III International Castle Meeting on Coding Theory and Applications. Univ. Autònoma de Barcelona, 2011, 5: 127.

[3] Gastón B, Pujol J, Villanueva M. Quasi-cyclic minimum storage regenerating codes for distributed data compression[C]/Data Compression Conference (DCC), 2011. IEEE, 2011: 33-42.

DOI: 10.1109/dcc.2011.11

[4] Dimakis A G, Godfrey P B, Wu Y, et al. Network coding for distributed storage systems[J]. Information Theory, IEEE Transactions on, 2010, 56(9): 4539-4551.

DOI: 10.1109/tit.2010.2054295

[5] Shah N B, Rashmi K V, Vijay Kumar P, et al. Distributed storage codes with repair-b- y-transfer and nonachievability of interior points on the storage-bandwidth tradeoff [J]. Information Theory, IEEE Transactions on, 2012, 58(3): 1837-1852.

DOI: 10.1109/tit.2011.2173792

[6] Oggier F, Datta A. Self-repairing homomorphic codes for distributed storage systems[C]/INFOCOM, 2011 Proceedings IEEE. IEEE, 2011: 1215-1223.

DOI: 10.1109/infcom.2011.5934901

[7] Shah N B, Rashmi K V, Vijay Kumar P. A flexible class of regenerating codes for distributed storage[C]/Information Theory Proceedings (ISIT), 2010 IEEE International Symposium on. IEEE, 2010: 1943-(1947).

DOI: 10.1109/isit.2010.5513353

[8] Shum K W. Cooperative regenerating codes for distributed storage systems[C]/Communications (ICC), 2011 IEEE International Conference on. IEEE, 2011: 1-5.

DOI: 10.1109/icc.2011.5962548

[9] Papailiopoulos D S, Dimakis A G, Cadambe V R. Repair optimal erasure codes through hadamard designs[C]/Communication, Control, and Computing (Allerton), 2011 49th Annual Allerton Conference on. IEEE, 2011: 1382-1389.

DOI: 10.1109/allerton.2011.6120328

[10] Shum K W, Hu Y. Cooperative regenerating codes[J]. arXiv preprint arXiv: 1207. 6762, (2012).

[11] Wu Y. A construction of systematic MDS codes with minimum repair bandwidth[J]. Information Theory, IEEE Transactions on, 2011, 57(6): 3738-3741.

DOI: 10.1109/tit.2011.2134170

[12] Shah N B, Rashmi K V, Kumar P V, et al. Interference alignment in regenerating codes for distributed storage: Necessity and code constructions [J]. Information Theory, IEEE Transactions on, 2012, 58(4): 2134-2158.

DOI: 10.1109/tit.2011.2178588

[13] 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[J]. Information Theory, IEEE Transactions on, 2011, 57(8): 5227-5239.

DOI: 10.1109/tit.2011.2159049

[14] Gastn B, Pujol J, Villanueva M. Quasi-cyclic regenerating codes[J]. arXiv preprint arXiv: 1209. 3977, (2012).

[15] R. Motwani and P. Raghavan, Randomized Algorithms. Cambridge U.K.: Cambridge Univ. Press, (1995).