Reduced state-space Markov decision process and the dynamic recovery and reconfiguration of a distributed real-time system

The performance of a dynamic real-time system can be improved through dynamic system reconfiguration and recovery selection under the control of the proper policies. Different actions (recovery or reconfiguration) have different short term efficiencies (or reliability) and long term effects on the system. A selected policy should take into account both of these factors to achieve better overall system behavior. A real-time system can fail due to the missing of a single critical task\u27s deadline. Therefore, the selected control policies should be able to take care of every critical task during the system mission. This means that a decision is made not only on the average system behavior values, but also some instantaneous system operational information such as workload. With this consideration, the analytic state space of the Markov Decision Process model would be prohibitively large for any practical analysis. In this work, a Reduced State Space Markov Decision Process model is proposed to model the real-time system behavior. This model takes into account not only the system internal hardware state (such as configuration and fault pattern), external parameter (such as task arrival rate), system remaining mission time, and the action overheads but also the current instantaneous workload. Due to the use of a state space aggregation technique, our approach leads to a very efficient algorithm applicable to most real-time systems. With the help of our model, the realistic optimal control policies of the dynamic reconfiguration and recovery selection for a real-time system can be generated. It is illustrated, through numerical examples, that the dynamic recovery selection and reconfiguration approaches can significantly enhance the real-time system\u27s performance. In addition to the theoretical work, a real-time system emulator has been developed. It provides a means for the researchers to test and debug their theoretical results