Multilevel diversity coding with regeneration

Chao Tian, Tie Liu

Introduction

In modern cloud data centers, distributed storage systems must manage massive volumes of data with varying reliability and latency requirements. For instance, critical real-time billing data requires higher redundancy and faster recovery than archival backups. While standard "erasure codes" and "regenerating codes" optimize the tradeoff between storage space and network repair bandwidth, they typically treat all data as having uniform priority. This paper introduces Multilevel Diversity Coding with Regeneration (MLD-R) to bridge this gap, exploring whether encoding different data tiers separately or jointly ("mixing" them) yields better efficiency.

The MLD-R Problem

When a storage node fails, the system must download data from surviving nodes to reconstruct the lost information. The amount of data stored per node is denoted by $\alpha$, and the data downloaded for repair is the repair bandwidth $\beta$. Standard regenerating codes optimize the $(\alpha, \beta)$ tradeoff for a single reliability level. MLD-R extends this to multiple message levels, each requiring reconstruction from a different number of surviving nodes.

The MLD-R system model illustrates node failure, repair (regeneration), and data decoding from a subset of nodes.

As shown in the figure above, the model considers $n$ nodes. If a node fails (e.g., Node 1), it is repaired by downloading $\beta$ amount of data from the remaining $n-1$ nodes to create a replacement (Node 1'). Simultaneously, a decoder must be able to retrieve specific message subsets by connecting to any $k$ nodes.

Key Findings: The Power of Mixing

A central question in MLD-R is whether "separate coding"—applying independent optimal codes to each data tier—is sufficient. The authors' research reveals a nuanced answer based on the size of the network:

  • Minimum Storage Optimality: If the primary goal is to minimize disk space (the Minimum Storage Regenerating or MSR point), separate coding is perfectly optimal for any number of nodes.
  • The 3-Node Threshold: In small systems with only 3 nodes, separate coding is optimal across the entire storage-repair tradeoff curve. There is no mathematical advantage to mixing data tiers.
  • The Advantage of Joint Coding ($n \ge 4$): For systems with 4 or more nodes, the authors prove that "mixing" data tiers—mathematically combining symbols from different priority levels using finite field arithmetic—strictly outperforms separate coding.

Results for 4-Node Systems

The paper provides a complete characterization of the tradeoff region for a 4-node system. By designing a novel algebraic code, the authors demonstrated that joint coding unlocks "sweet spots" on the efficiency curve that are unreachable by separate schemes.

Comparison of the MLD-R rate region versus separate coding for a four-node system, showing the performance gain from joint encoding.

As illustrated in the plot, the red solid line (MLD-R rate region) extends beyond the blue dashed line (separate coding). Specifically, the authors highlight the point $(4/9, 2/9)$ as a provable improvement where joint coding reduces the required resources compared to the best possible separate coding approach.

Methodology and Future Work

To derive these bounds, the authors moved beyond traditional human-derived information inequalities, instead employing computational converse proofs. By using computer-assisted tabulation of Shannon-type inequalities, they generated verifiable outer bounds for the capacity regions.

While this work focuses on $n=4$ and repairs involving all surviving nodes ($d=n-1$), it lays the groundwork for generalizing mixed-tier coding to larger systems and more complex repair scenarios, such as Locally Repairable Codes (LRCs) used in modern cloud architectures.

Summary updated

BibTeX
@article{tian2016multilevel,
  author = {Chao Tian and Tie Liu},
  title = {{Multilevel diversity coding with regeneration}},
  journal = {IEEE Trans. Information Theory},
  year = {2016},
  doi = {10.1109/tit.2016.2576467},
}
Figure