# Verification report — OWR-4530-006 (Norros–Reittu: stability of the two-chunk Deterministic First Chunk system)

Verification date: 2026-10-20.

**Verdict.** The note gives a **complete answer** to the question of the record, for the chain that the source
defines.
- **Proved.** For every λ > 0 the Deterministic First Chunk (DFC) chain of Norros–Reittu–Eirola,
  arXiv:0910.5577v1, Fig. 2 (state (A, B, X, Y) ∈ N⁴; contact population X + Y + 1) is irreducible, non-explosive
  and positive recurrent (Theorem 1.1), by an explicit Foster–Lyapunov function with L V ≤ −1/2 outside an explicit
  finite set.
- **Hence** (Corollary 1.2): DFC is a population process whose large system limit (eq. (5) of the source, (2) of the
  note) is not stable while the process is stable for every λ; instability of a population process does not follow
  from instability of its large system limit. This confirms the conjecture of the Oberwolfach abstract and refutes
  Conjecture 3.4 of arXiv:0910.5577v1 (instability for large λ).
- **Known, not claimed.** The model, the limit (2), its instability (Prop. 3.3), the notion of stability and the
  finite-set criterion, the remark that λ scales the limit but not the chain, and Conjecture 3.4 are due to Norros,
  Reittu and Eirola; the question and the stability conjecture to Norros and Reittu. The Foster–Lyapunov method is
  standard (Meyn–Tweedie 1993); the form used is proved in the note (Lemma 3.2).
- **Not covered.** The variant suggested by the verbal wording of the Oberwolfach abstract, in which empty peers are
  also contacted (contact population A + B + X + Y + 1), is a different chain; it is named as open. Also not
  treated: the other two-chunk systems, more chunks, the example in the opposite direction, the stationary law.
- **Constants.** Crude (X1 = ⌈2⁵⁰Λ⁴⌉, K astronomically large); the finite set F is not meant to be sharp.

The note is unrefereed.

## Statement checked
- **Record.** OWR-4530-006, dataset v1.8.0 label "open" (literature note: only the instability of the large
  system limit is proved). It asks to prove or disprove the stability conjecture for the two-chunk DFC population
  process and hence to decide whether instability of a population process can fail to follow from instability of its
  large system limit.
- **Primary source.** I. Norros (joint with H. Reittu), "On the stability of population processes", Oberwolfach
  Report 48/2010, Mathematical Challenges in Stochastic Networks, Oberwolfach Rep. 7 (2010), no. 4, pp. 2745–2812
  (issued 2011 per Crossref), DOI 10.4171/OWR/2010/48; the abstract is on pp. 2782–2783 and was read in full in the
  open PDF of the report. It describes the DFC system, says that its large system limit is unstable and that the
  stochastic system "is conjectured, by simulation evidence, to be stable", and draws the consequence about
  population processes. It cites arXiv:0910.5577 for the models.
- **Model source.** I. Norros, H. Reittu, T. Eirola, "On the stability of two-chunk file-sharing systems",
  arXiv:0910.5577v1 (29 October 2009), read in full; published in Queueing Systems 67 (2011), no. 3, 183–206,
  DOI 10.1007/s11134-011-9209-2. Fig. 2 gives the rates of Table 1 of the note (A → X at A(X+1)/(X+Y+1), B → Y at
  B(Y+1)/(X+Y+1), X leaves at X(Y+1)/(X+Y+1), Y leaves at (X+1)Y/(X+Y+1), arrivals λ/2 to A and to B); eq. (5) is
  the large system limit; Sec. 2 defines stability (irreducible and positive recurrent) and recalls the finite-set
  criterion; Prop. 3.3 gives the unbounded equilibrium curve and an open set of escaping trajectories; Conjecture
  3.4 predicts instability for large λ; the remark after Prop. 3.1 says that λ is a pure scaling parameter of the
  limits but that stability of the stochastic system may depend on λ.
