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, we model the replica placement problem arising in real-world P2P networks as a Clustered K-Center problem which we prove to be NP-complete. Then we propose an efficient approximation algorithm to this problem with a provable upper bound. Extensive experiments have been conducted to demonstrate the effectiveness and efficiency of our algorithm. The experimental results show that our approach can run several orders of magnitude faster than the optimal solution while being able to minimizing the query latency.