Zigzag Codes: MDS Array Codes With Optimal Rebuilding

By Itzhak Tamo, Zhiying Wang, Jehoshua Bruck. IEEE Transactions on Information Theory, 2011

382 citations recorded by the source corpus.

Maximum distance separable (MDS) array codes are widely used in storage systems to protect data against erasures. We address the rebuilding ratio problem, namely, in the case of erasures, what is the fraction of the remaining information that needs to be accessed in order to rebuild exactly the lost information? It is clear that when the number of erasures equals the maximum number of erasures that an MDS code can correct, then the rebuilding ratio is 1 (access all the remaining information). However, the interesting and more practical case is when the number of erasures is smaller than the erasure correcting capability of the code. For example, consider an MDS code that can correct two erasures: What is the smallest amount of information that one needs to access in order to correct a single erasure? Previous work showed that the rebuilding ratio is bounded between [1/2] and [3/4]; however, the exact value was left as an open problem. In this paper, we solve this open problem and prove that for the case of a single erasure with a two-erasure correcting code, the rebuilding ratio is [1/2]. In general, we construct a new family of r-erasure correcting MDS array codes that has optimal rebuilding ratio of [1/(r)] in the case of a single erasure. Our array codes have efficient encoding and decoding algorithms (for the cases r=2 and r=3, they use a finite field of size 3 and 4, respectively) and an optimal update property.

Subfields: Computer Networks and Communications, Information Systems

View Paper: https://www.semanticscholar.org/paper/3309031ad55d82bafaa337ac52cacf9a40beea1e

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Information Systems

Citations in the corpus

On the Delay-Storage Trade-Off in Content Download from Coded Distributed Storage Systems (2013, background): “A related line of work is concerned with another potential weakness of coding in distributed storage.”
Centralized Repair of Multiple Node Failures With Applications to Communication Efficient Secret Sharing (2016, methodology): “Zigzag Code): Let’s consider a zigzag code with the parameters n = 6, k = 3 and α = 9 from [3].”
A Family of Optimal Locally Recoverable Codes (2013, background): “…metrics: i) the number of bits communicated in the network, i.e., the repair-bandwidth [6], [22], [25], [27], [5], [18], ii), the number of bits read, the disk-I/O [13], [27], and iii), repair locality, i.e., the number of nodes that participate in the repair process [9], [16], [19], [26], [24].”
Locally Repairable Codes (2012, neutral): “.”
Locality and Availability in Distributed Storage (2014, background): “[3] on codes with optimal rebuilding ratio.”
Batch codes through dense graphs without short cycles (2014, methodology): “e multiset batch code is jV 1j=(jV 1j+ jV 2j) 1 1=q= 1 1= p k. Applying the gadget lemma as in the previous subsection gives the statement of the theorem. 4.4 Constructions based on zig-zag codes of [39] In this subsection, we describe a construction for primitive mutliset batch codes that allow for”
Communication Efficient Secret Sharing (2015, background): “Besides its application in distributed storage of secret data, secret sharing became a fundamental cryptographic primitive and is used as a building block in numerous secure protocols [1].”