Repair Locality With Multiple Erasure Tolerance

Abstract: In distributed storage systems, erasure codes with locality

r

is preferred because a coordinate can be recovered by accessing at most

r

other coordinates which in turn greatly reduces the disk I/O complexity for small

r

. However, the local repair may be ineffective when some of the

r

coordinates accessed for recovery are also erased. To overcome this problem, we propose the

(r, d e l t a)_{c}

-locality providing

d e l t a - 1

local repair options for a coordinate. Consequently, the repair locality

r

can tolerate

d e l t a - 1

erasures in total. We derive an upper bound on the minimum distance

d

for any linear

[n, k]

code with information

(r, d e l t a)_{c}

-locality. For general parameters, we prove existence of the codes that attain this bound when

n g e q k (r (d e l t a - 1) + 1)

, implying tightness of this bound. Although the locality

(r, d e l t a)

defined by Prakash et al provides the same level of locality and local repair tolerance as our definition, codes with

(r, d e l t a)_{c}

-locality are proved to have more advantage in the minimum distance. In particular, we construct a class of codes with all symbol

(r, d e l t a)_{c}

-locality where the gain in minimum distance is

O m e g a (s q r t r)

and the information rate is close to 1.

Cited in

(23)

This page was built for publication: Repair Locality With Multiple Erasure Tolerance