Clustered K-Center: Effective Replica Placement in Peer-to-Peer Systems

Peer-To-Peer (P2P) systems provide decentralization, self-organization, scalability and failure-resilience, but suffer from high worst-case latencies. Researchers have proposed various replication algorithms to place multiple copies of objects across the network in pursuit of better performance for P2P computing; nevertheless, they neither presented clear analysis nor derived worst-case bound for their algorithms. In this paper, the authors model the replica placement problem arising in real-world P2P networks as a Clustered K-Center problem which they prove to be NP-complete. Then they propose an efficient approximation algorithm to this problem with a provable upper bound.