Automated Design of Self-Adaptive Software with Control-Theoretical Formal Guarantees

Reference: Filieri, A., Hoffmann, H. & Maggio, M. (2014). Automated Design of Self-Adaptive Software with Control-Theoretical Formal Guarantees. In Proc. 36th International Conference on Software Engineering (ICSE ’14), ACM, pp. 299–310. DOI: 10.1145/2568225.2568272. URL

Summary

This paper attacks a practical obstacle to using control theory for self-adaptation: designing a controller normally requires control-engineering expertise that most software engineers lack. The authors propose an automated method that, given a software system exposing a tunable knob and a measurable goal, builds a dynamic model of the system by lightweight experimentation and then synthesises a controller for it — turning controller design into a push-button step of the software process rather than a bespoke modelling exercise.

The technique performs on-line system identification to fit a simple (linear, adaptive) model relating the control input to the measured output, then automatically derives a controller whose parameters are chosen to deliver formal control-theoretic guarantees: stability of the closed loop, absence of steady-state error (the goal is met in the limit), bounded settling time, and robustness to modelling inaccuracy and disturbances. Because the model is re-estimated on-line, the controller adapts as the system or environment drifts. The result is a general, reusable way to give self-adaptive software the kind of provable regulation guarantees advocated by Feedback Control of Computing Systems and Engineering Self-Adaptive Systems through Feedback Loops, without demanding that each developer become a control engineer.

Key Ideas

Automated controller synthesis: given a knob and a measurable goal, generate a controller with no manual control-theory design.
On-line system identification fits a simple adaptive model of input→output behaviour and re-estimates it as the system drifts.
Delivers formal guarantees — stability, zero steady-state error (goal convergence), bounded settling time, robustness to disturbance/model error.
Makes control-theoretic adaptation reusable and accessible to software engineers, not just control specialists.
A concrete bridge from classical control theory to the MAPE-K loop’s Plan/Execute stages.

Connections

Conceptual Contribution

Claim: Control-theoretic self-adaptation can be automated — a controller with formal stability and convergence guarantees can be synthesised from a system’s own measured behaviour, removing the control-engineering expertise barrier.
Mechanism: On-line system identification fits an adaptive linear model of the control input’s effect on the goal metric; a controller is then derived automatically to guarantee stability, zero steady-state error, bounded settling time, and robustness, and is re-tuned as the model is re-estimated.
Concepts introduced/used: Control Theory, System Identification, Feedback Loop, MAPE-K, Runtime Assurance
Stance: engineering / method
Relates to: Operationalises the control-theoretic programme of Feedback Control of Computing Systems and Engineering Self-Adaptive Systems through Feedback Loops, and supplies one form of the runtime assurance called for by Software Engineering for Self-Adaptive Systems - A Second Research Roadmap.

Tags

#control-theory #self-adaptive #feedback-control #controller-synthesis #runtime-assurance #software-engineering

Backlinks

Feedback Control of Computing Systems ×2
Engineering Self-Adaptive Systems through Feedback Loops ×2
index
Runtime Assurance ×2
Feedback Loop
Control Theory ×2

Linked Pages

Software Engineering for Self-Adaptive Systems - A Second Research Roadmap

Software Engineering for Self-Adaptive Systems: A Second Research Roadmap

Reference: de Lemos, R., Giese, H., Müller, H. A., Shaw, M., et al. (2013). Software Engineering for Self-Adaptive Systems: A Second Research Roadmap. In Software Engineering for Self-Adaptive Systems II, LNCS 7475, Springer, pp. 1–32. DOI: 10.1007/978-3-642-35813-5_1. URL

Summary

The second SEAMS roadmap, produced four years after the first, takes stock of the field’s progress and re-sets the agenda around what the community had learned to be the genuinely hard problems. Where the first roadmap partitioned the space, this one is organised around four thematic challenges that had emerged as central: design space (systematically characterising the choices a designer of a self-adaptive system faces), processes (development and lifecycle processes that span design time and runtime), decentralisation of control loops (moving beyond a single MAPE-K loop to multiple, interacting control loops and coordination patterns among them), and practical run-time verification and validation (V&V).

