On Optimizing XOR-Based Codes for Fault-Tolerant Storage Applications

For fault-tolerant storage applications, computation complexity is the key concern in choosing XOR-based codes. We observe that there is great benefit in computing common operations first (COF). Based on the COF rule, we describe a generic problem of optimizing XOR-based codes and make a conjecture about its NP-completeness. Two effective greedy algorithms are proposed. Against long odds, we show that XOR-based Reed-Solomon codes with such optimization can in fact be as efficient and sometimes even more efficient than the best known specifically designed XOR-based codes.