2009/12/31 by Changho Suh, Kannan Ramchandran, Suh, Changho +1 · 2 citations
Computer Science · #Advanced Data Storage Technologies #Caching and Content Delivery #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.1001.0107
openalex publication_date 2009/12/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The high repair cost of (n,k) Maximum Distance Separable (MDS) erasure codes\nhas recently motivated a new class of codes, called Regenerating Codes, that\noptimally trade off storage cost for repair bandwidth. On one end of this\nspectrum of Regenerating Codes are Minimum Storage Regenerating (MSR) codes\nthat can match the minimum storage cost of MDS codes while also significantly\nreducing repair bandwidth. In this paper, we describe Exact-MSR codes which\nallow for any failed nodes (whether they are systematic or parity nodes) to be\nregenerated exactly rather than only functionally or information-equivalently.\nWe show that Exact-MSR codes come with no loss of optimality with respect to\nrandom-network-coding based MSR codes (matching the cutset-based lower bound on\nrepair bandwidth) for the cases of: (a) k/n <= 1/2; and (b) k <= 3. Our\nconstructive approach is based on interference alignment techniques, and,\nunlike the previous class of random-network-coding based approaches, we provide\nexplicit and deterministic coding schemes that require a finite-field size of\nat most 2(n-k).\n