Redundancy-based iterative method to select multiple safe replication sites for risk-aware data replication

This paper presents a method to solve the 'replication site decision problem' (RSDP) in a short computation time in the case of multiple replicas. RSDP is a problem of finding which combination with pairs of primary-replication sites is the safest when an assumed disaster such as an earthquake affects hundreds or thousands of sites. The existing representation of RSDP is solvable, but it frequently takes much computation time to seek an optimal solution because numerous replicas cause a rapid increase in the number of primary-replication site combinations. The proposed heuristic method, derived from redundancy-based problem partitioning and iterative parameter update techniques, reduces the number of combinations at the slight cost of data availability in the disaster-affected area. Computation time evaluation shows that the proposed method with two or three replicas costs at most twice or thrice, respectively, as much time as that of the original RSDP with one replica, independently of the number of sites. However, the original RSDP with two replicas costs 5 times as much time as that of the original RSDP at 10 sites and 3036 times at 80 sites. Moreover, the data availability cost of the proposed method is only 0.1%.