The roadmap’s sharpest emphasis is on assurance: it argues that self-adaptive systems demand a continuous supply of evidence that requirements are still met as the system and its environment change, shifting V&V from a design-time gate to a runtime, incremental activity. It highlights the need to reason explicitly about the uncertainty that motivates adaptation, to make control loops (and their interactions) explicit architectural entities, and to develop perpetual assurance techniques — including quantitative and formal methods applied at runtime — that keep pace with adaptation. It is the standard “state of the field, part II” reference for engineering and assuring self-adaptive software.

Key Ideas

Four thematic challenges: design space, processes (design-time + runtime), decentralised control loops, and practical run-time V&V.
Decentralised control: self-adaptive systems increasingly need multiple interacting MAPE-K loops with explicit coordination, not one central loop.
Perpetual / runtime assurance: continuous, incremental evidence that goals still hold, replacing one-shot design-time verification.
Uncertainty is first-class: adaptation exists to handle it, so it must be modelled and reasoned about explicitly across the lifecycle.
Positions runtime quantitative verification and formal runtime models as key enabling techniques for assurance.

Connections

Conceptual Contribution

Claim: Four years on, the hard core of engineering self-adaptive systems is decentralised control, lifecycle processes spanning design/runtime, and — above all — continuous runtime assurance under uncertainty.
Mechanism: Reorganise the agenda around design space, processes, decentralisation of control loops, and practical run-time V&V; treat uncertainty as first-class and pursue perpetual assurance via runtime quantitative/formal verification.
Concepts introduced/used: Runtime Assurance, MAPE-K, Requirements Under Uncertainty, Feedback Loop, Runtime Quantitative Verification
Stance: roadmap / community agenda
Relates to: The sequel to Software Engineering for Self-Adaptive Systems - A Research Roadmap; its assurance emphasis is realised in Self-Adaptive Software Needs Quantitative Verification at Runtime and ActivFORMS - Active Formal Models for Self-Adaptation, and its decentralised-control theme extends the single loop of The Vision of Autonomic Computing.

Tags

Engineering Self-Adaptive Systems through Feedback Loops

Reference: Brun, Y., Di Marzo Serugendo, G., Gacek, C., Giese, H., Kienle, H., Litoiu, M., Müller, H., Pezzè, M. & Shaw, M. (2009). Engineering Self-Adaptive Systems through Feedback Loops. In Software Engineering for Self-Adaptive Systems, LNCS 5525, Springer, pp. 48–70. DOI: 10.1007/978-3-642-02161-9_3. URL

Summary

This chapter makes a single, influential argument: the feedback loop should be a first-class, explicit entity in the engineering of self-adaptive software. The authors observe that although virtually every self-adaptive system is, at heart, one or more control loops, those loops are usually hidden — dispersed through the code and left implicit — which makes the system hard to understand, analyse, and assure. Their prescription is to surface the loop as an architectural element with named, documented parts, drawing directly on the long tradition of control engineering, where feedback loops are the primary object of design and analysis.

The paper anatomises the loop into its canonical activities — collect (sense), analyse, decide, and act — closely mirroring MAPE-K, and stresses the properties engineers must reason about by analogy to control theory: stability, accuracy, settling time, and overshoot, together with the handling of disturbances and the cost of sensing and actuation. It further argues for making the loop’s control properties explicit design concerns and for recognising when a system needs multiple, possibly interacting or hierarchical loops. By naming the feedback loop as the unit of design and importing control-theoretic vocabulary, the chapter became a standard reference for the “the loop is the architecture” stance in self-adaptive systems.

Key Ideas

