Erasure Codes That Can Absorb Tomorrow's Data Rules

Cloud storage systems protect data with erasure codes. An erasure code splits each file into data pieces, adds computed "parity" pieces, and spreads everything across machines so that lost pieces can be rebuilt. The layout and the arithmetic of these codes are fixed when the data is written, and data often stays in place for years. Data rules move on a different clock. A jurisdiction can later require that its residents' data be recoverable using only machines inside its borders, or that it tolerate more simultaneous failures. When that happens, operators today re-encode, which means reading data and rewriting parity across the fleet. We propose to design codes so that a rule change confined to one jurisdiction can be met by adding parity computed only from that jurisdiction's pieces. The global recovery guarantee must survive the change. We also propose to measure what this foresight costs in the size of the arithmetic, and therefore in encoding speed.

The link between the two research directions is concrete. Coding theory has spent a decade shrinking the field size of maximally recoverable codes. The field is the finite number system in which parity is computed, and a smaller field means symbols fit in 8- or 16-bit machine words, where CPU vector instructions run fast. Regulatory-lag research documents that rules arrive late, piecemeal, and differently in each jurisdiction. The design question is how large a field one must pay for today to stay maximally recoverable under the rule changes that are plausible over the data's lifetime. Our answer has two parts. Some upgrades, namely adding local parity within one jurisdiction's group, should cost no field size beyond designing for the final layout. Others, namely re-partitioning groups along new borders, have an unknown and probably real price. That price is what we will bound.

Background and the Gap

A locally repairable code arranges pieces into small local groups, each with $a$ local parities, so that a single failure is repaired from about $r$ neighbours instead of the whole stripe. A further $h$ global parities cover larger failures. A maximally recoverable (MR) code is one of these that corrects every failure pattern its layout could possibly correct. MR codes need large fields, and the field-size question is well studied. Explicit Maximally Recoverable Codes with Locality gave explicit constructions with field size $O(k^{h-1})$ for $k$ data symbols and proved an $\Omega(k)$ lower bound. For $k=60, r=4, h=4$ this cut symbol width from 80 bits to 16. Improved Maximally Recoverable LRCs using Skew Polynomials reached $q \le (O(\max\{r,n/r\}))^{\min\{h,r-a\}}$ for $n$ total symbols, which is tight at $\Theta_h(n^{h/2})$ when $r\approx\sqrt n$. It does this by mapping local groups to algebraic conjugacy classes of polynomials whose multiplication is not commutative. A Construction of Maximally Recoverable Codes with Order-Optimal Field Size matches this with linearized Reed–Solomon codes and handles the binary, hardware-friendly case for $h=3$. Lower Bounds for Maximally Recoverable Tensor Codes and Higher Order MDS Codes supplies lower-bound techniques and a polynomial-time max-flow test of which erasure patterns are correctable for tensor codes with one local parity.

These papers supply our methods. They share one assumption: the layout ($r$, $a$, $h$, and the grouping) is fixed forever. That assumption is exactly what regulatory lag breaks.

On the governance side, several papers motivate the problem rather than supply methods.

  • Navigating Governance Paradigms mapped 15 governance processes across six jurisdictions and found only one, "Data Sourcing," shared by all six. Rules therefore diverge per region, which is why changes will arrive one local group at a time.
  • The Bottleneck in AI Governance and Oversight fit a two-stage hurdle model to 1,419 U.S. state AI bills. Volume grew over 35-fold, 32.3% of bills reached a terminal outcome, and specialist committees cut floor access (OR = 0.34). This is the only quantitative handle in our material on how often and how unpredictably rules land.
  • Advancing Science- and Evidence-based AI Policy proposed "If-Then Protocols," which commit in advance to rules triggered by measurable thresholds. Pre-announced conditional rules make the set of possible future layouts foreseeable even when their timing is not. That foreseeability is what makes pre-designing for them possible.

No paper in the file joins these threads. The closest boundary work concerns runtime compliance at the application layer: temporal-logic monitoring in Auditing, Monitoring, and Intervention for Compliance of Advanced AI Systems and copyright guardrails in SHIELD. Neither touches storage codes. Our work sits at the storage layer instead and asks an algebraic question those works do not.

