LOCATING REPLICAS OF A DATABASE ON A NETWORK

We study the problem of locating replicas of a database on a network t o minimize the communication cost. We first present extensions of the p-median theorem to prove that under two different measures of communi cation cost one can always optimally locate the replicas at the vertic es (nodes) of the network. We briefly review the fact that the problem is NP-hard for general networks under either measure of communication cost, and we then provide efficient algorithms for solving the proble m on tree networks for either of the two measures. (C) 1997 John Wiley & Sons, Inc.