Market-Based Model Predictive Control for Large-Scale Information Networks: Completion Time and Value of Solution

There are several important properties of modern software systems. They tend to be large-scale with distributed and component-based architectures. Also, dynamic nature of operating environments leads them to utilize alternative algorithms. However, on the other hand, these properties make it hard to provide appropriate control mechanisms due to the increased complexity. Components are sharing resources and each component can have alternative algorithms. As a result, the behavior of a software system can be controlled through resource allocation, as well as algorithm selection. This novel control problem is worthy of investigation in order to double the benefits of those properties. In this paper, we design a control mechanism for such systems. The quality-of-service we are considering is a product of the value of solution and the time for generating solution for a given problem. We build a mathematical programming model that trades off these two conflicting objectives, and decentralize the model through an auction market. By periodically opening the auction market for each existing system state, a closed-loop policy is formed. Though similar problems can be found in multiprocessor scheduling literature, they have limitations in addressing this control problem. They commonly consider so-called workflow applications in which each component only has to process one task after all of its predecessors complete their tasks. In contrast, a component in the networks under consideration processes multiple tasks in parallel with its successors or predecessors.