Positive Recurrence of the Two-Chunk Deterministic First Chunk System: A Stable Population Process with an Unstable Large System Limit

In Oberwolfach Report 48/2010, I. Norros (joint work with H. Reittu) considered the two-chunk Deterministic First Chunk (DFC) file-sharing system of Norros, Reittu and Eirola, in which one permanent seed holds both chunks and arriving peers choose by a fair coin the chunk they download first. The large system limit of this population process is not stable, but the stochastic system was conjectured, on simulation evidence, to be stable; if so, instability of a population process cannot be inferred from instability of its large system limit. We prove the conjecture for the chain defined in Fig. 2 of arXiv:0910.5577v1, whose contact population consists of the seed and the peers holding one chunk: for every arrival rate \(\lambda>0\) this chain on \(\mathbb{N}^4\) is irreducible, non-explosive and positive recurrent. Hence DFC is a stable population process whose large system limit is not stable; the theorem also refutes Conjecture 3.4 of arXiv:0910.5577v1 (instability for large \(\lambda\)). The proof is an explicit Foster–Lyapunov function with drift at most \(-\frac12\) outside an explicit finite set; the constants are crude. The mechanism is an exact identity: the difference \(Q\) between the two classes of peers has drift \((X-Y)/(X+Y+1)\), a term of order one that comes from the seed alone; it vanishes in the large system scaling, where \(Q\) becomes a first integral. The model, its large system limit and the instability of the limit are due to Norros, Reittu and Eirola, the question to Norros and Reittu. The variant in which empty peers are contacted as well (contact population \(A+B+X+Y+1\)) is not covered and remains open. This is an unrefereed note.