PaperlayerView exact revision on arXiv

Source-linked AI summary

Replica Thresholds for Stripeless Erasure Coding Based on Symmetric Block Designs

Guiwen Luo, Xiao Li, Yaqiang Zhang, Ke Wang

arXiv:2609.29149v1cs.ITmath.IT

TL;DR

The paper studies how many replicas stripeless SBIBD coding needs to guarantee recovery under up to p node failures, and how that threshold varies with the chosen representative. It classifies the threshold using structural properties of the representative, with exact results except for one identified case.

  • Problem

    The paper asks for the minimum replica count that guarantees recovery under every legal placement and failure set of at most p nodes, and whether a sufficient count can be reduced for a fixed representative.

    Source: §I · p. 2

  • Method

    It defines q*(A, p) and classifies it using pairwise separated sets, private target permutations, and affinity relabelings.

    Source: §I · p. 2, B. Private target permutations under… · p. 17

  • Results

    The threshold classification is exact except when p≥3, λ>1, and A has no pairwise separated set of size p.

    Source: §I · p. 2, D. Summary of thresholds for fixed… · p. 12

  • Takeaways & Limitations

    For a suitable SBIBD representative, the required replica count can be reduced by one compared with Nos and FLESC.

    Source: §VI · p. 18

    The exact threshold remains open when p≥3, λ>1, and the representative has no pairwise separated set of size p.

    Source: §I · p. 2

Abstract

