Title

A Graph Theoretic Algorithm For Placing Data And Parity To Tolerate Two Disk Failures In Disk Array Systems

Abstract

In recent years commercial Redundant Arrays of Inexpensive Disks (RAID) systems have become increasingly popular because of their enhanced I/O bandwidths, large capacities and low cost. However, the continued demand for larger capacities at low cost, has led to the use of larger arrays with increased probability of random disk failures. Hence the need for RAID systems to tolerate two or more random disk failures without sacrificing performance or storage space. In this paper, we devise a novel graph-theoretic method for placing data and parity in an array of N disks (N ≥ 3) to enable its recovery from any two random disk failures. We first provide an algorithm for the case when the number of disks N= P - 1, where P is a prime number, and then generalize the solution for any arbitrary N. We also determine the fraction of space used for storing parity in an array of W disks employing our algorithm, and show that this fraction has the optimal value of 2/N for all N = P - 1. For illustration, this fraction and the percentage of its difference from the optimal ratio are graphed for values of N between 5 and 255. Finally, we describe a method for determining the data-blocks from where the reconstruction of two failed disks can be started in such an array. © 2005 IEEE.

Publication Date

12-1-2005

Publication Title

Proceedings of the International Conference on Information Visualisation

Volume

2005

Number of Pages

542-549

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/IV.2005.8

Socpus ID

33749068855 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/33749068855

This document is currently not available here.

Share

COinS