1 Introduction
-
The EvoChecker approach for the search-based synthesis of probabilistic models for QoS software engineering, and its application to the synthesis of models that meet QoS requirements both at design time and at runtime.
-
The definition of the probabilistic model synthesis problem.
-
An incremental probabilistic model synthesis technique for the efficient runtime generation of probabilistic models that satisfy the QoS requirements of a self-adaptive system.
-
An extensive evaluation of EvoChecker in three case studies drawn from different application domains.
-
A prototype open-source EvoChecker tool and a repository of case studies, both of which are freely available from our project webpage at http://www-users.cs.york.ac.uk/simos/EvoChecker.
2 Running example
ID | Informal description |
---|---|
R1 | “Workflow executions must complete successfully with probability at least 98%” |
R2 | “The total service response time per workflow execution should be minimised” |
R3 | “The probability of a service failure during a workflow execution should be minimised” |
R4 | “The total cost of the third-party services used by a workflow execution should be minimised” |
-
if \(\textit{str}_i=\text {PROB}\), FX uses a probabilistic strategy to randomly select one of the service implementations based on an FX-specified discrete probability distribution \(p_{i1}, p_{i2},\ldots , p_{im_i}\); and
-
if \(\textit{str}_i=\text {SEQ}\), FX uses a sequential strategy that employs an execution order to invoke one after the other all enabled service implementations until a successful response is obtained or all invocations fail.
3 EvoChecker modelling language
-
Each evolvable parameter (2) is replaced by a ‘const int param = val;’ or ‘const double param = val;’ declaration (depending on the type of the parameter), where \(val\in \{min, \ldots , max\}\) or \(val\in [min..max]\), respectively.
-
Each evolvable probability distribution (3) is removed, and the n occurrences of its name instead of expressions \(e_1\), ..., \(e_n\) of a command (1) are replaced with values from the ranges \([\textit{min}_1\textit{..max}_1]\), ..., \([\textit{min}_n\textit{..max}_n]\), respectively. For a discrete-time model, the sum of the n values is 1.0.
-
Each set of evolvable modules with the same name is replaced with a single element from the set, from which the keyword ‘evolve’ was removed.
Type of probabilistic model | QoS requirement specification logic |
---|---|
Discrete-time Markov chains | PCTL\(^\mathrm{a}\), LTL\(^\mathrm{b}\), PCTL*\(^\mathrm{c}\) |
Continuous-time Markov chains | CSL\(^\mathrm{d}\) |
Markov decision processes | PCTL\(^\mathrm{a}\), LTL\(^\mathrm{b}\), PCTL*\(^\mathrm{c}\) |
Probabilistic automata | PCTL\(^\mathrm{a}\), LTL\(^\mathrm{b}\), PCTL*\(^\mathrm{c}\) |
Probabilistic timed automata | PCTL\(^\mathrm{a}\) |
-
four evolvable parameters specify the enabled Market watch service implementations and their execution order (lines 50–53) associated with the sequential invocation strategy;
-
an evolvable distribution specifies the discrete probability distribution for the probabilistic invocation strategy of the first MarketWatch module (line 36);
-
two alternative implementations of the MarketWatch module are provided in lines 37–49 and 54–57, respectively.
4 EvoChecker specification of QoS requirements
4.1 Quality-of-service attributes
QoS attribute | Informal description | Formula \({\varPhi }_i\) |
---|---|---|
\( attr _1\)
| Workflow reliability |
\(P_{=?} [F\; state \!=\!15]\)
|
\( attr _2\)
| Workflow response time |
\(R_{=?}^{\textsf {time}} [F\; state \!=\!15 \vee state \!=\!5]\)
|
\( attr _3\)
| Workflow invocation cost |
\(R_{=?}^{\textsf {invocationCost}} [F\; state \!=\!15 \vee state \!=\!5]\)
|
-
the probabilities \( pExpert \), \( pSat \), \( pNotSat \), \( pTrade \) and \( pRetry \) from module WorkflowFX in Fig. 2;
-
the success probabilities \(r_{ij}\), response times \(t_{ij}\) and costs \(c_{ij}\) of the FX service implementations.
-
the invocation strategies \( str _i\) used for the ith FX service;
-
the probabilities \(p_{ij}\) of invoking the jth implementation of service i when the probabilistic invocation strategy is used;
-
the \(x_{ij}\) and \( ex _i\) parameters specifying which implementations of service i are used by the sequential invocation strategy and their execution order.
4.2 Quality-of-service requirements
ID | Formal description | Informal description | Requirement type |
---|---|---|---|
R1
|
\( attr _1 \ge 0.98\)
| Workflow reliability greater than 98% | Constraint |
R2
|
\(\textsf {minimise} \quad attr _2\)
| Minimise workflow reponse time | Optimisation objective |
R3
|
\(\textsf {minimise} \quad 1- attr _1\)
| Minimise worklfow reliability | Optimisation objective |
R4
|
\(\textsf {minimise} \quad attr _3\)
| Minimise workflow invocation cost | Optimisation objective |
5 EvoChecker probabilistic model synthesis
5.1 Using EvoChecker at design time
5.1.1 Probabilistic model synthesis problem
5.1.2 Probabilistic model synthesis approach
Evolvable feature of the probabilistic model template | EvoChecker gene(s) | ||
---|---|---|---|
Type | Cardinality | Value range \(V_i\) | |
evolve int param\([\textit{min..max }\!]\); | int | 1 |
\(\{\textit{min,\ldots , max}\}\)
|
evolve double param\([\textit{min..max }\!]\); | double | 1 |
\([\textit{min..max }\!]\)
|
\(\begin{array}{l}\textsf {evolve distribution}{} \textit{dist}[\textit{min}_1\textit{..max}_1]\ldots \\ \quad \quad \quad \qquad \qquad \qquad \ldots [\textit{min}_n\textit{..max}_n];\end{array}\)
| double | n | \([\textit{min}_1\textit{..max}_1]\) ...\([\textit{min}_n\textit{..max}_n]\) |
evolve module
\(\textit{mod implementation}_1\)
| int | 1 |
\(\{1,2,\ldots ,m\}\)
|
endmodule... | |||
evolve module
\(\textit{modimplementation}_m\)
| |||
endmodule
|
5.2 Using EvoChecker at runtime
5.2.1 EvoChecker -based self-adaptive systems
5.2.2 Runtime probabilistic model synthesis
\(\bigl (\forall 1 \le i \le n_1 \bullet attr _i(e,c) \bowtie _i bounds_i \;\wedge \;\) | |
\(\exists 1 \le i \le n_1 \bullet \lnot ( attr _i(e,c') \bowtie _i bounds_i)\bigr )\;\vee \) | ① |
\(\bigl (\forall 1 \le i \le n_1 \bullet attr _i(e,c) \bowtie _i bounds_i \;\wedge \; attr _i(e,c') \bowtie _i bounds_i\) | |
\(\wedge \; loss (e,c) < loss (e,c')\bigr )\;\vee \) | ② |
\(\bigl (\exists 1\!\!\le \!i,j\!\!\le n_1 \bullet \lnot ( attr _i(e,c)\!\bowtie _i bounds_i) \wedge \lnot ( attr _j(e,c')\!\bowtie _j bounds_j)\) | |
\(\wedge \; violation (e,c) < violation (e,c')\bigr )\) | ③ |
6 Implementation
7 Evaluation
7.1 Evaluating EvoChecker at design time
7.1.1 Research questions
7.1.2 Experimental setup
Variant | Details | Size | T\(_\text {run}[s]\) |
---|---|---|---|
FX_Small |
\(m_1 = \cdots = m_4 = 3, m_5 = m_6 =1\)
| 4.98E+31 | 0.0858 |
FX_Medium |
\(m_1=\cdots =m_6=4\)
| 1.39E+65 | 0.1695 |
FX_Large |
\(m_1=\cdots =m_8=4\)
| 7.22E+86 | 0.4162 |
DPM_Small | \( Qmax _{H,L}\!\in \! \{1,\ldots ,10\}\), \(m\!=\!2\) | 2E+14 | 0.1050 |
DPM_Medium | \( Qmax _{H,L}\!\in \! \{1,\ldots ,15\}\), \(m\!=\!2\) | 4.5E+14 | 0.2118 |
DPM_Large | \( Qmax _{H,L}\!\in \! \{1,\ldots ,20\}\), \(m\!=\!2\) | 8E+14 | 0.3796 |
7.1.3 Evaluation methodology
×
|
7.1.4 Results and discussion
×
|
×
|
7.2 Evaluating EvoChecker at runtime
7.2.1 Research questions
7.2.2 Experimental setup
Variant | Details | Size | T\(_\text {run}[s]\) |
---|---|---|---|
UUV_Medium | \(m=5, r_1, r_2, \ldots , r_5 \in [0Hz, 8Hz]\), \(sp \in [0,10m/s]\) | 1.04E+19 | 0.0076 |
UUV_Large | \(m\!=\!10, r_1, r_2, \ldots , r_{10} \!\in \! [0Hz, 8Hz]\), \(sp \!\in \! [0,10m/s]\) | 1.09E+35 | 0.1622 |
FX_Small |
\(m_1 = \cdots = m_4 = 3, m_5 = m_6 =1\)
| 4.98E+31 | 0.0312 |
FX_Medium |
\(m_1=\cdots =m_6=4\)
| 1.39E+65 | 0.0953 |
ID | Informal description |
---|---|
R1 | “The UUV must take at least 500 accurate measurements for each 100 m travelled” |
R2 | “The UUV sensors must not consume more than 1000 J per 100 m travelled” |
R3 | “The speed with which the UUV travels should be maximised” |
R4 | “The energy consumed by the UUV sensors should be minimised” |
ID | UUV_Medium | UUV_Large | FX_Small | FX_Medium |
---|---|---|---|---|
C1 |
\(r_1\leftrightarrow , \ldots , r_5\leftrightarrow \)
|
\(r_1\leftrightarrow , \ldots ,r_9\leftrightarrow \)
|
\(r_{11}\!\!\!\leftrightarrow , \ldots , \)
\(r_{61}\!\!\!\leftrightarrow \)
\(t_{11}\!\leftrightarrow , \ldots ,\)
\(t_{61}\leftrightarrow \)
|
\(r_{11}\!\!\!\leftrightarrow , \ldots ,\)
\(r_{64}\!\!\!\leftrightarrow \)
\(t_{11}\!\leftrightarrow , \ldots ,\)
\(t_{64}\leftrightarrow \)
|
C2 |
\(r_1\leftrightarrow ,\ldots ,r_5\leftrightarrow \)
|
\(r_1\leftrightarrow ,\ldots ,r_9\leftrightarrow \)
|
\(r_{11}\!\!\!\leftrightarrow , \ldots ,\)
\(r_{61}\!\!\!\leftrightarrow \)
\(t_{11}\!\leftrightarrow , \ldots ,\)
\(t_{61}\leftrightarrow \)
|
\(r_{11}\!\!\!\leftrightarrow , \ldots ,\)
\(r_{64}\!\!\!\leftrightarrow \)
\(t_{11}\!\leftrightarrow , \ldots ,\)
\(t_{64}\leftrightarrow \)
|
C3 | \(r_1\!\downarrow \), \(r_5\!\downarrow \) | \(r_1\!\downarrow \), \(r_4\!\downarrow \) \(r_9\!\downarrow \) | \(r_{11}\!\downarrow \), \(r_{13}\!\downarrow \) | \(r_{11}\!\downarrow \), \(r_{13}\!\downarrow \), \(r_{14}\!\downarrow \) |
C4 | \(r_1\!\leftrightarrow \), \(r_5\!\leftrightarrow \) | \(r_1\!\leftrightarrow \), \(r_4\!\leftrightarrow \) \(r_9\!\leftrightarrow \) | \(r_{11}\!\leftrightarrow \), \(r_{13}\!\leftrightarrow \) | \(r_{11}\!\leftrightarrow \), \(r_{13}\!\leftrightarrow \), \(r_{14}\!\leftrightarrow \) |
C5 | \(r_2\!\downarrow \), \(r_4\!\downarrow \) | \(r_2\!\downarrow \), \(r_4\!\downarrow \), \(r_8\!\downarrow \), \(r_{10}\!\downarrow \) | \(r_{21}\!\downarrow \), \(r_{22}\!\downarrow \) | \(r_{21}\!\downarrow \), \(r_{22}\!\downarrow \), \(r_{24}\!\downarrow \) |
C6 | \(r_2\!\leftrightarrow \), \(r_4\!\leftrightarrow \) | \(r_2\!\!\leftrightarrow \), \(r_4\!\leftrightarrow \), \(r_8\!\leftrightarrow \), \(r_{10}\!\leftrightarrow \) | \(r_{21}\!\leftrightarrow \), \(r_{22}\!\leftrightarrow \) | \(r_{21}\!\leftrightarrow \), \(r_{22}\!\leftrightarrow \), \(r_{24}\!\leftrightarrow \) |
C7 |
\(r_2\!\downarrow \)
| \(r_8\!\downarrow \), \(r_{10}\!\downarrow \) | \(r_{11}\!\downarrow \), \(r_{13}\!\downarrow \) | \(r_{11}\!\downarrow \), \(r_{13}\!\downarrow \), \(r_{14}\!\downarrow \) |
C8 |
\(r_2\!\leftrightarrow \)
| \(r_8\!\leftrightarrow \), \(r_{10}\!\leftrightarrow \) | \(r_{11}\!\leftrightarrow \), \(r_{13}\!\leftrightarrow \) | \(r_{11}\!\leftrightarrow \), \(r_{13}\!\leftrightarrow \), \(r_{14}\!\leftrightarrow \) |
C9 | \(r_1\!\downarrow \), \(r_5\!\downarrow \) | \(r_1\!\downarrow \), \(r_5\!\downarrow \) \(r_9\!\downarrow \) | \(t_{41}\!\uparrow \), \(t_{42}\!\uparrow \) | \(t_{41}\!\uparrow \), \(t_{42}\!\uparrow \), \(t_{44}\!\uparrow \) |
C10 | \(r_1\!\leftrightarrow \), \(r_5\!\leftrightarrow \) | \(r_1\!\leftrightarrow \), \(r_5\!\leftrightarrow \) \(r_9\!\leftrightarrow \) | \(t_{41}\!\leftrightarrow \), \(t_{42}\!\leftrightarrow \) | \(t_{41}\!\leftrightarrow \), \(t_{42}\!\leftrightarrow \), \(t_{44}\!\leftrightarrow \) |
C11 | \(r_1\!\downarrow \), \(r_3\!\downarrow \), \(r_5\!\downarrow \) | \(r_1\!\downarrow \), \(r_3\!\downarrow \), \(r_5\!\downarrow \) \(r_7\!\downarrow \), \(r_9\!\downarrow \), \(r_{10}\!\downarrow \) | \(t_{51}\!\uparrow \), \(t_{52}\!\downarrow \) | \(t_{51}\!\uparrow \), \(t_{52}\!\uparrow \), \(t_{53}\!\uparrow \) |
C12 | \(r_1\!\leftrightarrow \), \(r_3\!\leftrightarrow \), \(r_5\!\leftrightarrow \) | \(r_1\!\leftrightarrow \), \(r_3\!\leftrightarrow \), \(r_5\!\leftrightarrow \) \(r_7\!\leftrightarrow \), \(r_9\!\leftrightarrow \), \(r_{10}\!\leftrightarrow \) | \(t_{51}\!\leftrightarrow \), \(t_{52}\!\leftrightarrow \) | \(t_{51}\!\leftrightarrow \), \(t_{52}\!\leftrightarrow \), \(t_{53}\!\leftrightarrow \) |
C13 | \(r_{11}\!\downarrow \), \(r_{12}\!\downarrow \), \(r_{21}\!\downarrow \), \(r_{22}\!\downarrow \), \(r_{31}\!\downarrow \), \(r_{33}\!\downarrow \), \(r_{42}\!\downarrow \), \(r_{43}\!\downarrow \) | \(r_{11}\!\downarrow \), \(r_{12}\!\downarrow \), \(r_{13}\!\downarrow \), \(r_{21}\!\downarrow \), \(r_{22}\!\downarrow \), \(r_{31}\!\downarrow \), \(r_{33}\!\downarrow \), \(r_{43}\!\downarrow \), \(r_{44}\!\downarrow \) \(r_{51}\!\downarrow \), \(r_{52}\!\downarrow \), \(r_{54}\!\downarrow \) \(r_{62}\!\downarrow \), \(r_{64}\!\downarrow \) |
7.2.3 Evaluation methodology
7.2.4 Results and discussion
Strategies | C4 | C11 | ||||||
---|---|---|---|---|---|---|---|---|
1000 | 2000 | 3000 | 4000 | 1000 | 2000 | 3000 | 4000 | |
FX_Small | ||||||||
RS vs PGA | PGA(L) | PGA(L) | PGA(L) | PGA(L) | PGA(L) | PGA(L) | PGA(L) | PGA(L) |
PGA vs LRGA | LRGA(L) | LRGA(M) | LRGA(M) | LRGA(S) | LRGA(L) | LRGA(L) | LRGA(L) | LRGA(M) |
PGA vs CRGA | CRGA(L) | CRGA(S) | – | – | – | – | – | – |
LRGA vs CRGA | – | – | – | – | LRGA(L) | LRGA(L) | LRGA(L) | LRGA(L) |
FX_Medium | ||||||||
RS vs PGA | PGA(L) | PGA(L) | PGA(L) | PGA(L) | PGA(L) | PGA(L) | PGA(L) | PGA(L) |
PGA vs LRGA | LRGA(L) | LRGA(M) | LRGA(S) | – | LRGA(L) | LRGA(M) | LRGA(S) | – |
PGA vs CRGA | CRGA(M) | CRGA(S) | – | – | – | – | – | – |
LRGA vs CRGA | LRGA(S) | LRGA(S) | LRGA(S) | LRGA(S) | – | – | – | – |