Cheng, Chieh-WenChieh-WenChengWu, Jan-JanJan-JanWuPANGFENG LIU2009-05-062018-07-052009-05-062018-07-05200809208542http://ntur.lib.ntu.edu.tw//handle/246246/155141https://www.scopus.com/inward/record.uri?eid=2-s2.0-68149156351&doi=10.1007%2fs11227-008-0221-1&partnerID=40&md5=f9290b5583e889ce1f84d463d2b182bdIn this paper, we study the quality-of-service (QoS)-aware replica placement problem in grid environments. Although there has been much work on the replica placement problem in parallel and distributed systems, most of them concern average system performance and have not addressed the important issue of quality of service requirement. In the very few existing work that takes QoS into consideration, a simplified replication model is assumed; therefore, their solution may not be applicable to real systems. In this paper, we propose a more realistic model for replica placement, which consider storage cost, update cost, and access cost of data replication, and also assumes that the capacity of each replica server is bounded. The QoS-aware replica placement is NP-complete even in the simple model. We propose two heuristic algorithms, called greedy remove and greedy add to approximate the optimal solution. Our extensive experiment results demonstrate that both greedy remove and greedy add find a near-optimal solution effectively and efficiently. Our algorithms can also adapt to various parallel and distributed environments. © 2008 Springer Science+Business Media, LLC.application/pdf572439 bytesapplication/pdfen-USData grids; Greedy heuristics; Replica placement[SDGs]SDG9Access cost; Average system; Data grids; Data replication; Distributed environments; Greedy heuristics; Grid environments; Near-optimal solutions; NP Complete; Optimal solutions; Parallel and distributed systems; Real systems; Realistic model; Replica placement; Replica placement problems; Replica servers; Replication models; Simple model; Storage costs; Grid computing; Heuristic methods; Optimal systems; Parallel algorithms; Quality of service; Heuristic algorithmsjournal article10.1007/s11227-008-0221-12-s2.0-68149156351http://ntur.lib.ntu.edu.tw/bitstream/246246/155141/1/14.pdf