Extremally fault tolerant arrays

The author characterizes the repairability of arrays without regard to how their faults are distributed. Worst-case, or extremal fault tolerance, is used as a basic metric for any redundant system. Two schemes are examined: a traditional dedicated spares model in which spare rows and columns cover rows and columns with faults, and a homogeneous model in which every row and column is a spare. In both cases deciding the existence of a fault cover is NP-complete, thus providing impetus for the extremal (i.e. worst-case) approach. With dedicated spares the extremal fault tolerance is just the number of spares; within this number of faults, a cover is constructed in time proportional to the dimensions of the array. Finding the homogeneous extremal fault tolerance is equivalent to the problem in which the number of spares does not exceed the dimension of the desired usable array. Within this number of faults, a repair is found in time proportional to the size of the array