Characterizing the Rate Region of the (4,3,3) Exact-Repair Regenerating Codes

I. INTRODUCTION

• Erasure-coded storage can improve availability and durability over replication, but repair requires remaining nodes to transmit information to a replacement node.The repair bandwidth is identified as a key issue affecting system performance.Source: §I · p. 1
• Functional repair permits a replacement node to store different data, whereas exact repair requires it to reproduce the failed node’s stored data exactly.The functional-repair tradeoff is an outer bound for exact repair; prior work left unclear whether non-achievability implied an asymptotic-only effect or a persistent gap.Source: §I · p. 1
• The paper completely characterizes the previously incomplete rate region for (4,3,3) exact-repair codes and establishes a non-vanishing gap from the functional-repair tradeoff.The achievable region also includes codes better than time-sharing between the MSR and MBR points.Source: §I · pp. 1–2
• The converse uses a computer-aided proof approach that reduces the LP variables using symmetry and problem-specific structure, then uses a secondary optimization to obtain explicit information-theoretic proofs.The method extends Yeung’s LP framework; an ℓ1 objective approximates the sparsest ℓ0 solution, which roughly corresponds to fewer proof steps.Source: §I · p. 2

A. Exact-Repair Regenerating Codes

• The formal (4,3,3) code definition specifies encoding, reconstruction, and repair functions, with reconstruction from any three nodes and repair using three helpers.The paper also defines normalized achievable bandwidth-storage pairs to include tradeoffs approached asymptotically.Source: A. Exact-Repair Regenerating Codes · p. 2
• The code definition adopts zero-error reconstruction; the paper states that requiring asymptotically vanishing error would make no essential difference to its rate-region characterization.The achievable region is the collection of normalized storage-bandwidth pairs attainable under the stated definition.Source: A. Exact-Repair Regenerating Codes · p. 2

B. Some Further Notation

• The message is represented by a uniformly distributed random variable, alongside variables for stored data and repair information.These variables form the notation used to express the code constraints.Source: B. Some Further Notation · p. 3
• Reconstruction requires the stored data at a node to be determined by the repair information sent from the other nodes.The section states the corresponding entropy condition for each node.Source: B. Some Further Notation · p. 3
• The symmetric storage and repair-bandwidth constraints, together with reconstruction and repair conditions, are the constraints used in the converse proof.Source: B. Some Further Notation · p. 3

C. Review of Functional-Repair Outer Bound

• The functional-repair optimum provides an outer bound for the exact-repair case.The bound is attributed to Dimakis et al..Source: C. Review of Functional-Repair Outer… · p. 3
• The specialized functional-repair bound is expressed as four simultaneous linear inequalities: 3ᾱ ≥ 1, 2ᾱ + β̄ ≥ 1, ᾱ + 3β̄ ≥ 1, and 6β̄ ≥ 1.Source: C. Review of Functional-Repair Outer… · p. 3
• Figure 1 depicts the functional-repair outer bound together with the exact-repair rate region R.Source: Figure 1 · p. 3

III. THE RATE REGION OF (4, 3, 3) REGENERATING CODES

• The region is defined by 3ᾱ ≥ 1, 2ᾱ + β̄ ≥ 1, 4ᾱ + 6β̄ ≥ 3, and 6β̄ ≥ 1.Theorem 1 gives the complete characterization.Source: §III · p. 3
• The exact-repair region has a gap from the functional-repair outer bound, and the only difference is its third bounding plane.Thus the functional-repair outer bound is not asymptotically achievable under exact repair.Source: §III · p. 3

A. The Achievability Proof

• The MSR and MBR points are achievable, leaving only the (3/8, 1/4) point as the non-trivial corner to construct.A binary (4, 3, 3) code with α = 3, β = 2, and B = 8 achieves this point.Source: A. The Achievability Proof · p. 3
• Circular symmetry reduces repair verification to node 1 failing, when nodes 2, 3, and 4 each contribute two bits to reconstruct it.The new node forms combinations that recover x1 and x2 by differences, completing the construction.Source: A. The Achievability Proof · pp. 3–4

B. The Converse Proof

• For (4, 3, 3), the symmetric achievable region R* equals the full exact-repair region R.This permits the converse to consider only codes inducing symmetric entropy vectors.Source: B. The Converse Proof · p. 4
• Space-sharing across permutations establishes that the symmetric achievable region is included in the full region.The reverse inclusion is direct, yielding R = R*.Source: B. The Converse Proof · p. 4
• The converse derives the outer bound on symmetric entropy vectors using symmetry and entropy inequalities.The proof chain invokes symmetry and that the sum of individual entropies is at least the joint entropy.Source: B. The Converse Proof · pp. 4–5
• The same rate region holds when zero error is relaxed to asymptotic zero error probability as B approaches infinity.The proof replaces applications of the zero-error constraint with a version based on Fano’s inequality.Source: B. The Converse Proof · p. 5

IV. THE COMPUTER-AIDED PROOF APPROACH

• The converse uses unconventional steps, including adding and subtracting the same term, arising from complex symmetry and dependence among variables.The authors report that extensive manual attempts to find the proof were unsuccessful.Source: §IV · p. 5
• The authors obtained the converse through a computer-aided proof approach after unsuccessful manual attempts.Source: §IV · p. 5
• The paper presents its converse-finding approach as potentially useful for future research.Source: §IV · p. 5