- **Reading.** The theorem is about the Fig. 2 chain, the chain to which the record's "large-system limit" refers.
  The wording "a randomly selected peer (seed included)" of the abstract also fits a chain with contact population
  A + B + X + Y + 1; its large system limit is also unstable in the same sense (first integral (b+y) − (a+x),
  unbounded curve a = y, b = x, xy = λ(x + y), y > λ), so the scope restriction matters, and the note states it in
  the abstract, the introduction, Section 6 and "Scope and priority".

## Readings
- arXiv:0910.5577v1: in full (both verification runs and the writing stage); Secs. 1, 2, 3.1–3.3 again in
  verification run 2.
- Oberwolfach Report 48/2010: Norros's abstract (pp. 2782–2783) and Hajek's abstract (pp. 2760–2764; its reference
  list ends on p. 2764; the theorem used is on pp. 2762–2763), open PDF.
- Published version (Queueing Syst. 67): only the abstract, on the Springer article page as served to one anonymous
  request on 2026-10-19, 22:26 UTC (the other anonymous requests, on 2026-10-19 and 2026-10-20, returned a 3 kB
  automated-access page); it says that proofs for the
  stochastic systems are given only "in the two simplest cases", i.e. Plain Random Contact (Prop. 3.2) and Friedman
  (Prop. 3.6) in v1. The zbMATH review Zbl 1225.60145 (O. K. Zakusilo) describes DFC as "very unsatisfactory in the
  present scenario" where v1 says "found unstable". The full text was not read; whether Conjecture 3.4 was kept is
  unknown. A HAL record (hal-00781341, document type ART, with a file) exists; the file request returned an
  automated-access check and was not pursued.
- Meyn–Tweedie (1993), Adv. Appl. Probab. 25(3) 518–548, DOI 10.2307/1427522: abstract only (Crossref).
- Hajek–Zhu, Stochastic Systems 1(2) (2011) 246–273, DOI 10.1214/10-SSY017: not read; described from Hajek's abstract.
- Oguz–Anantharam–Norros, IEEE/ACM Trans. Netw. 23(5) (2015) 1444–1456, DOI 10.1109/TNET.2014.2331352: title and
  the passages of its preprints that cite the source, as shown by Semantic Scholar.
- Fogelklou–Konstantopoulos–Tucker, Oper. Res. Lett. 40(3) (2012) 190–194, DOI 10.1016/j.orl.2012.02.002: title only
  (no abstract in Crossref, OpenAlex, Semantic Scholar or zbMATH).
- Not read: the theses of Reittu, Oguz (2012) and Fogelklou (2012).
- All bibliographic data with a DOI were checked with Crossref (six DOIs; the two Oberwolfach abstracts share one).

## Results in the paper
- Lemma 2.1: L Q = (X − Y)/D, L N = λ − T, T = (2XY + X + Y)/D. Lemma 2.2: q = (b + y) − (a + x) is a first integral
  of (2); equilibrium curve; (2) not stable. Remark 2.3: L(Y − X) = (1 − λ)(X − Y)/D (Plain Random Contact) and
  (1 + λ)(X − Y)/D (Friedman), consistent with Props. 3.2 and 3.6 of the source.
- Lemma 3.1: irreducibility; total rate ≤ λ + n on {N ≤ n} and non-explosion; min(X,Y) ≤ T < 2 min(X,Y) + 1;
  symmetry σ(A,B,X,Y) = (B,A,Y,X). Lemma 3.2: the Foster–Lyapunov criterion in the form used, with proof.
- Section 4: parameters (3) in Λ = max(λ, 1); V = h(Q) + δN + η(A+B) − κ[g(Y)w(Q) + g(X)w(−Q)] (Huber h,
  g(z) = Mz/(M+z), ramp w); Lemma 4.1 (symmetry, lower bound, jump bound J, closed form of γ); Lemma 4.2 (master
  inequality (6)); Lemma 4.3 (γ bounds (g1)–(g3)).