Make the feedback loop first-class: name it, document its parts, and treat it as the primary architectural element — not logic buried in code.
Canonical loop activities — collect → analyse → decide → act — align with the MAPE-K phases.
Import control-engineering properties as design concerns: stability, accuracy, settling time, overshoot, disturbance rejection.
Reason explicitly about multiple and interacting loops (hierarchical or coordinated control).
Positions control theory as a source of both design guidance and assurance for adaptation.

Connections

Conceptual Contribution

Claim: Because a self-adaptive system is a feedback control system, the feedback loop should be an explicit, first-class engineering artefact whose control properties are designed and analysed, not an implicit by-product of the code.
Mechanism: Surface the loop as an architectural element with named collect/analyse/decide/act parts (the MAPE-K phases), reason about it with control-theoretic properties (stability, accuracy, settling time, overshoot), and structure systems as one or more coordinated loops.
Concepts introduced/used: Feedback Loop, MAPE-K, Control Theory, Self-Adaptation
Stance: engineering / position
Relates to: Deepens the feedback-loop theme of the SEAMS roadmaps (Software Engineering for Self-Adaptive Systems - A Research Roadmap); its control-theoretic programme is made rigorous in Feedback Control of Computing Systems and Automated Design of Self-Adaptive Software with Control-Theoretical Formal Guarantees.

Tags

Feedback Control of Computing Systems

Reference: Hellerstein, J. L., Diao, Y., Parekh, S. & Tilbury, D. M. (2004). Feedback Control of Computing Systems. Wiley–IEEE Press. ISBN 978-0-471-26637-2. URL

Summary

This book is the standard text that brings classical control theory to bear on computing systems, and it is the reference source for the control-theoretic strand of self-adaptation. Its thesis is that the performance and resource management of software systems — web servers, databases, middleware, queues — can and should be engineered with the same feedback-control apparatus used in mechanical and electrical engineering: model the system, design a controller, and obtain provable guarantees about its closed-loop behaviour rather than tuning by trial and error.

The authors develop the toolkit systematically: black-box system identification to fit dynamic models (e.g. difference-equation / transfer-function models) to measured input–output data from a computing system; controller design (proportional, integral, PID and pole-placement techniques); and analysis of the resulting closed loop through the properties that name the book’s recurring acronym SASO — Stability, Accuracy, Settling time, and Overshoot. Worked examples target real systems such as Apache HTTP server tuning, Lotus Notes/email server admission control, and load and queue-length regulation. For the self-adaptive-systems community the book supplies the rigorous underpinning that papers like Engineering Self-Adaptive Systems through Feedback Loops invoke: when the MAPE-K loop is treated as a genuine control loop, this is where the design-and-guarantee machinery comes from.

Key Ideas

Applies classical (mostly linear) control theory to computing systems for performance and resource management.
System identification: fit empirical dynamic models to measured input/output data of a running system (black-box modelling).
Controller design: proportional/integral/PID and pole-placement controllers for computing targets.
SASO closed-loop properties — Stability, Accuracy, Settling time, Overshoot — as the analysis vocabulary.
Concrete case studies (Apache, email/Notes servers, queueing/admission control) demonstrating measured, guaranteed regulation.

Connections

Conceptual Contribution

Claim: The dynamic behaviour of computing systems can be managed with classical feedback control, yielding provable closed-loop guarantees (stability, accuracy, settling time, overshoot) instead of heuristic tuning.
Mechanism: Identify an empirical dynamic model of the target system, design a proportional/integral/PID or pole-placement controller against it, and analyse the closed loop with the SASO properties; validate on real server/queue case studies.
Concepts introduced/used: Control Theory, Feedback Loop, System Identification, MAPE-K
Stance: foundational textbook / methodology
Relates to: The rigorous control-theoretic basis behind the “loop as first-class artefact” stance of Engineering Self-Adaptive Systems through Feedback Loops and the automated controller synthesis of Automated Design of Self-Adaptive Software with Control-Theoretical Formal Guarantees.

