Cloud and peer-to-peer storage systems protect data with erasure codes. A file is cut into $k$ pieces and expanded into $n$ coded pieces on $n$ machines, so that any $k$ survivors can rebuild everything. Coding theorists have spent fifteen years making the repair of a single lost machine cheap. With the right code, a replacement machine downloads a small slice from each of several "helper" machines instead of pulling $k$ full pieces. These savings, however, have always been measured against machines that fail at random.
This proposal asks a different question. How many machines, or congested links, must an adversary knock out so that cheap repair of one chosen machine becomes impossible and the system falls back to expensive full decoding? We call that minimum the repair denial margin. We propose to compute it exactly, map when it is easy or hard to compute, and measure how it trades off against the two quantities coding theory already optimizes: repair bandwidth and sub-packetization, meaning the number of sub-blocks each stored piece must be split into.
The organizing idea comes from computational social choice. There, a manipulator who wants to elect a candidate faces a conjunction of constraints: beat every rival. A manipulator who only wants a candidate to lose faces a disjunction: let any rival win. That structural difference is why constructive manipulation is often NP-hard while destructive manipulation is polynomial. We argue the asymmetry flips in storage. The defender's problem, finding one cheap helper set, is disjunctive. The attacker's denial problem, destroying every cheap helper set, is a conjunction, which in general is a hitting-set problem.
Core Claim
Fix a failed node $i$, a cost $c_j$ per downloaded symbol from helper $j$ (cross-rack links cost more than intra-rack ones), and a repair budget $B$. Let $\mathrm{cost}(i,S)$ be the cheapest download achievable by the code's repair schemes when only helpers in $S$ are available. The repair denial margin is
$$\delta_B(i) \;=\; \min\Big\{\, |T| \;:\; T \subseteq [n]\setminus\{i\},\ \min_{S \subseteq [n]\setminus(\{i\}\cup T)} \mathrm{cost}(i,S) > B \,\Big\},$$
the fewest nodes whose removal pushes every remaining repair option over budget. Equivalently, $\delta_B(i)$ is the minimum hitting set of the family $\mathcal{F}_B(i)$ of helper sets that repair node $i$ within budget.
We make three claims. The first concerns complexity. When $\mathcal{F}_B(i)$ is determined by counts, $\delta_B$ has a closed form and is polynomial. Counts determine the family for classical MDS and regenerating codes with homogeneous costs, and for rack-aware codes whose repair depends only on how many helpers sit in each rack. When repair uses overlapping local groups, computing $\delta_B$ is NP-hard, as in codes that give each data block several disjoint or overlapping repair groups built from combinatorial packings (Cheng et al.). Computing $\delta_B$ is also fixed-parameter tractable in the number of removed nodes when the locality $r$ is small, because hitting sets whose sets have size at most $r$ admit $r^t$ branching.
The second concerns robustness. Codes that are best under benign failures can have the smallest margins. A rack-aware code that routes repair through a single relayer in each rack is one example. A locally repairable code that repairs from a single local group is another.
The third concerns sub-packetization. Large margins at tight budgets come from repair flexibility, meaning the code can repair efficiently from many different helper counts. Flexibility is exactly what costs sub-packetization. The margin therefore adds a third axis to the known bandwidth versus sub-packetization trade-off.
Relation to Prior Work
Several papers motivate this work by leaving the attacker out. Dimakis et al. define regenerating codes and the minimum-storage and minimum-bandwidth operating points, assuming any $d$ helpers are reachable. Hou et al. show that rack-aware codes cut cross-rack repair traffic by 33.3% over classical minimum-storage codes at $(n,k,r)=(12,8,4)$, with cooperative nodes. Li et al. build codes with near-optimal repair for every admissible helper count $d$, implicitly assuming the system chooses which $d$ helpers to use. None of these asks what happens when an adversary shapes the set of reachable helpers. We take their repair schemes as given and compute margins on top of them.
A second group supplies the codes on the sub-packetization side:
- Guruswami and Rawat trade an $\epsilon$ bandwidth slack for polynomial sub-packetization.
- Shi et al. formalize the bandwidth versus sub-packetization trade-off through set transformations.
- Ma et al. lower sub-packetization while keeping optimal access.
- The partial-MDS codes of Li et al. confine repair to local groups to keep sub-packetization small.
These papers define the frontier we extend. Our hypothesis is that the constructions saving the most sub-packetization do so partly by shrinking $\mathcal{F}_B$, and so lose margin.
Boneh et al. is the closest adversarial storage work. It adds local repair to blockchain data-availability sampling with polynomial commitments and reports a 2.1x repair-bandwidth gain over PeerDAS. Its adversary threatens correctness, and commitments stop forged data. They do not stop an adversary from making repair expensive by withholding or throttling, which is the threat we study.
From social choice we borrow method, not metaphor:
- The conjunction/disjunction explanation of why constructive weighted manipulation is NP-complete with three candidates while destructive manipulation is easy, and the same split in Borda control, give the prediction we test.
- The margin concept follows margin of victory for tournament solutions.
- The goal of a full classification follows the control dichotomy for pure scoring rules.
That literature finds destructive attacks easy, and we predict denial is the hard side, so the two appear to conflict. There is no real contradiction. In elections the destructive manipulator iterates over rivals and needs one to succeed. In storage the denier must defeat every helper set, which is the conjunctive side. Treating "destructive = easy" as a law rather than a consequence of logical structure would be the mistake. A second constraint comes from Rothe et al.'s experiments: worst-case hardness in control often melts on realistic instances. We treat that as a hypothesis to test for denial, not as a reason to skip the theory.
Research Program
Formalization. Each code family is represented by its explicit repair schemes. For each failed node, the representation lists the helper sets it supports and the per-helper download each set requires. This turns $\mathrm{cost}(i,S)$ into a lookup plus a minimization. We restrict to explicit repair schemes because deciding the optimal linear repair of an arbitrary code from its parity-check matrix is a separate problem that the file gives us no handle on. Two attack variants are covered: node removal, and link removal with weighted costs, the latter modeling congestion on top-of-rack links.
Complexity map. We then build the map in three parts.
- Closed forms for threshold-type families. For MDS repair with homogeneous costs, fixed-$d$ minimum-storage repair, all-degree repair, and rack-count-based rack-aware repair, $\delta_B$ should be a step function of $B$ readable from the code parameters.
- A hardness reduction from Hitting Set for codes with overlapping repair groups. Gadgets encode sets as repair groups, much as election gadgets encode clauses in candidate slates.
- A fixed-parameter algorithm in $t$ for locality $r$, plus W[2]-hardness in $t$ when group sizes are unbounded, which Hitting Set gives.
Measurement. We compute exact margins with an integer program, cross-checked by enumeration at small $n$. Doing this across code families produces the three-way frontier of bandwidth, sub-packetization and denial margin.
Baselines
The naive reference point is classical fault tolerance. It says an adversary must remove $n-k$ nodes before data is lost, and it implicitly treats cheap repair as available until then. Any code whose computed $\delta_B$ at the operating budget is far below $n-k$ shows that this reference misstates the threat. We report the ratio for every code.
The second baseline is random-failure degraded-repair analysis. For $t$ uniformly random unavailable nodes, it estimates the probability that repair exceeds $B$. It uses exactly the same codes, costs and budgets as our adversarial computation. Our method beats it in informativeness if the adversarial $t$ needed for denial with certainty is much smaller than the $t$ at which random failures deny repair with probability one half.
The third baseline is the attacker a practitioner would write: greedily remove the helper that appears in the most cheap sets, or the cheapest cross-rack relayer. It runs on the same instances with no tuning budget. On threshold families we predict greedy is optimal. On overlapping-group families we predict a measurable gap to the exact margin, and that gap is the empirical signature of the hardness boundary.
The strongest existing code on benign cost is the rack-aware minimum-storage construction of Hou et al., with its reported 33.3% cross-rack reduction at $(12,8,4)$. We evaluate it at its own optimal budget and at relaxed budgets. Our robustness claim is supported if its margin is smaller than that of a flexible all-degree code such as Li et al. at matched budget.
Two ablations isolate our key ingredients. Setting all link costs equal tests whether heterogeneity alone creates hardness and fragility. Fixing $d$ in otherwise identical flexible codes separates the effect of flexibility from the effect of sub-packetization.
Why not just…?
Why not just enumerate all attack sets, since real clusters are small? This is a real threat to the computational half of the proposal. For $n \le 20$ and small $t$, enumeration is fast, and we use it as ground truth. The contribution does not depend on attackers being unable to compute margins. It depends on the margin being a new, quantifiable robustness property of codes and on the structural map saying which designs have closed forms. The experiments report enumeration and integer-program runtimes as $n$ grows toward the $(40,30)$ regime highlighted by Li et al.. If those stay trivial on overlapping-group codes too, we will say the hardness result is of worst-case interest only, as Rothe et al. found for voting control.
Why not just use standard reliability analysis under random failures? Random models answer how often repair is expensive by accident. They say nothing about how cheaply someone can make it expensive on purpose. The random-failure baseline above measures exactly this gap on identical instances. A small gap would count against the proposal.
Why not just rely on authenticated repair as in data-availability sampling? Commitments like those in Boneh et al. ensure that downloaded symbols are correct. A withheld or throttled helper sends nothing to authenticate, so denial of cheap repair is untouched. The two defenses are complementary, and we will evaluate their multiplicity-code repair within our model if its repair schemes can be written explicitly.
Why bring social choice in at all? Its role is methodological. It supplies the conjunction/disjunction test for predicting which side of an attack is hard, the margin-of-victory style quantity, and reduction gadgets. The prediction that the asymmetry reverses in storage is falsifiable by the greedy-versus-exact gap. If greedy were optimal everywhere, the analogy would add nothing and we would report that.
Proposed Experiments
Codes and costs. We instantiate the following, at $(n,k)=(12,8)$ with four racks following Hou et al. and at larger sizes up to $(40,30)$ where sub-packetization permits:
- Reed–Solomon codes
- a fixed-degree minimum-storage regenerating code
- the all-degree codes of Li et al.
- the $\epsilon$-slack codes of Guruswami and Rawat
- set-transformed codes from Shi et al.
- partial-MDS codes from Li et al.
- locally repairable codes with multiple repair groups in the style of Rawat
- rack-aware codes
Link costs come from two sources: a two-level rack model, and a congestion-weighted variant whose per-rack background load is derived from the Ali-Cloud and Ten-Cloud access traces used by TSUE. No public failure or topology trace appears in the file. The absolute numbers are therefore illustrative, while the rankings are the object of study.
Decisive checks. Four checks decide the outcome:
- Closed-form margin predictions must match exact integer-program margins on every threshold family, and the hardness reduction must be validated on generated gadget instances.
- The greedy attacker must be optimal on threshold families but show a positive gap on overlapping-group families. If it does not, the reversed-asymmetry claim fails.
- We plot margin against budget and against sub-packetization. This tests whether flexible, higher-sub-packetization codes dominate on margin at tight budgets while low-sub-packetization and locality-based codes collapse to margins of one or two.
- We track exact-solver runtime as $n$ grows on overlapping-group codes. This tells us whether denial hardness survives on realistic instances or is as fragile as control hardness in elections.
A clear ranking reversal would change how storage designers should read the benign-bandwidth numbers. The prediction is that the best benign code, the rack-aware construction, has a margin of one relayer while a flexible code of higher sub-packetization needs several removals.
References
- Optimal Locally Repairable Systematic Codes Based on Packings
- Network Coding for Distributed Storage Systems
- Rack-Aware Regenerating Codes for Data Centers
- MDS Array Codes With (Near) Optimal Repair Bandwidth for All Admissible Repair Degrees
- MDS Code Constructions with Small Sub-packetization and Near-optimal Repair Bandwidth.
- Set Transformation: Trade-Off Between Repair Bandwidth and Sub-Packetization
- Generic Construction of Optimal-Access Binary MDS Array Codes with Smaller Sub-packetization
- PMDS Array Codes With Small Sub-packetization, Small Repair Bandwidth/Rebuilding Access
- Data Availability Sampling with Repair
- Complexity of Manipulating Elections with Few Candidates
- Closing the Gap of Control Complexity in Borda Elections: Solving ten open cases
- Refining Tournament Solutions via Margin of Victory
- A Control Dichotomy for Pure Scoring Rules
- Control Complexity in Bucklin, Fallback, and Plurality Voting: An Experimental Approach
- On locality in distributed storage systems
- TSUE: A Two-Stage Data Update Method for an Erasure Coded Cluster File System