Paper Info
Title
Determining Fault Tolerance of XOR-Based Erasure Codes Efficiently
Abstract
We propose a new fault tolerance metric for XOR-based erasure codes: the minimal erasures list (MEL). A minimal erasure is a set of erasures that leads to irrecoverable data loss and in which every erasure is necessary and sufficient for this to be so. The MEL is the enumeration of all minimal erasures. An XOR-based erasure code has an irregular structure that may permit it to tolerate faults at and beyond its Hamming distance. The MEL completely describes the fault tolerance of an XOR-based erasure code at and beyond its Hamming distance; it is therefore a useful metric for comparing the fault tolerance of such codes. We also propose an algorithm that efficiently determines the MEL of an erasure code. This algorithm uses the structure of the erasure code to efficiently determine the MEL. We show that, in practice, the number of minimal erasures for a given code is much less than the total number of sets of erasures that lead to data loss: in our empirical results for one corpus of codes, there were over 80 times fewer minimal erasures. We use the proposed algorithm to identify the most fault tolerant XOR-based erasure code for all possible systematic erasure codes with up to seven data symbols and up to seven parity symbols.
Year
DOI
Venue
2007
10.1109/DSN.2007.32
Edinburgh
Keywords
Field
DocType
fault tolerance,possible systematic erasure code,erasure code,xor-based erasure codes efficiently,hamming distance,data loss,minimal erasure,fault tolerant,minimal erasures list,times fewer minimal erasure,xor-based erasure code,redundancy,availability,decoding
Online codes,Computer science,Fountain code,Algorithm,Hamming distance,Fault tolerance,Decoding methods,Tornado code,Erasure code,Erasure
Conference
ISSN
ISBN
Citations 
1530-0889
0-7695-2855-4
20
PageRank 
References 
Authors
1.17
11
2
Name
Order
Citations
PageRank
Jay J. Wylie168544.29
Ram Swaminathan291365.42