from arXiv · show

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,\lambda)$ construction. One replica is necessary and sufficient for $p=1$, and $q=\lambda(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 $\lambda>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.

I. INTRODUCTION

The paper extends SBIBD-based stripeless coding and asks how many replicas guarantee recovery under up to p node failures. It refines recovery guarantees and classifies when the sufficient replica count is tight for a fixed representative.

I. INTRODUCTION

  • Nos’s λ=1 design restricts available parameters, and neither Nos nor FLESC determines whether its sufficient replica count is tight for a fixed representative.FLESC allows general admissible λ, expanding available design choices when the corresponding SBIBDs exist.Source: §I · p. 2
  • One replica is necessary and sufficient for p=1; for p≥2, λ(p−1)+2 replicas suffice when the count is at most k.For p=2, every lost object is directly recoverable; for p≥3, recovery takes at most two rounds.Source: §I · p. 2
  • The universal threshold q*(A, p) depends on the fixed representative’s structure; the classification is exact except for p ≥3, λ>1, and no pairwise separated set of size p.The paper uses pairwise separated sets and private target permutations to classify when the sufficient count is tight or reducible.Source: §I · p. 2
  • The paper gives sufficient conditions and a greedy construction for pairwise separated sets, and shows affinity relabelings can realize private target permutations.For a suitable representative, the required replica count can be reduced by one compared with Nos and FLESC.Source: §I · p. 2

A. Symmetric balanced incomplete block designs

  • An SBIBD representative is an incidence matrix from independently labeled points and blocks; a zero-diagonal representative has no diagonal incidences.Every SBIBD admits a zero-diagonal representative.Source: A. Symmetric balanced incomplete block… · p. 3

B. Stripeless erasure coding on an SBIBD

  • Each object independently selects q admissible targets, sends replicas there, and those replicas are combined into XOR parities and discarded after parity formation.A legal placement partitions incoming replicas at each node into k-tuples, one from each prescribed source node.Source: §I · p. 1, B. Stripeless erasure coding on an SBIBD · p. 4

III. UNIVERSAL RECOVERY GUARANTEE

The paper proves a replica count that guarantees recovery for every legal placement and any failure set of at most p nodes. It then introduces a representative-specific threshold to determine when that sufficient count can be reduced.

III. UNIVERSAL RECOVERY GUARANTEE

  • The guarantee treats p=1, p=2, and p≥3 separately: one replica suffices for one failure, two-failure recovery is direct, and the general recovery process uses at most two rounds.The proof applies uniformly to every legal placement.Source: §III · p. 4
  • For integer p ≥ 1, let A be a fixed zero-diagonal representative of SBIBD(v, k, λ) and q be given by (3); if q ≤ k, every legal placement with exactly q distinct target nodes per object permits recovery after any at most p node failures.If at most two nodes fail, every lost object is directly recoverable. In general, directly recoverable lost objects are restored in the first round and all remaining lost objects in the second round.Source: §III · p. 4
  • For p≥3, a counting argument forces an alive parity with exactly one lost encodee, enabling its recovery and then recovery of the target object.The argument bounds cases involving failed parity hosts and parities with multiple lost encodees; the remaining pair yields the direct recovery step.Source: §III · pp. 5–6

IV. REFINING THE SUFFICIENT REPLICA COUNT

  • The sufficient guarantee does not settle whether fewer replicas work for a fixed zero-diagonal representative, motivating the threshold q*(A, p).The paper derives unconditional bounds and then uses incidence structures to obtain exact thresholds or sharper bounds.Source: §IV · p. 6

A. Threshold definition and unconditional bounds

For a fixed zero-diagonal SBIBD representative, the universal replica threshold is the minimum count guaranteeing recovery for every legal placement and failure set. The section classifies this threshold exactly for p=1 and p=2, and for p≥3 according to pairwise separation and private target permutations, with one case remaining open.

A. Threshold definition and unconditional bounds

  • For a fixed representative A, q*(A, p) is the minimum replica count guaranteeing recovery for every legal placement and every failure set of at most p nodes; q*(A, 1) = 1.The stated feasibility assumptions are k ≥ 1 for p = 1 and k ≥ λ(p − 1) + 2 for p ≥ 2.Source: A. Threshold definition and… · p. 6

B. Exact classification for p = 2

C. Classification for p ≥3

  • For p ≥ 3, if A has no pairwise separated set of size p, then q*(A, p) = p.The recovery bound assumes k ≥ λ(p − 1) + 1 and uses an iterative procedure that recovers all lost objects in at most p stages.Source: C. Classification for p ≥3 · pp. 8, 10
  • For λ > 1 and no pairwise separated set of size p, the exact threshold remains open because finer local incidence information affects its value.The SBIBD parameters and pairwise-separation status alone do not capture that information.Source: C. Classification for p ≥3 · p. 11
  • For p ≥ 3, if A contains a pairwise separated set of size p, the threshold is λ(p − 1) + 2 if any such set admits a private target permutation, and λ(p − 1) + 1 otherwise.This classification assumes k ≥ λ(p − 1) + 2.Source: C. Classification for p ≥3 · p. 11

D. Summary of thresholds for fixed representatives

The threshold summary classifies fixed representatives by failure count and structural properties of the design. One case in the p≥3 classification remains unresolved.

D. Summary of thresholds for fixed representatives

  • For p = 2, the threshold cases are distinguished by whether a reciprocal pair exists; for p ≥ 3, the classification uses pairwise separated sets and private target permutations.Table I summarizes exact values and bounds under its stated feasibility assumptions.Source: D. Summary of thresholds for fixed… · p. 12, Table I · p. 13
  • The exact threshold remains open when p ≥ 3, λ > 1, and A contains no pairwise separated set of size p.The table’s classification is exact outside this case.Source: D. Summary of thresholds for fixed… · p. 12

V. EXISTENCE AND RELABELING OF THRESHOLD STRUCTURES

This section examines when the structures used in the threshold classification exist and how relabeling can realize some of them.

V. EXISTENCE AND RELABELING OF THRESHOLD STRUCTURES

  • The threshold classification uses reciprocal pairs, pairwise separated sets, and private target permutations.Pairwise separation depends only on the underlying SBIBD, while a private target permutation may also depend on affinity labeling.Source: §V · p. 13
  • For p = 2, pairwise separation is automatic, and a private target permutation is precisely a reciprocal pair.This links the two-node threshold condition to the structures used for p ≥ 3.Source: §V · p. 13
  • The section studies pairwise-separated-set existence before showing how suitable zero-diagonal labelings realize private target permutations.Source: §V · p. 13

A. Existence and construction of pairwise separated sets

The section gives a sufficient condition and greedy construction for pairwise separated sets, then establishes when such sets must exist and presents feasible designs where they do not. For fixed p and λ, the nonexistence case is confined to finitely many feasible k values.

A. Existence and construction of pairwise separated sets

  • The stated parameter condition guarantees that the greedy construction can continue until the selected set has size p.At each step, an eligible row is added while preserving pairwise separation; the condition for m = p −1 guarantees the final extension.Source: A. Existence and construction of… · p. 13
  • Incidence in PG(3, ρ) supplies feasible designs with no pairwise separated set of size p for 3 ≤p ≤ρ.Any three points lie in a plane; the smallest example has parameters (40, 13, 4).Source: A. Existence and construction of… · p. 14
  • For fixed p ≥3 and λ, every existing SBIBD contains a pairwise separated set of size p once feasible k is sufficiently large.Consequently, for fixed p and λ, designs without such a set can occur for only finitely many k values.Source: A. Existence and construction of… · p. 14

B. Private target permutations under zero-diagonal relabeling

A pairwise separated set can be used to construct a zero-diagonal affinity labeling with a private target permutation, yielding the upper-end replica threshold. The guarantee concerns a suitable representative, not every fixed zero-diagonal representative.

B. Private target permutations under zero-diagonal relabeling

  • If A contains a pairwise separated set F of size p and k ≥λ(p −1) + 2, column relabeling yields a zero-diagonal representative where F has a private target permutation.The construction selects distinct columns with zeros in distinct rows, then uses a matching to complete the relabeling.Source: B. Private target permutations under… · pp. 14, 16, 17
  • For p = 2, a zero-diagonal representative of SBIBD(7, 3, 1) without a reciprocal pair has threshold 2, while another labeling has threshold 3.Proposition V.3 establishes that some zero-diagonal labeling of every underlying SBIBD contains a reciprocal pair, not that every representative does.Source: B. Private target permutations under… · p. 17
  • Independent point and block relabeling need not preserve a zero diagonal, while simultaneous node relabeling preserves whether a fixed representative has a private target permutation.The matching construction instead finds a different affinity labeling that remains zero-diagonal.Source: B. Private target permutations under… · p. 17
  • For fixed p ≥3 and λ, every existing SBIBD with sufficiently large feasible k admits a zero-diagonal labeling attaining q∗(A′, p) = λ(p−1)+2.This does not guarantee that every fixed representative attains that endpoint; the threshold depends on local incidence structures.Source: B. Private target permutations under… · p. 17

VI. DISCUSSION

The discussion compares parameter flexibility, affinity labeling, and redundancy in the generalized stripeless scheme.

VI. DISCUSSION

  • The discussion treats parameter flexibility relative to Nos, SBIBD selection and affinity labeling, and resulting failure tolerance and redundancy.These are the three aspects identified for discussion.Source: §VI · p. 18
  • Compared with Nos, the construction provides more flexible parameter choices.The flexibility is discussed alongside the selection of SBIBDs and their affinity labelings.Source: §VI · p. 18
  • For a suitable SBIBD representative A, the required replica count can be reduced by one.The reduction is conditional on the representative being suitable.Source: §VI · p. 18

A. Parameter flexibility beyond Nos

Allowing general admissible λ values expands the available SBIBD parameter choices beyond Nos, with a tradeoff between cluster size and sufficient replicas.

A. Parameter flexibility beyond Nos

  • Nos uses an SBIBD with λ = 1, while allowing any admissible value of λ changes the SBIBD identity; these passages do not provide the resulting identity.Source: A. Parameter flexibility beyond Nos · p. 18
  • An SBIBD(11, 5, 2) exists although no SBIBD(11, k, 1) exists; for p = 2, the former supports the sufficient count q = 4.The λ = 1 nonexistence follows because k² −k + 1 = 11 has no integral solution.Source: A. Parameter flexibility beyond Nos · p. 18
  • For fixed k, increasing λ reduces the design-permitted v but increases the sufficient replica count.For prescribed v and p, the parameters must also satisfy the stated constraints and correspond to an existing SBIBD.Source: A. Parameter flexibility beyond Nos · p. 18

B. Selecting a design and an affinity labeling

Choosing the SBIBD representative and its affinity labeling can reduce replica thresholds, with corresponding savings in encoding traffic and parity storage. The paper also states the scope of its exact threshold results and connects the structural criteria to design selection.

B. Selecting a design and an affinity labeling

  • Different zero-diagonal affinity labelings of the same SBIBD can yield different replica thresholds because labeling determines which points and blocks represent the storage nodes.Design parameters and the underlying block design set the admissible incidence structure; affinity labeling then selects the node correspondence.Source: B. Selecting a design and an affinity… · p. 18
  • For λ = 1, a suitable representative reduces the sufficient count from p + 1 to p by avoiding the relevant reciprocal-pair or private-target-permutation obstruction.For p ≥3, a design with no pairwise separated set of size p also ensures the latter condition.Source: B. Selecting a design and an affinity… · p. 19

C. Failure tolerance and redundancy

  • Reducing the replica threshold by one cuts encoding traffic by one replica per object and persistent parity storage by 1/k.The encoding transmission cost is q replicas per object.Source: C. Failure tolerance and redundancy · p. 19

VII. CONCLUSION

  • The recovery guarantee is uniform over legal placements, with direct recovery for p = 2 and at most two recovery rounds for p ≥3.The exact threshold remains open when p ≥3, λ > 1, and the representative has no pairwise separated set of size p; the paper notes that finer incidence information may matter.Source: §VII · p. 20
  • Existence and relabeling results connect the structural threshold classification to selecting SBIBDs and affinity labelings for coding applications.Source: §VII · p. 20

APPENDIX

The appendix establishes that zero-diagonal representatives exist and illustrates structural obstructions that determine exact thresholds in specific cases. Its examples include a reciprocal-pair obstruction for p = 2 and a private-target-permutation obstruction for p = 3.

A. Existence of zero-diagonal representatives

  • Every SBIBD(v, k, λ) admits a zero-diagonal representative, obtained by applying Hall’s theorem to a bipartite graph and using a perfect matching.The proof uses the equal row and column degrees to verify Hall’s condition.Source: A. Existence of zero-diagonal… · p. 21

B. An obstruction from a reciprocal pair for p = 2

  • For the SBIBD(7, 4, 2) example, a reciprocal pair makes q = 3 fail, giving the exact threshold q∗(A, 2) = 4.When nodes 0 and 3 fail, both surviving equations reduce to x ⊕ y = γ, so their coefficient matrix has rank one.Source: B. An obstruction from a reciprocal… · p. 21

C. A representative with a private target permutation on a pairwise separated triple

  • For F = {0, 1, 4}, disjoint target sets make F pairwise separated, and 0 →1 →4 →0 is a private target permutation.The example then shows q = 5 fails while q = 6 permits recovery, yielding q∗(A, 3) = 6.Source: C. A representative with a private… · p. 22

D. A relabeled representative with no private target permutation on any pairwise separated triple

Relabeling the columns can preserve the SBIBD while changing whether pairwise separated triples admit private target permutations. The appendix’s enumeration gives a representative with none of these permutations.

D. A relabeled representative with no private target permutation on any pairwise separated triple

  • Permuting columns produces another zero-diagonal representative of the same SBIBD(16, 6, 2), yet the universal replica threshold depends on the affinity labeling.The rows remain fixed in the relabeling.Source: D. A relabeled representative with no… · p. 23
  • Among 240 pairwise separated triples, the counts with s(G) = 0, 1, and 2 are 37, 136, and 67, respectively; none has s(G) = 3.Because private targets for different sources must be distinct, a triple admits a private target permutation exactly when s(G) = 3.Source: D. A relabeled representative with no… · p. 23
Loading 2609.29149v1…