Low-Complexity Array Codes for Random and Clustered 4-Erasures
- Creators
-
Cassuto, Yuval
-
Bruck, Jehoshua
Abstract
A new family of low-complexity array codes is proposed for correcting 4 column erasures. The new codes are tailored for the new error model of clustered column erasures that captures the properties of high-order failure combinations in storage arrays. The model of clustered column erasures considers the number of erased columns, together with the number of clusters into which they fall, without pre-defining the sizes of the clusters. This model addresses the problem of correlated device failures in storage arrays, whereby each failure event may affect multiple devices in a single cluster. The new codes correct essentially all combinations of clustered 4 erasures, i.e., those combinations that fall into three or less clusters. The new codes are significantly more efficient, in all relevant complexity measures, than the best known 4-erasure correcting codes. These measures include encoding complexity, decoding complexity and update complexity.
Additional Information
© 2012 IEEE. Manuscript received February 10, 2010; revised May 04, 2011; accepted May 25, 2011. Date of current version January 06, 2012. This work was supported in part by the Caltech Lee Center for Advanced Networking. The authors wish to thank the anonymous reviewers for comments contributing to the clarity of presentation. Communicated by J.-P. Tillich, Associate Editor for Coding Theory. The authors wish to thank the anonymous reviewers for comments contributing to the clarity of presentation.Additional details
- Eprint ID
- 29137
- DOI
- 10.1109/TIT.2011.2171518
- Resolver ID
- CaltechAUTHORS:20120203-154015264
- Caltech Lee Center for Advanced Networking
- Created
-
2012-02-06Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 12443713