# CodingSets probability: count failed nodes once

**A formula based on independent minimal failure subsets is not an exact
probability for a uniformly chosen fixed-size set of failed nodes.** In a
six-node example it gives 78.4% when every three-node failure makes a codeword
unavailable. In a constructed 1,000-node configuration it instead overestimates.
It is therefore neither a universal upper nor lower bound.

This is an original worked mathematical audit, not a newly discovered theorem,
an observed failure rate, or a replication of Hydra's experiments. It extends
Hesela's [CodingSets entry](https://hesela.dev/terms/codingsets/) and its existing
event-frequency/conditional-size example. No extra glossary entity is needed.

## The question and the primary sources

[Hydra, section 5](https://www.usenix.org/system/files/fast22-lee.pdf) first counts
dangerous subsets of exactly r+1 nodes, then uses a power expression for larger
failure sets. Section 7.2.1 reports calculated probabilities, separately from
the deployment experiment. [Copysets, section 4.3](https://files.usenix.org/s3fs-public/cdn/atc13-cidon.pdf)
separates event frequency from expected loss magnitude. Neither distinction
makes overlapping failure subsets independent.

We transcribed the Hydra expression from printed p. 187, visually checking
the exponent. It has the form A = 1 - (1 - q)^C(f,r+1), where f here is an
**integer failed-node count**, not the paper's percentage notation. The source
metadata and PDF hashes are in [sources.json](sources.json).

## Explicit population and event

There are G node-disjoint groups with sizes s_1,...,s_G, totaling N nodes.
Select exactly f distinct failed nodes uniformly from all C(N,f) subsets.
A group is bad if it contains at least r+1 failed nodes.

For l=0, each group holds at least one fully written ideal k-of-(k+r) codeword,
with s_i=k+r and one valid fragment per node. A bad group then means at least
one codeword is unavailable. A currently unavailable codeword need not be
permanently lost.

The denominator is C(N,f), not an annual observation count. This conditional
failure population does not model event frequency, repair, rack topology,
silent corruption, asynchronous writes, stale fragments or service downtime.
The paper's looser copyset-disjoint groups can overlap by up to r nodes.
Our exact occupancy formula does **not** apply to those overlapping groups.

## Exact calculation

Each group contributes a polynomial that counts safe choices within it:

```text
B_i(x) = sum(j=0..r) C(s_i,j) x^j
safe = coefficient of x^f in product_i B_i(x)
P(any bad group | exactly f failures) = 1 - safe / C(N,f)
```

This follows by multiplying the number of ways to choose j failures per group,
then summing only combinations with total f. The program uses integer
coefficients and exact rational output. No Monte Carlo uncertainty is present.

Let D = sum_i C(s_i,r+1), q = D/C(N,r+1), and M=C(f,r+1).
When f=r+1, q is exact: each failure set is itself one minimal subset.
For larger f, the same failed nodes participate in multiple minimal subsets.

Linearity of expectation gives **E[number of dangerous minimal subsets] = Mq**,
without assuming independence. Markov's inequality gives the valid bound
P(any bad group) <= min(1,Mq). Replacing this union probability with
1-(1-q)^M instead acts as if the M checks were independent. That step is what
the counterexamples test.

## Checked results

All percentages below are conditional on the stated number of failed nodes.
Values are rounded for reading; [results.json](results.json) retains integer
counts, rational probabilities and 50-digit decimal comparisons.

| Groups; parity r | Failed nodes | Exact probability | Power expression | Difference, percentage points |
|---|---:|---:|---:|---:|
| 2 groups of 3; r=1 | 2 | 40.0000% | 40.0000% | 0 |
| 2 groups of 3; r=1 | 3 | 100.0000% | 78.4000% | -21.6000 |
| 3 groups of 3; r=1 | 3 | 67.8571% | 57.8125% | -10.0446 |
| 100 groups of 10; r=2 | 10 | 0.8341% | 0.8629% | +0.0288 |
| 100 groups of 10; r=2 | 20 | 7.3510% | 7.9032% | +0.5521 |
| 100 groups of 10; r=2 | 40 | 46.3191% | 51.0086% | +4.6895 |

The six-node proof needs no program. With three failures distributed between
two groups, at least one group receives two. All 20 possible failure sets are
bad. Yet q=6/15 and M=3, so the power expression is 1-(3/5)^3=98/125.

The 1,000-node rows use k=8, r=2, **l=0** and 100 complete groups.
They are not Figure 15's l=2 baseline. For example, the 10-failure discrepancy
is about 0.029 percentage points, not 2.9 percentage points. The small
counterexample establishes non-exactness, not that a paper's practical ranking
must reverse.

## Extended groups need actual placement coverage

With l>0 a codeword occupies only k+r nodes of a larger group. A group having
r+1 failures is necessary for any of its stripes to fail, but may not suffice.

For example, a 2+1 stripe occupies {0,1,2} in extended group {0,1,2,3}.
Failures {0,3} exceed r=1 at group level, but leave the stripe's two required
fragments on {1,2}. Counting every minimal subset as dangerous assumes that
actual stored codewords cover it. Load balancing alone does not establish
this finite-workload coverage.

The additional JSON rows with 83 groups of 12 use N=996, not a silently rounded
1,000-node partition. Their exact values are **group-threshold envelope**
probabilities, not exact codeword-loss probabilities without coverage evidence.
The generic unequal-size row checks arithmetic support; it does not prescribe
a CodingSets remainder policy.

## Reproduce and verify

Python 3.12 standard library and Node 24 are sufficient; no package installation,
network access, storage devices or root privileges are required.

```sh
cd content/research/codingsets-occupancy
python3 occupancy.py --check
python3 -m unittest discover -s . -p 'test_*.py' -v
python3 -O -m unittest discover -s . -p 'test_*.py' -v
node oracle.mjs
python3 verify.py
```

Use `python3 occupancy.py --write` only to deliberately regenerate results.
The tests compare 2,079 integer counts with literal enumeration over every
group-size partition through ten nodes and every valid r and f: 110,534 subset
classifications. A separate JavaScript BigInt implementation uses
inclusion-exclusion over bad-group events, checking all 17 homogeneous rows;
its direct bitmask enumeration also checks all five small rows. This is
independent code and arithmetic, **not independent human peer review**.

The acceptance record binds results, code and synthesis by hashes. It records
runtime versions, commands and exit statuses. The work remains review material;
there are no changes to public site pages or their current claims.

## Integration decision

Keep the existing six-node topology study intact. Add one compact qualification
to the existing CodingSets note after technical review, linking this exact
calculation. No new article, universal reliability estimate or performance
claim is justified by this work. See [INTEGRATION.md](INTEGRATION.md).
