## 2 The Constrained Multi-Objective Component Deployment Problem
### Reliability Objective  
To model the possible states of a software execution system and the probability of transiting from one state to another, a Discrete Time Markov Chain (DTMC) [8] is used. Essentially, the execution begins at an _initial state_ and terminates either with _successful_ completion or _failure_. Mathematically, a DTMC can be represented as an ordered tuple \((S,s_{0},P)\) where, \(S\) is a finite set of states, \(s_{0}\in S\) is the _initial state_, and \(P:S\times S\rightarrow[0,1]\) is the transition probability matrix, where \(P(s,s^{\prime})\) denotes the probability of changing from state \(s\) to state \(s^{\prime}\). In a DTMC, \(\sum\limits_{s^{\prime}\in S}P(s,s^{\prime})=1\) for all states \(s\in S\), which requires that terminal states also have transition probabilities to themselves. In modelling a software system as DTMC, the execution is considered as a path thorough the states of the DYMC. DTMC models are characterised by the behavioural specifications of a software embedded system such that a vertex represents the execution of one software component and edges denote the transition of execution from one software component to another. _Super-initial_ vertices represent the beginning of execution, and edges are added from these vertices weighted with corresponding execution initialisation probabilities (\(q\)). The model presumes that the failure of components occur independently and the reliability of the component \(c_{i}\) is specified by the failure frequency rate \(f_{i}\), associated with a component functioning correctly:  
\[R_{i}=e^{-f_{\mathsf{d}(c_{i})}\cdot\frac{w_{c_{i}}}{\mathsf{s}\mathsf{d}(c_{ i})}}, \tag{1}\]  
where \(\mathsf{d}(c_{i})\) is the hardware host where component \(c_{i}\) is allocated, \(f_{\mathsf{d}(c_{i})}\) is its failure rate, \(w_{c_{i}}\) is component \(c_{i}\)'s computational requirement expressed in MI (or million instructions) and \(s_{\mathsf{d}(c_{i})}\) the instruction-processing capacity of hardware unit \(\mathsf{d}(c_{i})\) expressed in MILPS (million instructions per second). For a communication element, the reliability is computed by the failure rates of the network  
Figure 1: An example of the component deployment problem. The hardware units. links and the amount time spent for communication, defined in Equation (2) as a function of the communication link data rates \(r\) and data sizes \(d\) required for components \(c_{i}\) and \(c_{j}\) to interact. \[R_{ij}=e^{-f_{d(c_{i})d(c_{j})}\cdot\frac{d_{ij}}{r_{\mathbf{d}(c_{i}),\mathbf{d }(c_{j})}}}. \tag{2}\]  
The expected number of visits of a DTMC node, expressed in Equation (3), with \(q_{i}\) denoting the probability that the execution of a system starts from component \(c_{i}\), quantifies the expectation of a component \(v:\mathcal{C}\rightarrow\mathbb{R}_{\geq 0}\) being used during a single system execution. \[v_{i}=q_{i}+\sum_{j\in\mathcal{I}}v_{j}\cdot p_{ji}. \tag{3}\]  
The transition probabilities \(p_{ij}\) can be expressed in a matrix form \(P_{n\times n}\). In similar fashion, the initialization probabilities \(q_{i}\) can be represented by matrix \(Q_{n\times 1}\). The expected number of visits for all components \(V_{n\times 1}\) can be written as:  
\[V=Q+P^{T}\cdot V. \tag{4}\]  
Equation (4) can be expressed as:  
\[V=(I-P^{T})^{-1}\times Q, \tag{5}\]  
where \(I\) denotes the identity matrix. For a DTMC with absorbing states, the inverse matrix \((I-P^{T})^{-1}\) always exists [8], which guaranties the existence of vector \(V\). The expected number of visits associated with network links \(v_{l}:\mathcal{C}\times\mathcal{C}\rightarrow\mathbb{R}_{\geq 0}\) is calculated by \(v_{l}(c_{i},c_{j})=v_{i}\cdot p_{ij}\), where \(v_{l}(c_{i},c_{j})\) denotes the expected number of occurrences of the transition \((c_{i},c_{j})\).