A 2-Approximation Algorithm for QoS-Aware and Fault-Tolerant Replica Placement

Abstract

As emerging applications become more and more distributed and decentralized, how to design and build a faulttolerant network system with high Quality of Service (QoS) guarantee has become a challenging problem. In this paper, we formulate an unique optimal replica placement problem in terms of minimizing the replica placement cost subject to both QoS and fault-tolerant constraints at the same time. Based on the generalized graph model, we prove that the optimal replica placement problem is NP-hard. To solve the problem, our proposed a novel heuristic based greedy solution that comprises of two interesting rounding algorithms that are applied in tandem on the results preprocessed by a relaxed linear programming component. We further prove our the proposed greedy algorithm actually is a 2-approximate algorithm.

Publication
2020 IEEE High Performance Extreme Computing Conference