Row-Diagonal Parity
Row-Diagonal Parity is an XOR array code that combines row and diagonal parity to recover any two known disk erasures.
For prime p greater than 2, the basic layout has p-1 data columns, one row-parity column and one diagonal-parity column, each with p-1 symbols. The row-parity column participates in the diagonals. Symbol (disk i, row r) belongs to diagonal (i+r) mod p; diagonal p-1 has no stored parity. Recovery alternates solvable diagonal and row equations. [1]
The p=5 example has four data disks and two parity disks, with four symbols each. Its independent binary-rank check covers all 15 failed-disk pairs. Excluding row parity from diagonal equations instead leaves only rank 15 for 16 data bits after losing data disk 1 and row-parity disk 4. Two parity columns alone do not guarantee two-disk recovery. [3]
The prime parameter is substantive: blindly applying the same layout at p=9 leaves rank 62 for 64 data bits when disks 0 and 3 disappear. This counterexample concerns that unchanged layout, not every code using composite parameters. All arithmetic checks use known erasures and consistent surviving symbols, not unidentified corruption. [3]
RDP and EVENODD are related but distinct constructions. An augmented-array formulation obtains RDP by constraining a column of an EVENODD array and removing the resulting zero parity column. That shortening relation does not make their parity formulas interchangeable. [2]
Relations
Citations
- Corbett et al. Row-Diagonal Parity for Double Disk Failure Correction. FAST 2004, sections 4-5.
- Hou, Han, Shum and Li. A Unified Form of EVENODD and RDP Codes and Their Efficient Decoding (2018), section II, Proposition 3.
- Hesela: independent RDP recovery, binary rank and invalid-construction controls.
Further reading
Sources & caveats
- The primary construction and the 2018 algebraic relationship were reviewed beyond their abstracts. The scope is the basic double-erasure construction, not a product implementation or generalized multi-parity code.
- Run node --test model.test.js beside model.js. Independent rank checks cover every failed-disk pair for p=3,5,7,11; p=3 also enumerates all binary messages. No external packages are required.
- The finite model checks recoverability. It does not measure repair bandwidth, CPU performance, physical read amplification, crash consistency or field failure rates.