Error Resilience in Distributed Storage via Rank-Metric Codes

Motivation

• Distributed storage uses coding rather than replication to reduce storage overhead while preserving resilience and enabling prompt single-node repair.Repair bandwidth is also important because downloading data consumes system bandwidth and energy.Source: §I · p. 1

Adversarial models

• Static errors replace an affected node's content once, whereas dynamic errors can change the pollution pattern on every collection or repair request.Dynamic errors are harder to manage because malicious behavior can repeatedly introduce corruption.Source: §I · p. 2

Coding scheme

• The proposed scheme applies an MRD outer code and a bandwidth-efficient MDS array inner code to quantify propagated corruption by rank while supporting node repair.The inner code also lets any k of n storage nodes recover the original data.Source: §I · p. 2

Resilience results

• For static errors, the scheme is optimal in the amount of data that can be reliably stored; for dynamic errors, it combines redundancy or subspace signatures with the concatenated construction.The signature-based solution bounds pollution rank, while the naïve solution is optimal for a specific parameter choice.Source: §I · p. 2

Locally repairable codes

• The paper also constructs MRD-based locally repairable scalar codes that tolerate adversarial errors and are optimal in minimum distance.This extends the contribution beyond bandwidth-efficient array-code repair.Source: §I · p. 2

A. System Model

• A distributed storage system stores a file across n nodes, reconstructs it from any k nodes, and repairs a failed node by downloading β symbols from d surviving nodes.The repair bandwidth is γ = βd, and MSR and MBR codes occupy extremal points of the storage-bandwidth trade-off.Source: A. System Model · p. 2

B. Rank-Metric Codes

• Rank-metric codes measure distance through matrix rank, and MRD codes attain the Singleton bound for rank metric.The paper uses rank metric because propagated errors can have large Hamming weight but controlled rank.Source: B. Rank-Metric Codes · p. 3

1) Gabidulin MRD Codes:

• Gabidulin codes are MRD codes constructed by evaluating linearized polynomials at points linearly independent over the base field.Their evaluation map is linear over Fq, which supports the rank-metric construction.Source: 1) Gabidulin MRD Codes · p. 3

2) Rank Errors and Rank Erasures Correction:

• Gabidulin MRD codes correct rank errors and rank erasures whenever 2t + s ≤ δ − 1.Here t is the rank of the unknown error component and s is the number of known rank erasures.Source: 2) Rank Errors and Rank Erasures… · p. 3

C. MDS Array Codes for Distributed Storage

• An MDS array code stores α-symbol blocks across n nodes so that the original data can be recovered from any k nodes.The MDS property is equivalent to every k × k block submatrix of the generator matrix having full rank.Source: C. MDS Array Codes for Distributed… · p. 3
• Optimal repair allows one failed node to be reconstructed by downloading αd/(d − k + 1) elements from each of d surviving nodes.The paper uses such MDS array codes as inner codes in its storage construction.Source: C. MDS Array Codes for Distributed… · p. 3, 1) Examples of Optimal Repair MDS… · p. 3

Zigzag code

• The (5,3) Zigzag code stores data across three systematic nodes with α = 4 and repairs a failed second node using symbols from shaded locations.Figure 1 contrasts repair in an error-free system with repair when the first storage node contains erroneous information.Source: 1) Examples of Optimal Repair MDS… · p. 4, Figure 1 · p. 4

Hadamard Design codes

• Hadamard Design codes use interference alignment so the newcomer can cancel contributions from other nodes before solving for the failed node.For second-node repair, data from nodes 4 and 5 is combined with repair matrices derived from nodes 1 and 3.Source: 1) Examples of Optimal Repair MDS… · p. 4

III. CODE CONSTRUCTION FOR STATIC ERROR MODEL

• The section presents the scheme as an error-tolerant construction for the static error model and establishes its optimality in that model.The construction is organized around the concatenation of the two code families and a proof of static-error resilience.Source: §III · p. 4

A. The Construction

• The construction encodes data with a Gabidulin MRD code and then partitions its output across an optimal-repair MDS array code.The MDS array code operates over Fq within the extension field used by the MRD code and supports bandwidth-efficient repair.Source: A. The Construction · p. 4
• For t erroneous nodes, the system recovers the original data from any k nodes whenever 2tα + 1 ≤ δ.This condition lets the MRD decoder correct the propagated error.Source: A. The Construction · p. 4
• The propagated error is represented through the MDS array code's block matrices, while its rank remains at most tα before MRD decoding.The construction therefore converts repair-induced corruption into a rank-metric error that the outer code can correct when δ ≥ 2tα + 1.Source: A. The Construction · pp. 4–5

B. Examples

• The examples use a single attacked storage node and illustrate that static corruption does not increase in rank through node-repair dynamics.The same concatenated construction can use any optimal-repair MDS array code as its inner code.Source: B. Examples · p. 5
• With the (5,3) Zigzag code, repairing a node after first-node corruption produces a transformed error, but the collected error has rank at most four.An MRD code with rank distance at least nine can then recover the original codeword and information.Source: B. Examples · p. 5
• With the (5,3) Hadamard design code, interference-alignment repair yields an error of rank at most α at the data collector.An MRD code with sufficient minimum rank distance recovers the uncorrupted information.Source: B. Examples · p. 5

C. Code Parameters

