Paper Info
Title
Computing the Probability for Data Loss in Two-Dimensional Parity RAIDs
Abstract
Parity RAIDs are used to protect storage systems against disk failures. The idea is to add redundancy to the system by storing the parity of subsets of disks on extra parity disks. A simple two-dimensional scheme is the one in which the data disks are arranged in a rectangular grid, and every row and column is extended by one disk which stores the parity of it.In this paper we describe several two-dimensional parity RAIDs and analyse, for each of them, the probability for dataloss given that f random disks fail. This probability can be used to determine the overall probability using the model of Hafner and Rao. We reduce subsets of the forest counting problem to the different cases and show that the generalised problem is #P-hard. Further we adapt an exact algorithm by Stones for some of the problems whose worst-case runtime is exponential, but which is very efficient for small fixed f and thus sufficient for all real-world applications.
Year
DOI
Venue
2017
10.1109/EDCC.2017.14
2017 13th European Dependable Computing Conference (EDCC)
Keywords
Field
DocType
RAID,complexity,data loss,graph,Tutte polynomial,counting problem
Discrete mathematics,Data loss,Exact algorithm,Tutte polynomial,Computer science,Counting problem,Redundancy (engineering),RAID,Parity (mathematics),Grid,Distributed computing
Conference
ISBN
Citations 
PageRank 
978-1-5386-0603-2
0
0.34
References 
Authors
13
2
Name
Order
Citations
PageRank
Lars Nagel17613.58
Tim Süß25010.80