Advanced search
Start date
Betweenand
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Reliability of Erasure Coded Storage Systems: A Combinatorial-Geometric Approach

Full text
Author(s):
Vaishampayan, Vinay A. [1] ; Campello, Antonio [2, 3]
Total Authors: 2
Affiliation:
[1] AT&T Shannon Lab, Florham Pk, NJ 07932 - USA
[2] Telecom Paris Tech, F-75013 Paris - France
[3] Univ Estadual Campinas, BR-13083970 Campinas - Brazil
Total Affiliations: 3
Document type: Journal article
Source: IEEE TRANSACTIONS ON INFORMATION THEORY; v. 61, n. 11, p. 5795-5809, NOV 2015.
Web of Science Citations: 0
Abstract

We consider the probability of data loss, or equivalently, the reliability function for an erasure coded distributed data storage system under worst case conditions. Data loss in an erasure coded system depends on probability distributions for the disk repair duration and the disk failure duration. In previous works, the data loss probability of such systems has been studied under the assumption of exponentially distributed disk failure and disk repair durations, using well-known analytic methods from the theory of Markov processes. These methods lead to an estimate of the integral of the reliability function. Here, we address the problem of directly calculating the data loss probability for general repair and failure duration distributions. A closed limiting form is developed for the probability of data loss, and it is shown that the probability of the event that a repair duration exceeds a failure duration is sufficient for characterizing the data loss probability. For the case of constant repair duration, we develop an expression for the conditional data loss probability given the number of failures experienced by a each node in a given time window. We do so by developing a geometric approach that relies on the computation of volumes of a family of polytopes that are related to the code. An exact calculation is provided, and an upper bound on the data loss probability is obtained by posing the problem as a set avoidance problem. Theoretical calculations are compared with simulation results. (AU)

FAPESP's process: 13/25219-5 - Applications of Discrete Geometry and lattices to multiple user Information theory
Grantee:Antonio Carlos de Andrade Campello Junior
Support type: Scholarships in Brazil - Post-Doctorate
FAPESP's process: 14/20602-8 - Lattices and multiple user Information Theory
Grantee:Antonio Carlos de Andrade Campello Junior
Support type: Scholarships abroad - Research Internship - Post-doctor