Optimal File Distribution in Peer-to-Peer Networks
The authors study the problem of distributing a file initially located at a server among a set of peers. Peers who downloaded the file can upload it to other peers. The server and the peers are connected to each other via a core network. The upload and download rates to and from the core are constrained by user and server specific upload and download capacities. Their objective is to minimize the make-span. They derive exact polynomial time algorithms for the case when upload and download capacities per peer and among peers are equal. They show that the problem becomes strongly NP-hard for equal upload and download capacities per peer that may differ among peers.