Consistency-Aware Multi-Server Network Design under Server Failures in Delay-Sensitive Applications
Masaki Oda, Akio Kawabata, Eiji Oki · 2025
Real-time applications require low latency and event order guarantees. While distributed server processing is effective, data consistency across servers is crucial. Existing models address consistency but overlook server failures. This paper proposes a server allocation model for a consistency-aware multi-server network for delay-sensitive applications with preventive start-time optimization (PSO) under single-server failures. PSO determines the assignment to minimize the worst-case delay over all possible failure scenarios while avoiding service disruption for users connected to non-failed servers. We formulate the proposed model as an integer linear programming (ILP) problem. The decision version of the server allocation problem is proven to be NP-complete, and it becomes difficult to solve in a practical time when the problem size is large. We develop a polynomial-time approximation algorithm with theoretical performance analysis. Numerical results show that the proposed model outperforms start-time optimization in terms of the largest total delay and run-time optimization in terms of avoiding instability. Numerical results also show that our developed algorithm achieves a maximum speedup of 33.8 times compared to the ILP approach, while the maximum delay is, on average, only 1.016 times the optimal value.