Plotkin-type codes reveal new recovery sets for better data service rates
Recovery Set Structures and Service Rates of Codes Obtained by the Plotkin-type Construction
Information Theory
Summary
In systems that store data across many servers, it's important to recover data quickly without overloading any single server. The authors study a special way to build error-correcting codes called Plotkin-type construction and how it creates new ways to recover data. They show that recovery groups for these codes relate closely to those from the original code, revealing extra recovery options. This helps understand and improve the combinations of requests the system can handle at the same time. Their method extends to a famous family of codes, Reed-Muller codes, to find recovery sets recursively.
What this means in practice
- •For distributed storage engineers: Design storage systems with improved data recovery options and service rate guarantees by using Plotkin-type constructed codes.
- •For network capacity planners: Estimate feasible simultaneous data request rates in multi-server systems using service rate region bounds derived from Plotkin-type codes.
Authors
Priyanka Choudhary, Maheshanand Bhaintwal
Abstract
In distributed storage systems, redundancy enables a single data object to be reconstructed using several disjoint groups of servers. The resulting service rate region (SRR) captures all combinations of object request rates that the system can support simultaneously without overloading any individual server. We analyze the SRR of binary codes obtained via the Plotkin-type construction. We demonstrate that each recovery set for an information object of the Plotkin-type code $\mathcal{C}_p$ induces a corresponding recovery set for the same data object characterized by the underlying code $\mathcal{C}$. Furthermore, by characterizing the recovery sets structure of $\mathcal{C}_p$ in terms of the recovery set structure of $\mathcal{C}$, we identify the additional recovery sets introduced by this construction. Using the associated recovery hypergraphs, we establish bounds on the SRRs of $\mathcal{C}_p$ and iterated code $\mathcal{C}_{p^m}$ in terms of the SRR of $\mathcal{C}$. We consider the family of first-order binary Reed-Muller codes and show how the recovery structure, and consequently, the service rates of R$(1,m)$ for arbitrary $m$ can be recursively derived from a generator matrix of R$(1,2)$ through our results for successive Plotkin-type constructions.