An Exploration of Optimization Algorithms and Heuristics for the Creation of Encoding and Decoding Schedules in Erasure Coding
Abstract
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.
How to Cite:
Schuman, C., (2011) “An Exploration of Optimization Algorithms and Heuristics for the Creation of Encoding and Decoding Schedules in Erasure Coding”, Pursuit - The Journal of Undergraduate Research at the University of Tennessee 2(1). doi: https://doi.org/10.7290/pur2ycgb
Downloads
Download PDF