Characterizing the Rate Region of the (4,3,3) Exact-Repair Regenerating Codes
arXiv:1312.0914 · doi:10.1109/JSAC.2014.140516
Abstract
Exact-repair regenerating codes are considered for the case (n,k,d)=(4,3,3), for which a complete characterization of the rate region is provided. This characterization answers in the affirmative the open question whether there exists a non-vanishing gap between the optimal bandwidth-storage tradeoff of the functional-repair regenerating codes (i.e., the cut-set bound) and that of the exact-repair regenerating codes. To obtain an explicit information theoretic converse, a computer-aided proof (CAP) approach based on primal and dual relation is developed. This CAP approach extends Yeung's linear programming (LP) method, which was previously only used on information theoretic problems with a few random variables due to the exponential growth of the number of variables in the corresponding LP problem. The symmetry in the exact-repair regenerating code problem allows an effective reduction of the number of variables, and together with several other problem-specific reductions, the LP problem is reduced to a manageable scale. For the achievability, only one non-trivial corner point of the rate region needs to be addressed in this case, for which an explicit binary code construction is given.
This is the extended version of the conference paper arXiv:1305.2440, with more details on the computed aided proof approach, as well a further simplified outer bound proof. Accepted for publication in IEEE JSAC on Communication Methodologies for the Next-Generation Storage Systems
References in corpus (3)
Cited by in corpus (29)
- Symmetry, Outer Bounds, and Code Constructions: A Computer-Aided Investigation on the Fundamental Limits of Caching
- Layered, Exact-Repair Regenerating Codes Via Embedded Error Correction and Block Designs
- Towards Optimal Secure Distributed Storage Systems with Exact Repair
- Outer bounds for exact repair codes
- Cascade Codes For Distributed Storage Systems
- Towards Practical Private Information Retrieval from MDS Array Codes
- Coded Caching with Heterogeneous Cache Sizes and Link Qualities: The Two-User Case
- Caching and Delivery via Interference Elimination
- Capacity-Achieving Private Information Retrieval Codes with Optimal Message Size and Upload Cost
- Multilinear Algebra for Distributed Storage
- Multilinear Algebra for Minimum Storage Regenerating Codes
- PMDS Array Codes With Small Sub-packetization, Small Repair Bandwidth/Rebuilding Access
- Explicit Polyhedral Bounds on Network Coding Rate Regions via Entropy Function Region: Algorithms, Symmetry, and Computation
- Multilevel Diversity Coding Systems: Rate Regions, Codes, Computation, & Forbidden Minors
- On Multi-source Networks: Enumeration, Rate Region Computation, and Hierarchy
- Erasure Coding for Distributed Storage: An Overview
- Constrained Linear Representability of Polymatroids and Algorithms for Computing Achievability Proofs in Network Coding
- On the Storage Cost of Private Information Retrieval
- New Results on the Storage-Retrieval Tradeoff in Private Information Retrieval Systems
- The Storage-Repair-Bandwidth Trade-off of Exact Repair Linear Regenerating Codes for the Case
- User Manual CAI version-1.0: An Open-Source Toolbox for Computer-Aided Investigation on the Fundamental Limits of Information Systems
- Multilevel Diversity Coding with Secure Regeneration: Separate Coding Achieves the MBR Point
- Multi-Version Coding - An Information Theoretic Perspective of Consistent Distributed Storage
- Cooperative Repair of Multiple Node Failures in Distributed Storage Systems
- On Secure Exact-repair Regenerating Codes with a Single Pareto Optimal Point
- New Results on Multilevel Diversity Coding with Secure Regeneration
- A Numerical Study on the Wiretap Network with a Simple Network Topology
- On the Tradeoff Region of Secure Exact-Repair Regenerating Codes
- Erasure Codes for Distributed Storage: Tight Bounds and Matching Constructions