Online Markov Chain Learning for Quality of Service Engineering in Adaptive Computer Systems

Computer systems are increasingly used in applications where the consequences of failure vary from financial loss to loss of human life. As a result, significant research has focused on the model-based analysis and verification of the compliance of business-critical and security-critical computer systems with their requirements. Many of the formalisms proposed by this research target the analysis of quality-of-service (QoS) computer system properties such as reliability, performance and cost. However, the effectiveness of such analysis or verification depends on the accuracy of the QoS models they rely upon. Building accurate mathematical models for critical computer systems is a great challenge. This is particularly true for systems used in applications affected by frequent changes in workload, requirements and environment. In these scenarios, QoS models become obsolete unless they are continually updated to reflect the evolving behaviour of the analysed systems.

This thesis introduces new techniques for learning the parameters and the structure of discrete-time Markov chains, a class of models that is widely used to establish key reliability, performance and other QoS properties of real-world systems. The new learning techniques use as input run-time observations of system events associated with costs/rewards and transitions between the states of a model. When the model structure is known, they continually update its state transition probabilities and costs/rewards in line with the observed variations in the behaviour of the system. In scenarios when the model structure is unknown, a Markov chain is synthesised from sequences of such observations. The two categories of learning techniques underpin the operation of a new toolset for the engineering of self-adaptive service-based systems, which was developed as part of this research. The thesis introduces this software engineering toolset, and demonstrates its effectiveness in a case study that involves the development of a prototype telehealth service-based system capable of continual self-verification.