We consider the video-on-demand streaming problem in a P2P network in a decentralized model, in which peers have no global information about the network. Assuming that only one server has all the chunks, the objective is to stream all chunks to all peers in the network such that small latency and good fluency are achieved by all peers.
We design a simple and decentralized protocol in which each peer maintains a constant number of neighbors and only need to communicate with one of them chosen uniformly at random every time. Moreover, the maximum number of communications established on each peer every time is also constant. We provide theoretical and experimental analysis to show that almost all peers achieve optimal latency and fluency under our protocol.