Abstract
Real-time applications require low latency and strict event ordering to ensure seamless operation. Distributed server processing is effective for this purpose, and there are two synchronization algorithms: a conservative synchronization algorithm (CSA) and an optimistic synchronization algorithm (OSA). OSA improves delay performance compared to CSA. While prior studies have considered OSA, they have not incorporated the impact of server failures. This paper proposes an OSA-based server allocation model for delay-sensitive applications with preventive start-time optimization (PreSO) under single-server failures (OSA-PreSO). The proposed OSA-PreSO model minimizes the largest total delay across all failure scenarios while satisfying constraints in OSA with PreSO under single-server failures. We formulate the proposed model as an integer linear programming (ILP) problem. In OSA-PreSO, the objective is to minimize the largest total delay across all failure scenarios, without giving special consideration to the total delay in the no-failure scenario. As a result, a penalty arises in the form of an increased total delay in the no-failure scenario. To reduce the penalty, we develop an improved OSA-PreSO model, OSA-PreSO-LP (low-penalty), which reduces the total delay in the nofailure scenario while maintaining the same delay characteristics in failure scenarios. We prove that the decision version of OSA-PreSO is NP-complete. We introduce heuristic algorithms to handle large-scale problems. Numerical results show that the proposed OSA-PreSO model reduces the delay compared to the conventional CSA-based model by effectively utilizing server memory resources. We observe that the proposed model achieves a lower largest total delay than start-time optimization and provides greater stability by preventing unnecessary user reassignments compared to run-time optimization. Numerical results also show that OSA-PreSO-LP reduces the penalty at most by 83%, while maintaining the same delay characteristics in failure scenarios.
Funding Information
  • Japan Society for the Promotion of Science (JSPS) Kakenhi (25K22800)
  • Japan Society for the Promotion of Science (JSPS) Kakenhi (25KF0055)