On the stability of two-chunk file-sharing systems

DOI10.1007/S11134-011-9209-2MaRDI QIDQ543548zbMATH OpenOpenAlexFDO

Authors Ilkka Norros, Hannu Reittu, Timo Eirola

Publication date 17 June 2011

Published in Queueing Systems (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0910.5577

zbMATH Keywords

file-sharingqueueing networksstabilityurn model

Mathematics Subject Classification ID

Stability of solutions to ordinary differential equations (34D20) Continuous-time Markov processes on discrete state spaces (60J27) Queueing theory (aspects of probability theory) (60K25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Communication networks in operations research (90B18)

Abstract: We consider five different peer-to-peer file sharing systems with two chunks, with the aim of finding chunk selection algorithms that have provably stable performance with any input rate and assuming non-altruistic peers who leave the system immediately after downloading the second chunk. We show that many algorithms that first looked promising lead to unstable or oscillating behavior. However, we end up with a system with desirable properties. Most of our rigorous results concern the corresponding deterministic large system limits, but in two simplest cases we provide proofs for the stochastic systems also.

Review text

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.

Recommendations

• A scheme of resource allocation and stability for peer-to-peer file-sharing networks
• On the Stability of a Distributed Network
• Optimal File Sharing in Distributed Networks
• A stability conjecture on bandwidth sharing networks
• On the global stability of a peer-to-peer network model
• Coupling from the Past in Hybrid Models for File Sharing Peer to Peer Systems
• Stability of a Subcritical Fluid Model for Fair Bandwidth Sharing with General File Size Distributions
• Network Stability Under Alpha Fair Bandwidth Allocation With General File Size Distribution

Cites work

• A simple urn model
• A survey of random processes with reinforcement
• Bernard Friedman's Urn
• Elements of applied bifurcation theory
• scientific article; zbMATH DE number 3729228 (Why is no real title available?)
• scientific article; zbMATH DE number 3766528 (Why is no real title available?)
• On positive Harris recurrence of multiclass queueing networks: A unified approach via fluid limit models
• The Missing Piece Syndrome in Peer-to-Peer Communication

Cited in

(12)

• Stability of a peer-to-peer communication system
• Interacting branching processes and linear file-sharing networks
• Choking/Unchoking mechanism in the ShareStorm protocol
• Coupling from the Past in Hybrid Models for File Sharing Peer to Peer Systems
• A Stochastic Epidemiological Model and a Deterministic Limit for BitTorrent-Like Peer-to-Peer File-Sharing Networks
• On the global stability of a peer-to-peer network model
• Probing high-capacity peers to reduce download times in P2P file sharing systems with stochastic service capacities
• The Missing Piece Syndrome in Peer-to-Peer Communication
• Stable and scalable universal swarms
• Dynamic model of growing file-sharing P2P network
• Overlay architectures for file distribution: Fundamental performance analysis for homogeneous and heterogeneous cases
• Stable and scalable universal swarms

This page was built for publication: On the stability of two-chunk file-sharing systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q543548)