- Section 5: Proposition 5.1 (interior, L V ≤ 1.8 − δ min(X,Y)/2 ≤ −4094), Proposition 5.2 (face, L V ≤ −0.7,
  cases F1(a)–(c), F2), Proposition 5.3 (corner, L V ≤ (λ + 2M0)J − η(A+B)/(X1 + M0)); proof of Theorem 1.1.

## Computations (sanity checks; programs and outputs in reproducibility/)
- `check_note.py` (the exact program of the note; standard library; about 20 s): TOTAL FAILS 0. It checks the
  identities exhaustively on small states and on large random states, the polynomial identities on grids that prove
  them, every numerical constant of Sections 4–5 (also the Λ-free bounds e1 ≤ 7.7·10⁻⁶, e2 ≤ 10⁻²⁰,
  e3 ≤ 3.9·10⁻⁶, e4 ≤ 5.8·10⁻⁶ and their total ≤ 0.001), and exact L V on 10,000 random states and a face sweep for
  each of λ = 1/10, 1, 37/10, 10, 100. Worst face values −1.1, −0.875, −0.7838, −0.7625, −0.7512.
- `original/check_drift.py` (first stage): TOTAL FAILS 0, the same worst face values.
- Simulations with recorded seeds (`run_sims.sh`, `sim_output_seeded.txt`): time-averaged N over [0, 2·10⁵] about
  4.48–4.51, 33.3–33.8, 154–157, 1173–1208, 11939–13064 for λ = 1, 4, 10, 30, 100 (seeds 1, 2, 7); from
  (5, 20000, 40000, 0) with λ = 10: Q = −20005 → −10072 at t = 10⁴, N peaks at about 1.0·10⁵, N = 3368 at t = 2·10⁴
  and 188 at t = 3·10⁴ (seed 3). Seeds 1, 2, 3 reproduce the saved first-stage output line by line. Illustration
  only.

## Independent verification runs
Two independent verification runs, both AI-assisted, examined the first written version of the proof (2026-10-20);
each re-derived it line by line and wrote its own exact programs; neither read the other's report.

| Item | Run A | Run B |
|---|---|---|
| Reading of the question; rates of Fig. 2; (5); Prop. 3.3; Conj. 3.4; definition of stability | CONFIRMED | CONFIRMED |
| Lemma 2.1, bounds (T), irreducibility, non-explosion | CONFIRMED (rate bound λ + n suggested) | CONFIRMED (wording of the X ≥ Y step) |
| Master inequality (*) | CONFIRMED; own transcription tested exactly | CONFIRMED; exact, min slack 1.6·10⁻⁴ |
| γ bounds (g1)–(g3) | CONFIRMED (also with sympy) | CONFIRMED |
| Interior, face (F1 a–c, F2), corner | CONFIRMED; nine λ in [0.01, 1000] | CONFIRMED; eight λ in [0.01, 1000], up to 3,539,160 face states for one λ |
| Foster/Dynkin step and coverage | CONFIRMED | CONFIRMED |
| Corollary (the "hence" part) | CONFIRMED | CONFIRMED |
| Other tests | consistency with Props. 3.2, 3.6; large system limit of the variant | re-run of the first programs (identical); adversarial hill-climb (no state outside F with L V > −1/2); 8 of 9 mutation tests detected; truncated stationary law E N ≈ 4.494 (λ = 1) |
| Literature | arXiv, zbMATH, one web search; no prior proof | arXiv, zbMATH, Crossref, Semantic Scholar (29 citing works), two web searches; published abstract and zbMATH review; no prior proof |
| Overall | CONFIRMED (PROVED), cosmetic fixes | CONFIRMED (PROVED), non-mathematical fixes |

**Corrections required by the runs**, all applied:
1. (A) Hajek's abstract begins on p. 2760 (not 2759): reference [Haj10] and the text. (Verification run 2 found that
   it ends on p. 2764, not 2763; corrected, see below.)
