Replica counts needed to recover data with symmetric erasure codes
Replica Thresholds for Stripeless Erasure Coding Based on Symmetric Block Designs
Information Theory
Summary
The paper studies how many copies of a data piece are needed to recover it if some storage nodes fail. The authors focus on special codes built from symmetric designs, which arrange data in balanced blocks. They find exact replica numbers required for up to two failures and identify structural reasons affecting higher failure cases. Their work refines previous limits and clarifies when fewer copies suffice for full recovery.
What this means in practice
- •For distributed storage engineers: Determine minimal data replication factors to guarantee recovery from node failures using symmetric block design codes.
- •For network reliability teams: Optimize fault tolerance parameters in erasure-coded networks to minimize replicas while ensuring data availability during multiple failures.
A theory result. No direct application yet.
Authors
Guiwen Luo, Xiao Li, Yaqiang Zhang, Ke Wang
Abstract
This paper investigates a fundamental question in stripeless erasure coding based on symmetric balanced incomplete block designs (SBIBDs): how many replicas per object are precisely required to guarantee recovery from any set of at most $p$ node failures? We refine the known sufficient recovery guarantee for the generalized SBIBD $(v,k,λ)$ construction. One replica is necessary and sufficient for $p=1$, and $q=λ(p-1)+2$ replicas ($q\le k$) guarantee recovery for $p\ge2$. Recovery takes one round for $p=2$ and at most two rounds in general. To study the tightness of this count, we define the universal replica threshold $q^\ast(A,p)$ for a fixed zero-diagonal SBIBD representative~$A$. We determine $q^\ast(A,p)$ for $p=1$ and $p=2$. For $p\ge3$, we identify pairwise separated sets and private target permutations as the structures determining whether the sufficient count is tight or can be further reduced. These conditions give exact thresholds for all but the case where $λ>1$ and $A$ contains no pairwise separated set of size~$p$. We improve the bounds for this remaining case and leave its exact threshold open. Finally, we give sufficient conditions for pairwise separated sets and show how affinity relabeling can realize private target permutations.