Abstract
The distance-3 cyclic lowest-density MDS array code (called the C-Code) is a good candidate for RAID 6 because of its optimal storage efficiency, optimal update complexity, optimal length, and cyclic symmetry. In this paper, the underlying connections between C-Codes (or quasi-C-Codes) and starters in group theory are revealed. It is shown that each C-Code (or quasi-C-Code) of length $2n$ can be constructed using an even starter (or even multi-starter) in $(Z_{2n},+)$. It is also shown that each C-Code (or quasi-C-Code) has a twin C-Code (or quasi-C-Code). Then, four infinite families (three of which are new) of C-Codes of length $p-1$ are constructed, where $p$ is a prime. Besides the family of length $p-1$, C-Codes for some sporadic even lengths are also presented. Even so, there are still some even lengths (such as 8) for which C-Codes do not exist. To cover this limitation, two infinite families (one of which is new) of quasi-C-Codes of length $2(p-1)$ are constructed for these even lengths.
Introduction
In modern data storage, RAID 6 is a critical standard for reliability, designed to withstand the simultaneous failure of any two disks. Achieving this reliability efficiently requires Maximum Distance Separable (MDS) codes. Ideally, these codes should possess three key properties: optimal storage efficiency, optimal update complexity (lowest-density), and cyclic symmetry.
While several array codes have been developed, few satisfy all these criteria simultaneously. For instance, B-Codes are known for being lowest-density and MDS but often lack cyclic symmetry, which simplifies hardware and software implementation. C-Codes (Cyclic Codes) represent a subtype that achieves this "holy grail" of properties.
Methodology: Bridging Graph Theory and Group Theory
The construction of C-Codes has historically been challenging. This research addresses the problem by establishing a formal link between coding theory and combinatorial design.
Graph Representation
The authors represent parity bits as vertices in a graph and data bits as edges. A valid C-Code corresponds to a "perfect one-factorization" (P1F) of a graph—a specific partitioning of edges where every pair of partitions forms a Hamiltonian cycle.
The Role of Starters
The core innovation lies in using even starters within additive groups $(Z_{2n}, +)$. An even starter is a mathematical object—a set of pairs—that satisfies specific difference properties. The paper proves that such starters can systematically generate the entire cyclic structure of a C-Code. This allows for the transformation of non-cyclic codes into perfectly symmetric C-Codes by identifying the appropriate generator in a cyclic group.
Key Insights
- The Algebraic Bridge: By identifying C-Codes as "bipyramidal perfect one-factorizations," the research leverages decades of combinatorial design theory to solve practical storage problems.
- Twin Codes: Every C-Code is shown to have a "twin" instance, offering designers multiple implementation options for the same code length.
- The Length 8 Limitation: The study confirms that a pure C-Code of length 8 is mathematically impossible. To address this, the authors introduced quasi-C-codes, which maintain partial symmetry for lengths where full cyclic symmetry is unattainable.
Results and Conclusion
The research introduces four infinite families of C-Codes (three of which are new) and two families of quasi-C-codes. Through exhaustive computer searches, the existence of these codes was validated for all even lengths from 4 to 36, with additional sporadic successes for lengths such as 14, 20, 26, and 50.
All constructed codes maintain optimal performance: they are MDS and feature an update complexity of exactly 2. While some lengths (e.g., 44, 48) remain open questions due to the complexity of finding perfect one-factorizations for large graphs, this work significantly expands the toolkit for designing high-performance, symmetric RAID 6 storage systems.
Summary updated