Tags

Runtime Assurance

The provision of continuous, runtime evidence that a self-adaptive system still satisfies its requirements as the system, its environment, and its workload change — replacing (or supplementing) one-shot design-time verification with an incremental, always-on activity. Because self-adaptation defers decisions to runtime precisely to cope with uncertainty, the guarantees must be re-established at runtime too; the SEAMS roadmaps call this perpetual assurance and treat it as the field’s defining challenge.

Runtime assurance is realised through several complementary techniques in this vault: quantitative (probabilistic) verification at runtime (Self-Adaptive Software Needs Quantitative Verification at Runtime), executable verified formal models of the feedback loop (ActivFORMS - Active Formal Models for Self-Adaptation), and control-theoretic guarantees synthesised for the adaptation controller (Automated Design of Self-Adaptive Software with Control-Theoretical Formal Guarantees). All of them keep a runtime model in the MAPE-K knowledge base and re-check goals against it as conditions drift.

In this vault

MAPE-K

The reference control loop of Autonomic Computing and self-adaptive software: an autonomic manager runs a closed feedback loop of Monitor → Analyse → Plan → Execute over a shared Knowledge base, acting on a managed element through sensors (probes/gauges) and effectors.

Monitor — collect and aggregate sensor data from the managed element and its environment.
Analyse — detect when adaptation is needed (symptoms, constraint/SLA violations, drift from goals).
Plan — select a course of action (a strategy/tactic, reconfiguration, or repair).
Execute — enact the plan through effectors on the managed element.
Knowledge — models, policies, goals, and history shared across the four phases (see Models@run.time).

Introduced in The Vision of Autonomic Computing (Kephart & Chess 2003) as the organising abstraction for the self-* properties (self-configuration, self-healing, self-optimisation, self-protection). It is the connective tissue linking architecture-based adaptation (Rainbow - Architecture-Based Self-Adaptation with Reusable Infrastructure), reference models (Three-Layer Reference Model), and the broader survey landscape (Self-Adaptive Software - Landscape and Research Challenges).

In this vault

Feedback Loop

A control structure in which a system observes the effect of its own actions (or of environmental change) and feeds that observation back to adjust subsequent behaviour toward a goal. Feedback control is the engineering backbone of self-adaptation: the MAPE-K loop is a feedback loop whose sensor readings (Monitor) close back onto the actions taken through effectors (Execute).

Making the feedback loop a first-class, visible architectural element — rather than logic buried in application code — is a recurring theme of the self-adaptive-systems literature and connects the field to classical control theory (stability, settling time, overshoot) as a source of design and assurance techniques.

In this vault

System Identification

(page does not exist)

Control Theory

The engineering discipline of designing feedback controllers that drive a system toward a reference goal despite disturbances, and of analysing the resulting closed loop for properties such as stability, accuracy, settling time, and overshoot (the “SASO” properties). In self-adaptive software it is the rigorous underpinning of the Feedback Loop / MAPE-K stance: if an adaptive system is really a control loop, control theory supplies both the design methods and the guarantees.

The line runs from Feedback Control of Computing Systems (Hellerstein et al. 2004), which imports classical control into computing-systems performance management via system identification and controller design, through Engineering Self-Adaptive Systems through Feedback Loops (Brun et al. 2009), which argues the loop should be a first-class artefact, to Automated Design of Self-Adaptive Software with Control-Theoretical Formal Guarantees (Filieri, Hoffmann & Maggio 2014), which automates controller synthesis so software engineers get formal guarantees without doing the control-theory design by hand.

In this vault

Self-Adaptation

A system’s capability to modify its own behaviour or structure at runtime in response to internal or environmental change, without external intervention. It is typically implemented as a MAPE-K loop (Monitor-Analyse-Plan-Execute over a Knowledge base), the control abstraction introduced by Autonomic Computing.