A multi-level model for self-adaptive systems
This work provides a formal framework for self-adaptive systems, which is incremental as it builds on existing theoretical computer science concepts to address complexity in emerging fields.
The authors tackled the problem of modeling self-adaptive systems by introducing a general multi-level model with two levels: a lower-level state machine and an upper-level second-order state machine to handle environmental constraints. They formalized weak and strong adaptability concepts and provided a flattened transition system for static correctness checking, aiming to give a formal computational characterization of such systems.
This work introduces a general multi-level model for self-adaptive systems. A self-adaptive system is seen as composed by two levels: the lower level describing the actual behaviour of the system and the upper level accounting for the dynamically changing environmental constraints on the system. In order to keep our description as general as possible, the lower level is modelled as a state machine and the upper level as a second-order state machine whose states have associated formulas over observable variables of the lower level. Thus, each state of the second-order machine identifies the set of lower-level states satisfying the constraints. Adaptation is triggered when a second-order transition is performed; this means that the current system no longer can satisfy the current high-level constraints and, thus, it has to adapt its behaviour by reaching a state that meets the new constraints. The semantics of the multi-level system is given by a flattened transition system that can be statically checked in order to prove the correctness of the adaptation model. To this aim we formalize two concepts of weak and strong adaptability providing both a relational and a logical characterization. We report that this work gives a formal computational characterization of multi-level self-adaptive systems, evidencing the important role that (theoretical) computer science could play in the emerging science of complex systems.