Stability of a peer-to-peer communication system

DOI10.1145/1993806.1993867zbMATH Open1321.68054arXiv1110.2753OpenAlexW2015690067MaRDI QIDQ2943409FDOQ2943409

Authors: Ji Zhu, Bruce Hajek 

Publication date: 11 September 2015

Published in: Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing (Search for Journal in Brave)

Abstract: This paper focuses on the stationary portion of file download in an unstructured peer-to-peer network, which typically follows for many hours after a flash crowd initiation. The model includes the case that peers can have some pieces at the time of arrival. The contribution of the paper is to identify how much help is needed from the seeds, either fixed seeds or peer seeds (which are peers remaining in the system after obtaining a complete collection) to stabilize the system. The dominant cause for instability is the missing piece syndrome, whereby one piece becomes very rare in the network. It is shown that stability can be achieved with only a small amount of help from peer seeds--even with very little help from a fixed seed, peers need dwell as peer seeds on average only long enough to upload one additional piece. The region of stability is insensitive to the piece selection policy. Network coding can substantially increase the region of stability in case a portion of the new peers arrive with randomly coded pieces.

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

Recommendations

• The Missing Piece Syndrome in Peer-to-Peer Communication
• On the stability of two-chunk file-sharing systems
• Topological implications of selfish neighbor selection in unstructured peer-to-peer networks
• On the global stability of a peer-to-peer network model
• Stable and scalable universal swarms

zbMATH Keywords

Markov processbranching processpeer to peerFoster-Lyapunov stabilitymissing piece syndromerandom peer contactrandom useful piece upload

Mathematics Subject Classification ID

Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Graph theory (including graph drawing) in computer science (68R10) Lyapunov and other classical stabilities (Lagrange, Poisson, (L^p, l^p), etc.) in control theory (93D05) Network design and communication in computer systems (68M10) Distributed systems (68M14) Network protocols (68M12)

Cites Work

• Title not available (Why is that?)
• Flooding time in edge-Markovian dynamic graphs
• How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
• Parsimonious flooding in dynamic graphs
• Distributed computation in dynamic networks
• Continuous consensus via common knowledge
• Reaching Agreement in the Presence of Faults
• Knowledge and common knowledge in a distributed environment
• Perfectly secure message transmission
• Programming simultaneous actions using common knowledge
• Knowledge and common knowledge in a Byzantine environment: Crash failures
• Consensus algorithms with one-bit messages
• Broadcasting in dynamic radio networks
• Opportunistic information dissemination in mobile ad-hoc networks: the profit of global synchrony
• Fault Tolerance in Networks of Bounded Degree
• Optimal gradient clock synchronization in dynamic networks
• Almost-Everywhere Secure Computation
• Gradient clock synchronization in dynamic networks

Cited In (5)

• Stability in referral systems
• The Missing Piece Syndrome in Peer-to-Peer Communication
• On the global stability of a peer-to-peer network model
• Impact of availability in P2P file sharing system caused by active peers
• Probing high-capacity peers to reduce download times in P2P file sharing systems with stochastic service capacities

This page was built for publication: Stability of a peer-to-peer communication system

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