An Exploration of Optimization Algorithms and Heuristics for the Creation of Encoding and Decoding Schedules in Erasure Coding
Catherine D. Schuman · Pursuit The Journal of Undergraduate Research at the University of Tennessee · 2011
Erasure codes are employed by disk systems to tolerate failures. They are typically characterized by bit-matrices that are used for encoding and decoding. The efficiency of an erasure code using a bit-matrix is directly related to the number of exclusive-or (XOR) operations required during the encoding process. Thus, a problem within the field of erasure coding is how to schedule the XOR operations for any given bit-matrix so that the fewest number of XOR operations are required. This paper develops an algorithm for finding the optimum solution and analyzes the performance of two known heuristics on a set of encoding matrices.