Core Claim

Fix a topology family $\mathcal T$: the starting layout plus every layout a jurisdiction might later demand. Examples include one extra local parity in a named group, one extra parity scoped to a jurisdiction, or splitting a group along a border. A mother code for $\mathcal T$ is a single code over one field $\mathbb F_q$. It stores only the parities of the starting layout, and it has the property that each target layout is reached by computing and adding the parities that layout calls for. Every intermediate code must be maximally recoverable.

For an add-only upgrade, meaning one that adds local parities within a group while keeping the grouping fixed, the new parity reads only that group's $r$ symbols and leaves every other jurisdiction untouched. Group splits are the exception, discussed below. The cost we care about is the smallest field such a mother code needs:

$$q^*(\mathcal T) \;\ge\; \max_{T\in\mathcal T} q_{\mathrm{MR}}(T),$$

where $q_{\mathrm{MR}}(T)$ is the minimal field size of an MR code for the single layout $T$. The research question is when this inequality is tight and how large the gap is when it is not.

Add-only local upgrades. For adding local parities, we conjecture the bound is tight. The argument runs as follows. Take an MR code for the final layout, which has $a+1$ local parities. Delete one local parity from a group, a step called puncturing. The resulting code should remain MR for the $a$-parity layout, because any pattern correctable in the smaller layout becomes a correctable pattern of the larger one once the deleted parity is counted as erased. Two consequences follow. Upgrading from the punctured code back to the full one is a purely local computation. And because the skew-polynomial bound has exponent $\min\{h, r-a\}$, which falls as $a$ grows, designing for more local parity may cost no extra field size at all.

Upgrades that change the grouping. Splitting a group along a new border, or adding a global parity that must protect only one jurisdiction, cannot be obtained by puncturing a single MR code. Here we expect $q^*(\mathcal T)$ to exceed the maximum over single layouts. Bounding that gap is the main theoretical target.

Research Program

Theory. The first step is to prove or refute the puncturing claim for arbitrary $a$ and $h$. The second is to build mother codes for split families. We will adapt the conjugacy-class construction of Gopi and Guruswami, reserving classes so that a group can later be divided into sub-groups that each own a class. We will also adapt the linearized Reed–Solomon construction of Cai et al., which keeps even characteristic so the result stays hardware-friendly.

For lower bounds, we will adapt the subspace-intersection arguments of Brakensiek et al. The key observation is that asking one code to be MR for two incompatible groupings imposes the union of their generic-position constraints. We aim to show a family where this union forces the field-size exponent up by at least one.

For verification, we will turn the "is this pattern correctable" test into an audit anyone can run from the code's public description, without seeing any data. Where the code has tensor structure with $a=1$, the max-flow test of Brakensiek et al. applies directly. Otherwise, at small parameters, we will use exhaustive rank checks.

Systems. We will implement mother codes and standard codes over $\mathbb F_{2^8}$, $\mathbb F_{2^{16}}$ and $\mathbb F_{2^{32}}$ using vectorized table arithmetic. We will also build a cluster simulator with six jurisdictions, matching the Luna et al. map, which replays streams of rule-change events.

The regulatory-lag lens. Governance data enters as an event model. We will fit arrival and enactment rates using the hurdle-model structure and rates of Khan et al. on the LegiScan state AI bills dataset. These bills are a proxy for how legislatures move, not a record of storage rules, so every conclusion will be reported across a sweep of event rates. The fitted rate is one marked point on that sweep, not the answer.

The operator's choice is then a simple expected-cost comparison over a data lifetime $L$:

$$\mathbb E[\mathrm{cost}] \;=\; L\cdot c_{\mathrm{enc}}(q) \;+\; \sum_{T\in\mathcal T}\lambda_T L\cdot c_{\mathrm{up}}(T,q).$$

Here $c_{\mathrm{enc}}(q)$ is the steady encoding cost per unit time in field $\mathbb F_q$, $\lambda_T$ is the arrival rate of rule changes demanding layout $T$, and $c_{\mathrm{up}}$ is the traffic and compute cost of meeting the change. The comparison is between upgrading a mother code and re-encoding a standard code. We will also measure infrastructure-level regulatory lag: the time between a rule taking effect and the stored data actually satisfying it. That quantity is small when an upgrade is local and large when it requires re-encoding.

