On the stability of two-chunk file-sharing systems (Q543548)

The paper considers five different peer-to-peer file-sharing systems with two chunks, assuming non-altruistic peers who leave the system immediately after downloading the second chunk. The aim is to find chunk selection algorithms that have a provably stable performance with any input rate. It is shown that many algorithms that first looked promising lead to unstable or oscillating behaviour. However, the paper ends up with a system with desirable properties. Most of the rigorous results concern the corresponding deterministic large system limits, but, in the two simplest cases, the paper provides proofs for stochastic systems also. The paper analyses the following: (i) the plain random contact system, which is found to be unstable; (ii) the deterministic first chunk system, found to be very unsatisfactory in the present scenario; (iii) the ideal Friedman system, which is proven to be stable; and two distributed algorithms that try to emulate the Friedman system: (iv) the delayed Friedman system, which may be stable but oscillate heavily; and (v) the enforced Friedman system which seems to provide the desired performance.