Database Location in Computer Networks
Marshall L. Fisher, Dorit S. Hochbaum · Journal of the ACM · 1980
Recent years have wRnessed an increasing number of systems of computers that are distributed geographically and connected by high-capacRy commumcauons channels in designing and managing such a network one must decide where to place copies of the various databases available to the users of the system This decision must trade off the cost of accessing a database, which ~s reduced by additional copies, against the cost of storing and updating the additional copies An optimizing algorithm for a general model of this problem ms described, and successful computational experience with large real examples is reported KEY WORDS AND PHRASES database location, mathematical programming models CR CATEGORIES 3 72, 4 33 IntroducuonRecent years have witnessed an increasing number of systems of computers that are distributed geographically and connected by high-capacity commumcations channels.The best known example is the network developed under the sponsorship of the Advanced Research Projects Agency (ARPA).These computer networks provide a number of benefits.They make possible the sharing of expensive specialized hardware, software, and databases, and they facilitate collaboration between geographically separated researchers studying the same problem.A number of difficult location problems arise in the design and management of such networks, including the problem of where to place copies of the various databases available to the users of the system.This decision must trade off the cost of accessing a database, which is reduced by additional copies, against the cost of storing and updating the additional copies.Other performance characteristics of the system are also affected by the positioning of database copies, including reliability of the system and opportumties for the parallel processing of requests against the database in order to reduce response time.This problem has received substantial attention.Previous literature (see Elam and Stutz [4] and Levin [13] for critical reviews) has been principally concerned with formulating appropriate models of the problem.Virtually all of these models are integer or mixedinteger linear programs.The more realistic models also belong to the notoriously difficult class of NP-hard problems, so we would expect the computation of an optimal solution to be a challenging task.Nevertheless, there has been little attention given to algorithm development in previous research.Computational experience with the few simple algorithms that have been proposed has been scant and limited to very small problems.This paper is intended to correct this gap in previous research.We describe an opumizing