6533b852fe1ef96bd12ab670

RESEARCH PRODUCT

Computing the Probability for Data Loss in Two-Dimensional Parity RAIDs

Lars NagelTim Suess

subject

Discrete mathematicsHardware_MEMORYSTRUCTURESRAIDComputer science020206 networking & telecommunications02 engineering and technologyData lossGridElectronic mail020202 computer hardware & architecturelaw.inventionExact algorithmCounting problemlawData_FILES0202 electrical engineering electronic engineering information engineeringTutte polynomialParity (mathematics)

description

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.

yearjournalcountryeditionlanguage
2017-09-012017 13th European Dependable Computing Conference (EDCC)
https://doi.org/10.1109/edcc.2017.14