A model for optimal resource allocation in distributed computing systems

Optimal allocation of redundant resources in distributed computing systems is studied. In this model, a request from a processing site for a resource can be satisfied by any one of the copies. Among the redundant copies of the resources, the least-expensive and the second-least-expensive ones are considered for accessing by each processing site, which is measured in terms of communication cost. This access scheme offers to encompass some of the intrinsically important features, such as graceful degradation and reliability consideration, in the design model. The increase of communication cost due to the failures of resources should be gradual to maintain the system performance. With the present formulation, the goal of the allocation is to minimize the total communication cost incurred. The Lagrangian relaxation and subgradient methods are applied to solve this problem. An efficient algorithm based on these techniques, and computational results, are presented.<>