Replica Thresholds for Stripeless Erasure Coding Based on Symmetric Block Designs
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≤ k) guarantee recovery for p≥2. 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∗(A,p) for a fixed zero-diagonal SBIBD representative~A. We determine q∗(A,p) for p=1 and p=2. For p≥3, 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.
Related
- Replica Symmetry Breaking and Algorithmic Thresholds in Empirical Risk Minimization under Multi-Index Model
- Approximating the Gibbs Measure of Spherical Spin Glasses to Within o(N−1/2) in the Replica Symmetric Phase
- Interference Queueing Networks: A Replica Mean-Field Approach in the Symmetric Setting
- The replica symmetric solution for hypergraph independent sets in the critical regime
- A quantitative replica-symmetric bound for Sherrington--Kirkpatrick model in the entire de Almeida--Thouless region
BibTeX
@misc{luo2026replica,
title = {{Replica Thresholds for Stripeless Erasure Coding Based on Symmetric Block Designs}},
author = {Guiwen Luo and Xiao Li and Yaqiang Zhang and Ke Wang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.29149},
eprint = {2609.29149},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.29149},
}
RIS
TY - UNPB
TI - Replica Thresholds for Stripeless Erasure Coding Based on Symmetric Block Designs
AU - Guiwen Luo
AU - Xiao Li
AU - Yaqiang Zhang
AU - Ke Wang
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.29149
UR - https://arxiv.org/abs/2609.29149
AB - 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≤ k) guarantee recovery for p≥2. 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^∗(A,p) for a fixed zero-diagonal SBIBD representative~A. We determine q^∗(A,p) for p=1 and p=2. For p≥3, 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.
ER -