R5X0: An Efficient High Distance Parity-Based Code with Optimal Update Complexity

We present a new class of array codes based on a generalization of the RAID5 XOR parity code. The R5X0(n, r, p) code protects an array of n data disks and p parity disks with r symbols per column from as many as p arbitrary column erasures. Decoding and encoding in R5X0 is computed using only XOR and cyclic shift operations. R5X0 is a simple geometric generalization of RAID5 and has optimal update complexity (the number of parity symbols affected by a single data symbol is exactly p) and asymptotically optimal storage effciency for its distance. The only geometric constraint on the R5X0 layout is that r (p - 1) · n.

By: Jeff R. Hartline, Tapas Kanungo, James Lee Hafner

Published in: RJ10322 in 2004


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to reports@us.ibm.com .