Double Erasures Correcting MDS Code with Heterogeneous Placement

Abstract:

One array code scheme is proposed for double erasures correcting. The scheme made use of horizontal and oblique data placements to accommodate parity strips. The scheme can reduce the occurrences of bottlenecks in part due to the oblique placement. The encoding and decoding algorithms can be used in distributed storage. It has been proved that the code with the encoding scheme is MDS. It has also been indicated that the decoding scheme is effective for array code (p-1)×(p+1) when p is and only is a prime number. Moreover, two placements stripes are not associated with each other, which made it much easier for decoding to tolerate double erasures.

• Periodical: Applied Mechanics and Materials (Volume 607)
• Pages: 901-905
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.607.901
• Online since: July 2014
• Authors: Xun Luo*, Huan Shen
• Keywords: Array Code, Double Erasures Correcting, MDS Code, Parity Strip

References

[1] D.A. Patterson, G.A. Gibson, R.H. Katz, A Case for Redundant Arrays of Inexpensive Disks (RAID), In Proceedings of ACM SIGMOD Conference, Chicago, 1988, pp.109-116.

DOI: 10.1145/971701.50214

[2] Feng Keqin, Algebraic Theory of Error-Correcting Codes, Tsinghua University Press., Beijing, (2005).

[3] R.J. McEliece, The Theory of Information and Coding (Second Edition), Publishing House of Electronics Industry, Beijing, 2006, pp.109-116.

[4] M. Blaum, J. Brady, J. Bruck, et al, EVENODD: An Efficient Scheme for Tolerating Double Disk Failures in RAID Architectures, IEEE Transactions on Computer, 1995, v45, n2, pp.192-202.

DOI: 10.1109/12.364531

[5] L. Xu, J. Bruck, X-Code: MDS array codes with optimal encoding, IEEE Transactions on Information Theory, 1999, v45, n1, pp.272-276.

DOI: 10.1109/18.746809

[6] M. Blaum, A Family of MDS Codes with Minimal Number of Encoding Operations, In IEEE International Symposium on Information Theory, Seattle, 2006, pp.2784-2788.

DOI: 10.1109/isit.2006.261569

[7] J.L. Hafner, WEAVER Codes: Highly fault tolerant erasure codes for storage systems, IBM Research Division, San Jose, (2005).

[8] J.L. Hafner, HoVer Erasure Codes for Disk Arrays, In Proceedings of International Conference on Dependable Systems and Networks, Philadelphia, 2006, pp.217-216.

DOI: 10.1109/dsn.2006.40

[9] Chih-Shing Tau, Tzone-I Wang, Efficient parity placement schemes for tolerating triple disk failures in RAID architectures", In 17th International Conference on Advanced Information Networking and Applications, Xi, an, 2003, pp.27-29.

DOI: 10.1109/aina.2003.1192855

[10] Wan Wunan, Research on Erasure Codes for Distributed Secure Storage System, Chengdu Institute of Computer Applications, Chinese Academy of Sciences, Chengdu, (2006).