2. (A) The refuted conjecture is called Conjecture 3.4 of arXiv:0910.5577v1 wherever the refutation is stated
   (abstract, Sections 1.1, 1.2, 7), with the remark that the published abstract suggests but does not prove that it
   was kept.
3. (A) Rate bound λ + n on {N ≤ n} (r3 ≤ A, r4 ≤ B, r5 ≤ X, r6 ≤ Y): Lemma 3.1(b).
4. (A) Remark that the variant with contact population A + B + X + Y + 1 also has an unstable limit, and that the
   proof does not cover it: Section 6.
5. (B) Published abstract and zbMATH review cited; the published full text stated as not read: Sections 1.2, 7.
6. (B) Seeds recorded: re-runs with seeds printed on every line (`sim_output_seeded.txt`); seeds 1, 2, 3 reproduce
   the saved runs.
7. (B, wording) Lemma 3.1(c): the step 2X + 1 ≥ D uses X ≥ Y; remark on crude constants and the non-sharp set F
   (Sections 1.4, 6); the A + B + X + Y + 1 variant only as an open question (run B's tests of the same V on the
   variant are not used).

**Changed when the note was written.** In case F2 the first version stated the constant −0.718; the estimate gives
−1 + 1/4 + 1/32 + 0.001 = −0.71775, now stated as −0.7177. The final bound L V ≤ −0.7 is unchanged, and
`check_note.py` checks the constant. The proof was reorganised into lemmas and propositions, and the Foster step was
written out as Lemma 3.2 with a complete proof (both runs had checked it in the shorter form "Dynkin plus
non-explosion plus finite return time to F"); the non-explosion argument uses Dynkin's formula for N on the stopped
chain.

## Independent verification run 2 (on the text of the note)
A further independent verification run, also AI-assisted, examined the text of the note itself on 2026-10-20
(runs A and B had examined the first written version). Programs and outputs: `reproducibility/independent_run_2/`.

- **Sources.** It read Norros's abstract (pp. 2782–2783) and Hajek's abstract in the open PDF of the report, and
  Sections 1, 2 and 3.1–3.3 of arXiv:0910.5577v1 again, and checked the six DOIs with Crossref and the zbMATH review.
  The question is answered as posed for the Fig. 2 chain; the scope (contact population X + Y + 1; the
  A + B + X + Y + 1 variant open, with no claim from simulations), the attribution of the refuted conjecture to
  Conjecture 3.4 of arXiv:0910.5577v1 and the statement that the published full text was not read are correct.
- **Proofs.** It re-derived, line by line, Lemmas 2.1, 2.2, 3.1, 3.2, 4.1–4.3, Propositions 5.1–5.3, the coverage of
  N⁴ and the Foster step; in particular the rates against Fig. 2 and (5), the joint moves of (Y, Q) under r6 and of
  (X, Q) under r5 in the master inequality, the signs of the dropped ramp terms, the γ bounds for real M ≥ 32, and
  the parameter arithmetic uniformly in Λ ≥ 1 (Λ-free: e1 ≤ 7.63·10⁻⁶, e3 ≤ 3.82·10⁻⁶, e4 ≤ 5.73·10⁻⁶, total of
  (7) ≤ 1.54·10⁻⁴). It found no mathematical error and no gap. The reduction of the face sweeps to min(A, B) = 0 is
  justified by an exact identity: for fixed Q, X, Y, L V is affine in min(A, B) with slope
  (X+1)/D·(−η − κΔ⁺g(X)w̄(Q)) + (Y+1)/D·(−η − κΔ⁺g(Y)w(Q)) < 0.
- **Computations** (own exact programs, written from the definitions in the note): generator identities; the
  master inequality (6) transition by transition against the exact generator (minimal slack 7.8·10⁻⁵); the γ
  bounds and all constants; interior, face and corner bounds for λ ∈ {1/100, 1/10, 1, 37/10, 10, 100, 1000} (face:
  X ∈ {X1, X1+1, 2X1+7}, all Y ≤ 4M+2 (stride 3 with dense windows for λ = 1000) and values up to M0 − 1, 18 values
  of Q including −L′−L, −L′−L+1, −L′, −L′+1, 0, L′, L′+L, −(X−Y) and far values, both mirror faces; up to 4.66
  million states; corner: A + B ∈ {K, K+1, 3K}); symbolic checks with sympy. TOTAL FAILS 0. Worst face values
  −1.1225, −1.1, −0.875, −0.78378, −0.7625, −0.75125, −0.750125 (the recorded −1.1, −0.875, −0.784, −0.763, −0.751
  agree). Mutation tests κ = 1, κ = 0 and "no seed in the departure rates" produce face states outside F with
  L V > −1/2 (worst +0.2365, +1.233, +0.25), so the tests are not vacuous.
- **Re-run of this package** from an extracted copy of the source archive: `check_note.py`, `run_sims.sh` and
  `original/check_drift.py 20000` give outputs identical to the recorded ones.
- **Literature.** arXiv API, Crossref, zbMATH, OpenAlex (all 31 citing titles) and one web search: no printed
  answer.
- **Corrections required, all applied (none mathematical):** Hajek's page range (pp. 2760–2764; theorem on
  pp. 2762–2763); the description of [FKT12] reduced to what was read (the title); in Section 1.3, the first
  integral does not imply the curve of equilibria (now: all equilibria lie on {q = 0}, so no trajectory with q ≠ 0
  converges to an equilibrium) and the escaping trajectories of Prop. 3.3 have a and y bounded, not small; the
  simulation start (5, 20000, 40000, 0) lies on the boundary of the escaping set of the proof of Prop. 3.3 (y = 0,
  a = λ/2), and the system empties between t = 2·10⁴ and 3·10⁴; the Verification paragraph now says that runs A and
  B examined the first written version and records this run; this report's suggested status follows the dataset
  policy.

