A Methodology for the Design of Distributed Databases and Distributed Systems.

Abstract

In the design of distributed databases and distributed systems there are four aspects of major importance: the selection of the computer system for each site, data allocation, program allocation, and the determination of the site for the execution of each process. In order to determine these elements, a model of distributed systems is developed. Based on the model, two optimization problems are considered. The basic problem consists of data allocation, program allocation and process assignment, and the selection of a computer for each site such that system constraints, application availability constraints, and system performance requirements are satisfied. In the first problem, the objective is to minimize the response time of the system while satisfying all system constraints and performance requirements. In the second problem, the objective is to obtain a system which satisfies all requirements at minimal cost, and to obtain the minimal response time at this minimal cost. To apply the methodology, the definition of the architecture of the system and a clear definition of all applications is necessary. It is also assumed that the applications, called transactions, are r and omly submitted for execution at the sites of the system. Since the optimization problems are computationally very complex, heuristic approaches are used to solve them. Two approaches, called, respectively, deterministic local search and probabilistic local search, are used to solve the problems. Although a solution to a solvable instance of the problems may not always be found, and a solution obtained is not necessarily a global optimum, comparison with solutions obtained with branch- and -bound algorithms shows that, at least for small problems, the solutions obtained with the heuristic approaches are close to optimal. For large problems, experimental results indicate that for most instances the solution obtained is satisfactory.