• The construction has efficient decoding based on one MDS array decoder and one Gabidulin decoder.This contrasts with the exponential-in-t decoding limitation reported for the construction in.Source: C. Code Parameters · p. 5
• The constructed codes attain bound (4), making the static-model construction optimal.The paper derives the matching parameter relation K = α(k − 2t) and concludes that the proposed scheme achieves the bound.Source: C. Code Parameters · p. 5
• The upper bound applies to the static model even though that model is less general than the model in, and the paper shows the bound is tight.The bound follows from an information-flow cut that remains valid under the static error model.Source: C. Code Parameters · p. 5
• The construction also corrects repair-data erasures when the corresponding MRD code has sufficiently large minimum distance, but its error model is restricted.It works with any MSR code, including high-rate codes, while providing a solution only for the restricted error model described.Source: C. Code Parameters · p. 6

IV. DYNAMIC ERROR MODEL

• Dynamic attacks can inject errors of arbitrarily large rank through repeated node repairs, unlike static attacks whose propagated rank is bounded by α.This unbounded accumulation can render stored data useless.Source: §IV · p. 6
• Prior approaches have limitations: lacks efficient reconstruction decoding and targets bandwidth-efficient repair at the MBR point, while handles the MSR point only in a low-rate regime.The paper distinguishes its dynamic-error focus from these settings.Source: §IV · p. 6
• The paper presents two solutions for dynamic errors: a direct repair-time correction approach and an approach based on subspace signatures.Both solutions target attacks in which a controlled node can send different data on different requests.Source: §IV · p. 6

A. Na¨ıve Scheme for Dynamic Error Model

• The naïve scheme reconstructs a failed node from downloaded symbols by treating unavailable MRD-codeword symbols as erasures and adversarial contributions as errors.At most tβ downloaded symbols can be erroneous, while the remaining kα − (k − 1)β − α symbols are treated as erased.Source: A. Na¨ıve Scheme for Dynamic Error Model · p. 6
• For k = 2t + 1, the naïve repair scheme is capacity-optimal under dynamic errors, but it becomes suboptimal as k − 2t − 1 increases.The gap between the naïve scheme’s bound and the applicable bound grows monotonically with k − 2t − 1.Source: A. Na¨ıve Scheme for Dynamic Error Model · p. 7

B. Subspace Signatures Approach

• Subspace signatures constrain each node’s repair data to its stored subspace, preventing dynamic attackers from injecting unbounded-rank pollution.The verifier tests repair and reconstruction data against stored signatures; failed nodes are treated as rank erasures.Source: B. Subspace Signatures Approach · p. 7
• Signature failures trigger naïve repair using k − s passing nodes, while s failed tests are handled as rank erasures and the remaining adversaries as rank errors.The trusted verifier initiates naïve repair for the failed node and nodes that do not pass the subspace test.Source: B. Subspace Signatures Approach · p. 7
• After signature-based repair, the aggregate error has rank at most tα, so an MRD code with sufficiently large minimum distance can recover the original data.The repaired node stores yi + yeBi, and the resulting system-wide error rank is bounded by tα.Source: B. Subspace Signatures Approach · p. 7

V. ERROR RESILIENCE FOR LOCALLY REPAIRABLE CODES

• The construction targets locally repairable scalar codes where α = β = 1 and each node can be repaired by accessing at most r < k other nodes.Such codes have small repair bandwidth but are not MDS because only designated repair groups are usable.Source: §V · p. 7
• Existing constructions attain the locality minimum-distance bound with systematic locality, but all-symbol constructions were known explicitly only for n = ⌈k/r⌉(r + 1).The paper introduces a new all-symbol construction that also corrects static errors.Source: §V · p. 8

A. Construction for Optimal Locally Repairable Codes

• Each Gabidulin MRD-codeword symbol is stored in a node, coordinates are partitioned into groups, and each group receives a parity equal to the sum of its symbols.The construction handles both m divisible by r and the case m ≡ k ≡ j (mod r), with an additional group of size j when needed.Source: A. Construction for Optimal Locally… · p. 8
• The example with m = N = 8, k = 6, δ = 3, and r = 4 adds two parity nodes, each summing four MRD-codeword symbols.The resulting codeword is [c1, …, c8, p1, p2], with p1 = c1 + c2 + c3 + c4 and p2 = c5 + c6 + c7 + c8.Source: A. Construction for Optimal Locally… · p. 8
• The constructed code Cloc attains the bound dmin = n − k + 2 − ⌈k/r⌉ for locally repairable scalar codes.The proof uses linearized-polynomial evaluations and shows that any required set of k independent evaluations remains available after the bounded erasures.Source: A. Construction for Optimal Locally… · p. 8
• The example code has minimum distance 4 and therefore tolerates any three erasures.The case analysis shows recovery when erasures are distributed across groups or concentrated within one group, because six independent evaluations remain.Source: A. Construction for Optimal Locally… · p. 8
• A single adversarial node can spread erroneous data across its entire repair group, but the resulting error can still have rank one and be corrected by an MRD code with δ ≥ 3.Thus, Hamming weight can grow to the group size while rank remains small.Source: A. Construction for Optimal Locally… · p. 8
• If the associated MRD code has minimum rank distance δ ≥ 2t + 1, the locally repairable construction tolerates at most t static errors.For t = 1, the example’s rank distance 3 corrects an error that Hamming distance alone cannot correct because the group size is 5.Source: A. Construction for Optimal Locally… · p. 8

• The concatenated scheme uses MRD codes first, followed by MDS optimal-repair array codes or locally repairable codes.The construction provides resilience against static adversarial errors.Source: §VI · p. 8
• With MDS optimal-repair array codes, the construction is optimal in resilience capacity.Source: §VI · p. 8
• With locally repairable codes, the construction is optimal in minimum distance.Source: §VI · p. 8
• A modification using subspace signatures provides resilience against dynamic errors.The paper identifies resilience against a passive eavesdropper as future work.Source: §VI · p. 9