Drives fail. In a storage array with tens or hundreds of disks, the question is not whether a drive will fail, but when. Fault-tolerant codes are the system’s insurance policy, and EVENODD is an especially elegant example.
At the IHUB Research Program, I worked with Prof. Lara Dolecek to study parity computation, error correction, and fault tolerance in EVENODD codes. Using MATLAB simulations, I compared the complexity and efficiency of different parity-calculation approaches under multi-disk-failure scenarios.
The need for double-disk tolerance
RAID-5 can recover from a single disk failure with one parity block computed by XOR. Large arrays, however, need more protection: two concurrent disk failures are no longer negligible. Reed–Solomon codes can address this case, but finite-field multiplication adds computational overhead. EVENODD achieves double-disk fault tolerance using XOR alone.
The key idea
EVENODD adds two parity columns to a data array:
- Row parity uses XOR across rows, similar to RAID-5.
- Diagonal parity uses XOR along diagonals with a global adjuster.
These two independent sets of constraints make it possible to locate and recover any two lost columns.
// Row parity: P[i] = D[i,0] XOR D[i,1] XOR ... XOR D[i,m-1]
// Diagonal parity: Q[k] = S XOR (XOR of D[i,j] where (i + j) mod p == k)
// S is a global adjuster derived from diagonal sums.
//
// Two-column recovery combines row and diagonal constraints
// through diagonal back-substitution using XOR only.Core idea: use two orthogonal sets of XOR constraints—rows and diagonals—to replace finite-field multiplication with inexpensive XOR operations.
Where the cost moves
EVENODD saves multiplication, but the cost reappears elsewhere:
- Global dependency. The diagonal adjuster depends on the entire array.
- Chained recovery. Reconstructing two lost columns follows diagonal dependencies that are harder to parallelise.
- Parameter constraints. The construction imposes prime-related restrictions on array dimensions.
What I measured
I built simulations that compared parity-calculation schemes on the same scale, measuring system complexity and execution efficiency during multi-node and multi-disk recovery. The useful question is not only “Can we recover the data?” but also “How quickly, and at what cost?”
There is no universally best fault-tolerant code—only a design that is best suited to a particular failure model and hardware constraint.
This article accompanies the published preprint Advanced Parity Calculation Techniques in EVENODD Coding. DOI: 10.61173/ww1ryv48 ↗