|
|||||
|
|
The optimal location of replicas in a network using a READ-ONE-WRITE-ALL policy |
|
| Authors: | Stephen A. Cook Jan Pachl Irwin S. Pressman |
| Affiliation: | (1) Department of Computer Science, University of Toronto, 10 King's College Road, Toronto, Ontario, Canada M5S 3G4 (e-mail: sacook@cs.toronto.edu), CA;(2) The Fields Institute for Research in Mathematical Sciences, 222 College Street, Toronto, Ontario, Canada M5T 3J1 (e-mail: pachl@acm.org), CA;(3) School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, Ontario, Canada K1S 5B6 (e-mail: ipress@math.carleton.ca), CA |
| Abstract: | We consider the problem of locating replicas in a network to minimize communications costs. Under the assumption that the read-one-write-all policy is used to ensure data consistency, an optimization problem is formulated in which the cost function estimates the total communications costs. The paper concentrates on the study of the optimal communications cost as a function of the ratio between the frequency of the read and write operations. The problem is reformulated as a zero-one linear programming problem, and its connection to the p-median problem is explained. The general problem is proved to be NP-complete. For path graphs a dynamic programming algorithm for the problem is presented. Received: May 1993 / Accepted: June 2001 |
| Keywords: | : Data replication – Optimization – Dynamic programming – NP-completeness |
| 本文献已被 SpringerLink 等数据库收录！ | |