A. The Basic Primal Linear Program

• The LP uses 65,535 joint-entropy variables for the non-empty subsets of 16 random variables, with information measures represented as their linear combinations.Source: A. The Basic Primal Linear Program · p. 5
• With B set to 1, the LP fixes α and minimizes β subject to the code constraints and general entropy inequalities.The passage describes sweeping α to obtain a lower bound on β for each fixed α.Source: A. The Basic Primal Linear Program · p. 6
• The basic LP has 1,966,112 inequality constraints and 21 equality constraints.The inequality total includes Shannon-type inequalities and problem constraints.Source: A. The Basic Primal Linear Program · p. 6
• The basic LP is too large for existing packages such as ITIP or XITIP, and a Cplex run did not solve it within 48 hours.Although the formulation omits non-Shannon inequalities, Shannon-type inequalities prove sufficient for this problem.Source: A. The Basic Primal Linear Program · p. 6

C. Dimension Reduction in the Primal Linear Program

• Symmetry permits equivalent entropy variables to be represented by one variable, reducing the LP’s dimension.For example, H(W1, S2,3) equals H(Wi, Sj,k) when i, j, and k are distinct.Source: B. Dimension Reduction in the Primal… · p. 6
• A set-growth procedure groups subsets with the same closure, whose entropies are equal, so each equivalence class needs only one LP variable.When a closure contains at least three W variables, its entropy equals B and can be eliminated; the equivalence classes also eliminate equality constraints (7)–(10).Source: B. Dimension Reduction in the Primal… · p. 6
• Without loss of optimality, constraints (12) and (13) can be set to equality, eliminating the variables for H(Wi) and H(Si,j) in favor of β.Source: B. Dimension Reduction in the Primal… · p. 6
• After variable reductions, degenerate and repeated inequalities are removed from the constraint set.Source: B. Dimension Reduction in the Primal… · p. 6
• The reductions leave 176 variables and 6,152 inequality constraints, solvable in under 0.1 second for each fixed α0 value.The reported solver is Cplex under the same setup as previously mentioned.Source: B. Dimension Reduction in the Primal… · p. 6

C. The Secondary LP

• The numerical primal LP leaves uncertainty about how densely to sample α and provides bounds only to numerical precision, motivating an explicit algebraic converse.The authors seek a bound tight under the primal constraints.Source: C. The Secondary LP · pp. 6–7
• Strong duality holds because the primal LP is feasible, so there is no duality gap and the dual solution can certify the bound.The primal has a trivial feasible solution with all joint entropies equal to B0.Source: C. The Secondary LP · p. 7
• A nonnegative combination of the LP’s information inequalities is itself valid; the target converse is 4α + 6β ≥ 3B.The target coefficients are encoded as [−3, 4, 6, 0, …, 0], under the stated tightness assumption.Source: C. The Secondary LP · p. 7
• The secondary LP uses an ℓ1 objective to seek a sparse dual-weight solution, while any solution satisfying the equalities still gives an exact converse.The ℓ1 objective approximates the NP-hard search for the sparsest solution; sparsity affects proof length, not validity.Source: C. The Secondary LP · p. 7
• The tabulated dual solution sums to 4α + 6β ≥ 3B, and manual combination of inequalities further simplifies the proof.Table IV lists the dual solution; Table V rewrites it in basic information inequalities.Source: C. The Secondary LP · p. 8, Table IV · p. 8, Table V · p. 8
• The approach generalizes Yeung’s LP framework with problem-specific constraints and introduces an ℓ1 objective to seek sparse information-inequality combinations.Strong duality establishes the tight LP bounds without relying on completeness of the elemental Shannon information inequalities.Source: C. The Secondary LP · p. 8

• For (4,3,3) exact-repair codes, the complete rate-region characterization shows the cut-set outer bound is not generally tight, even asymptotically.Source: §V · p. 8
• An explicit binary code construction establishes achievability of the characterized rate region.Source: §V · p. 8
• The computer-aided proof extends Yeung’s linear-programming framework to obtain an explicit information-theoretic converse.Source: §V · p. 8
• The secondary LP’s sparsity objective covers only elementary Shannon-type inequalities, and adding redundant basic inequalities may yield a sparser solution.Source: §V · p. 8
• The general-parameter rate-region problem remains open; the approach can tackle a few small cases, but its complexity is too high for larger parameters.Set growth and symmetry determination alone have exponential order in the total number of random variables.Source: §V · p. 8

• For any achievable (ᾱ, β̄) and ε > 0, the proposition considers an exact-repair code with parameters (N, Kd, K).Source: APPENDIX · p. 8
• The proof fixes ε and considers a code that may or may not induce a symmetric entropy vector.Source: APPENDIX · p. 8
• Using the 24 permutations of I4, the construction forms a code with parameters (N′, K′d, K′) = (N·24, K·24, K·24) that induces a symmetric distortion vector.Source: APPENDIX · p. 9
• The resulting encoding and decoding functions induce a symmetric entropy vector, and the original code’s zero-error decoding and repair requirements are satisfied.Source: APPENDIX · p. 9