×

Methods for placing data and parity to tolerate two disk failures in disk arrays using complete bipartite graphs. (English) Zbl 1111.68090

Summary: Redundant Arrays of Independent Disks (RAID) systems have come into widespread use because of their enhanced I/O bandwidths, large capacities, and low cost. However, the increasing demand for larger array capacities at low cost has led to the use of arrays with larger number of disks that increases the likelihood of the concurrent occurrence of two or more random disk failures. Hence the need for RAID systems to tolerate two or more random disk failures without compromising disk utilization. We present algorithms based on (a) the perfect 1-factorization of the complete bipartite graph, \(K_{P,P}\), for placing data and parity in arrays with \(P\) and \((P-1)\) disks, where \(P\) is a prime number, and (b) the perfect 1-factorization of \(K_{2P-1,2P-1}\) for placing data and parity in arrays with \(2P-2\) disks to enable their recovery from two random disk failures. In both cases the fraction of space used for storing parity in the disk array is optimal.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68W05 Nonnumerical algorithms

Software:

EVENODD
PDFBibTeX XMLCite