Data grids have been adopted by many scientific communities that need to share, access, transport, process, and manage geographically distributed large data collections. Data replication is one of the main mechanisms used in data grids whereby identical copies of data are generated and stored at various distributed sites to either improve data access performance or reliability or both. However, when data updates are allowed, it is a great challenge to simultaneously improve performance and reliability while ensuring data consistency of such huge and widely distributed data. In this paper, we address this problem. We propose a new quorum-based data replication protocol with the objectives of minimizing the data update cost, providing high availability and data consistency. We compare the proposed approach with two existing approaches using response time, data consistency, data availability, and communication costs. The results show that the proposed approach performs substantially better than the benchmark approaches.