Optimal Delay-Reconstruction Tradeoffs in Peer-to-Peer Networks

We study the tradeoff between delay and partial reconstruction in peer-to-peer networks, i.e., the number of messages a peer must obtain to reconstruct a given fraction of the file. We present a coding scheme based on erasure compression and Slepian-Wolf binning, in which peers generate coded messages based on their current knowledge of the file. Assuming symmetric peers, we show that the coding scheme provides a Pareto optimal tradeoff between delay and reconstruction, which we characterize. In the process of proving the result, we establish an improved outer bound on the rate region of the general multi-terminal source coding problem. We further show that in the case of asymmetric peers, the coding scheme is not optimal.