DISTRIBUTED INFORMATION AND DISTRIBUTED CONTROL: CASES FROM STOCHASTIC SYSTEMS AND DATABASE MANAGEMENT (QUERY OPTIMIZATION, DISCRETE-EVENT

The notions of state and state transition play a central role in the study of dynamical systems. In many control problems, state information is distributed or incomplete. Important issues arising in such problems are proper choice of observations, communication strategies between the decision makers at each location, and choice of a centralized or distributed control strategy.;This dissertation considers three different problems, each incorporating some or all of these issues. The first part studies the role of communication in conventional discrete-time stochastic control problems. A combined observation/control optimization problem is formulated and solved. This problem differs from previous work by the added feature that, at each stage, the decision makers can choose among different observations, each observation incurring a different cost. Dynamic programming is employed to determine the optimal observations and controls.;The second and third parts deal with two problems from database management. Although far less structured than stochastic control problems, their dynamics are described with the help of a state/state-transition formulation. The first problem studied is that of concurrency control. A state model (where the state is a graph composed of different types of arcs) is proposed for the analysis of existing concurrency control techniques. The partial state information nature of this problem is clearly identified, and a new locking protocol based on the idea of state estimation is presented. This protocol uses a higher degree of central control than conventional techniques to allow for more concurrency between the users of the database.;The optimization of query processing, particularly in the case of a distributed database, is the other database-management problem studied. The operations involved in the processing of a query are parametrized by means of a state-transition model. The optimization of communication and local processing costs is done by using a dynamic programming algorithm over the state space obtained from the model. This state space is general enough to encompass many important optimization strategies currently in use.