Approximation Polynomial-Time Algorithms for Consistency-Aware Multi-Server Network Design in Delay-Sensitive Applications

This letter proposes two polynomial-time approximation algorithms for allocating servers to design a consistency-aware multi-server network for delay-sensitive applications. Each algorithm selects servers and determines the main-secondary server pairs to minimize the total delay. Previous work has not provided any polynomial-time algorithm. The proposed algorithms are theoretically guaranteed to output an approximate value within three times the optimal value. Numerical results show that the more computationally efficient of the two algorithms is 46.4 to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$5.26 \times 10^{4}$ </tex-math></inline-formula> times faster than an integer linear programming technique, while the maximum delay is, on average, merely 1.0196 times the optimal value.