Optimal data conversion bandwidth found for special fault tolerant codes
Optimal Conversion Bandwidth for MDS Convertible Codes in the Split Regime with $r^F<k^F<r^I$
Information Theory
Summary
Distributed storage systems protect data by splitting and encoding it across multiple nodes. Sometimes, the system needs to change how much extra data it stores to handle different failure conditions. The paper focuses on a special kind of code, called MDS convertible codes, which can switch between configurations while keeping data safe. The authors solved an open problem about the best possible bandwidth needed to switch these codes in a tricky parameter range, and they also provide exact ways to achieve this efficiency.
What this means in practice
- •For cloud storage operators: Efficiently adjust data redundancy levels in storage clusters to optimize fault tolerance and storage overhead using minimal data movement.
- •For data center network engineers: Plan network resource allocation for code conversions in fault-tolerant storage systems with tight bounds on required bandwidth.
Authors
Lewen Wang, Sihuang Hu
Abstract
Erasure codes are widely used in distributed storage systems to provide fault tolerance. An $[n,k]$ erasure code encodes $k$ data symbols into $n$ coded symbols and distributes them across $n$ storage nodes. Once the code parameters are fixed, the achievable fault tolerance is also fixed. However, the failure rates of storage nodes may vary over time, and dynamically adapting the code parameters to these variations can substantially reduce storage overhead. Motivated by this observation, Maturana and Rashmi introduced convertible codes, which allow an $[n^I,k^I]$ initial code with redundancy $r^I=n^I-k^I$ to be transformed into an $[n^F,k^F]$ final code with redundancy $r^F=n^F-k^F$, while preserving the required code properties. Convertible codes whose initial and final codes are both MDS codes are called MDS convertible codes. They are of particular interest because MDS codes provide the maximum erasure tolerance for a given amount of storage overhead. Several works have established lower bounds and constructions for the bandwidth cost of MDS convertible codes in the split regime. However, the tight bound in the parameter range $r^F<k^F<r^I$ remains unknown. In this work, we establish a family of new rank inequalities for stable MDS convertible codes with linear conversion procedures and derive an improved lower bound on the bandwidth cost consisting of three cases for this remaining range. We prove that the bound is tight by presenting three explicit constructions, one for each case.