## Relation to the literature, novelty and scope
- **Searches (2026-10-19/20).** arXiv API (deterministic first/last chunk; two-chunk and stability; chunk selection
  or peer-to-peer with positive recurrence; missing piece; random peer sampling; population process and large
  system limit; au:Norros, au:Reittu), zbMATH (first chunk; two-chunk; Norros and stability), Crossref, OpenAlex
  (31 works citing the published paper; titles read on 2026-10-19 and again on 2026-10-20; other requests got
  HTTP 429), Semantic Scholar (29 citing works, citation contexts for 13), five web searches in all (one of them
  by verification run 2, which also repeated arXiv, Crossref, zbMATH and OpenAlex queries). None of the sources mentions a proof or disproof of
  positive recurrence of the stochastic DFC chain.
- **Related, different models.** Hajek–Zhu (missing piece syndrome; fixed seed upload rate U_s; positive recurrent
  if λ < U_s, transient if λ > U_s in the special case quoted in Hajek's abstract); Oguz–Anantharam–Norros (their
  two-chunk proof concerns their rare-chunk rule); Fogelklou–Konstantopoulos–Tucker (only the title was read; its
  relation to DFC is not known to us). Fluid-model
  results of multiclass queueing were not used (different scaling, not read).
- **Novelty.** No earlier proof found in the sources searched; this is a search result, not a proof of novelty;
  no priority is claimed beyond it. The likeliest places for an overlooked proof are the full text of the published
  paper and the theses of Reittu, Oguz and Fogelklou.
- **Suggested status.** Answered by an unrefereed note (analytic Foster–Lyapunov proof of positive recurrence of the
  Fig. 2 chain for every λ > 0); as the claim is unrefereed, under the dataset policy the label stays open with
  evidence unrefereed_claim. The A + B + X + Y + 1 variant, sharp constants and K-chunk versions stay open.

## Public release and license
This paper, its source files, and this verification report are licensed under the Creative Commons Attribution
4.0 International License (CC BY 4.0): https://creativecommons.org/licenses/by/4.0/