All-load stability of a deterministic-first-chunk file-sharing chain

Abstract

We prove positive recurrence at every fixed positive arrival rate for the four-population deterministic-first-chunk chain described by Norros, Reittu and Eirola. This answers the stability conjecture in Norros's 2010 Oberwolfach contribution and the retained 2011 author proof, for the exact six-rate model with a permanent seed and invisible empty waiting rooms. A single coercive Foster function combines remaining workload, rounded cohort imbalance, and two bounded finite birth–death Poisson correctors. Monotone ratio cutoffs make every first-download interface error nonpositive. The other interface errors are controlled pointwise. The proof requires no stationary averaging, moment assumption, or uniformity in the arrival rate. Exact finite controls supplement the analytic proof. The contribution is the all-load extension of the stated historical conjecture; classical methods and source-version limits are explicit.

The idea in plain English

Imagine a file split into two pieces. Each arriving participant independently chooses at random which piece to fetch first and keeps that first choice. Participants leave as soon as both pieces are obtained, while one permanent seed always has both pieces.

The paper proves stability for a particular continuous-time random model at every fixed positive arrival rate. Stability here means positive recurrence and a unique stationary probability distribution. It does not imply a bound on average population or download time.

The exact model matters: empty participants are excluded from the contact denominator, and the permanent seed has no separate aggregate upload cap. Many empty participants can contact it at once. This result is not a stability theorem for a capped-seed model.

The associated large-system differential equations can have trajectories growing without bound. For this model, that behavior does not force instability of the random chain. The paper extends the elementary small-load argument to every fixed positive load.

The precise result

For every fixed real λ>0, Theorem 1 states that the continuous-time chain on N₀⁴ is nonexplosive, irreducible and positive recurrent, and therefore has a unique stationary probability distribution. The conclusion covers every finite initial state.

The state (a,b,x,y) records empty participants assigned to each first-chunk choice and participants holding only each respective chunk. With D=x+y+1, the two arrivals have rate λ/2, the first downloads have rates a(x+1)/D and b(y+1)/D, and departures have rates x(y+1)/D and y(x+1)/D. A transition decrementing a zero coordinate has rate zero.

The seed contributes the +1 terms. The empty populations a and b do not enter D, and these rates allow unbounded aggregate seed upload as the waiting populations grow. The theorem applies to this literal generator.

Why the result holds

The proof combines the amount of unfinished downloading with a smoothed measure of imbalance between the two participant groups. Two bounded corrections handle states in which one piece is scarce.

The corrections are activated by monotone cutoffs. The first-download transitions change those cutoffs in a favorable direction; the remaining changes are bounded explicitly. One global function then has negative expected drift outside a finite set.

The argument uses localized stopping times and a finite-mean return cycle to obtain recurrence. It does not assume in advance that a stationary distribution or a stationary population moment exists.

Scope and limitations

The model has exactly two chunks, one permanent seed, independently uniform fixed first choices, immediate departure on completion and empty waiting rooms excluded from the contact denominator. It does not cover arbitrary file-sharing software or other chunk-selection rules.

The six rates impose no fixed aggregate seed-capacity bound. This is not a solution for a capped-seed or finite-bandwidth missing-piece model.

The arrival rate is fixed and strictly positive, and the proof constants can depend on it. No bound uniform in λ, stationary population moment, completion-time estimate, convergence rate or geometric ergodicity is established. At λ=0 the zero state is absorbing and the stated irreducibility conclusion does not apply.

The historical target is the 2010 Oberwolfach stability conjecture and the retained 2011 author-proof model. The 2009 preprint conjectured high-load instability instead. These source versions must be distinguished.

The classical Foster–Lyapunov method and finite birth–death Poisson equation are prior tools. The paper claims the all-load pointwise certificate for this model, and does not certify worldwide priority or continued openness.

Status and AI use

AI tools were used extensively in research, proof development, literature comparison, computation, manuscript preparation and adversarial auditing. Internal AI review does not constitute formal independent human peer review or proof-assistant certification.

The manuscript and Zenodo publication-date metadata are dated 20 October 2026. Zenodo records this version as created on 21 October 2026 (UTC). The displayed date is the manuscript date, not verified public availability on that date. Neither date establishes first priority. Version 1.0 is the Zenodo version; the manuscript does not print a version number.

Read the paper

Open PDF in a full window · Download the original from Zenodo

Collaborate on this result

I welcome substantive collaboration from researchers in stochastic processes, queueing theory and distributed systems, especially on checking the recurrence argument, placing it precisely in the file-sharing literature, and developing a journal-ready treatment. Any coauthorship would reflect a substantive contribution to the research.

Authorship and responsibilities would be discussed in relation to the substantive contributions made.

Cite this paper

Alec Kriebel. (2026). All-load stability of a deterministic-first-chunk file-sharing chain (Zenodo version 1.0) [Preprint]. Zenodo. https://doi.org/10.5281/zenodo.23524971

Download BibTeX

Background and prior work

• Norros — On the stability of population processes: Printed pages 2782–2783 state the deterministic-first-chunk stability conjecture despite instability of the large-system differential equations.
• Norros, Reittu and Eirola — On the stability of two-chunk file-sharing systems: Section 3.2, Figure 2 and Conjecture 3.6 of the retained January 5, 2011 author proof specify the model, including invisible empty waiting rooms, and conjecture stability.
• Norros, Reittu and Eirola — 2009 preprint: Figure 2 supplies the same transition rates, but this earlier version conjectures high-load instability. It must be distinguished from the later source.
• Meyn and Tweedie — Stability of Markovian processes III: Classical continuous-time Foster–Lyapunov criteria and localized Dynkin arguments provide the background stability method.
• Oguz, Anantharam and Norros — Stable, distributed P2P protocols based on random peer sampling: The Common Chunk protocol is a different all-load stable scheme: it samples the entire population and protects rare chunks before departure. Its theorem is not the DFC result.