Baselines

Re-encode on every change. The naive reference is what operators already do. Data is stored with a standard Reed–Solomon code, or with a fixed MR code for the current layout. On each rule change, the affected stripes are re-encoded into a code for the new layout. We will run it on the same simulated cluster, the same event traces, and the same vectorized arithmetic library. We count bytes read, bytes written, compute seconds, and time-to-compliance.

Strongest static design. The strongest competitor is the best existing MR construction for the current layout, which keeps the field as small as the literature allows. The file reports reference points:

No reported result was found on Lacuna for measured encoding throughput or re-encoding traffic of any of these codes. We will therefore measure both ourselves under identical implementation effort.

To beat this baseline, a mother code must do two things at a realistic event rate. It must stay within one symbol-width class of the static code, for example remaining at 16-bit symbols. And it must cut the total bytes moved per jurisdiction-scoped rule change by at least an order of magnitude, with lower time-to-compliance.

Over-provisioning. The third baseline stores the final layout's extra parities from day one. This isolates what "compute later" buys over "store now."

Ablation. The key ingredient is simultaneous maximal recoverability across the whole family $\mathcal T$. The ablation computes upgrade parities with a code that is MR for the start and target layouts separately, but not built jointly. We then count, by exhaustive check at small parameters, how many correctable patterns it loses after upgrade. If none are lost, the joint design is unnecessary and we will say so.

Why not just…?

Why not just re-encode when the rule changes? For systematic codes, which store the raw data pieces unchanged alongside the parity, re-encoding leaves data in place and rewrites only parity. So for changes that must touch every stripe anyway, a mother code saves write traffic but not reads, and the win is modest. We accept this. The claimed advantage is confined to jurisdiction-scoped changes. There, an upgrade reads roughly $r$ symbols per affected group, while re-encoding a globally mixed code reads roughly $k$ per stripe and rewrites all $h$ global parities. The simulator reports both regimes separately so the boundary is visible.

Why not just store the extra parities now? Over-provisioning is the most serious threat, because it needs no new theory. Its cost is permanent storage overhead for rules that may never pass. Khan et al.'s data show that most introduced bills do not reach enactment, and every change a rule might demand across six divergent jurisdictions would have to be pre-paid. The expected-cost comparison decides this directly. If event rates are high and the family $\mathcal T$ is small, over-provisioning should win, and we will report the crossover rather than hide it.

Why not just place standard LRC groups along jurisdiction borders and replicate regulated data locally? Placement alone solves residency of repair for single failures, and replication solves everything at 200–300% storage overhead. Neither is enough when a rule demands tolerance of multiple failures within a jurisdiction at erasure-code overhead. Neither survives borders that move after data is written. The ablation tests whether border-aligned placement with an ordinary non-MR code loses correctable patterns after a split, and it quantifies how many.

Proposed Experiments

Theory checks. We will tabulate the minimal field sizes for $q_{\mathrm{MR}}(T)$ and $q^*(\mathcal T)$ by exhaustive search at small parameters ($n\le 24$, $h\le 3$, $a\le 2$). Every MR claim will be checked by full rank enumeration, and by the max-flow test where it applies. The first decisive check is whether puncturing preserves maximal recoverability in all enumerated cases. A single counterexample would redirect the program. The second is whether some group-split family provably needs a larger field than its hardest single layout.

Systems checks. We will measure encoding throughput in GB/s at 8-, 16- and 32-bit symbols. This tests whether the "field-size cliff" assumed throughout the coding literature actually appears on current CPUs. We will also replay event traces with rates swept over two orders of magnitude around the LegiScan-derived fit. For each trace we report bytes moved, compute, time-to-compliance, and storage overhead against the three baselines.

Decision criteria. The proposal succeeds if two things hold. First, mother codes for realistic families stay at the static code's symbol width. Second, they dominate re-encoding and over-provisioning over a stated band of event rates. It fails informatively if a 16-bit mother code cannot cover even the one-split families. In that case the result is a lower bound telling regulators and operators that border-moving rules carry a measurable computational price. The price is paid in field size or in re-encoding, and it can be stated in advance.