\documentclass{acm_proc_article-sp} \begin{document} \title{On the Computational Complexity of \\ Designing and Reconfiguring \\ Component-based Software Systems} %\subtitle{[Extended Abstract]} \numberofauthors{2} \author{ \alignauthor Todd Wareham \titlenote{Corresponding Author} \\ \affaddr{Department of Computer Science} \\ \affaddr{Memorial University of Newfoundland}\\ \affaddr{St.\ John's, NL Canada}\\ \email{harold@mun.ca} \alignauthor Marieke Sweers \\ \affaddr{Radboud University Nijmegen} \\ \affaddr{Donders Institute for Brain, Cognition, and Behaviour} \\ \affaddr{Nijmegen, The Netherlands} \email{marieke.sweers@gmail.com} } \maketitle \begin{abstract} Though Component-Based Development (CBD) is a popular approach to mitigating the costs of creating software systems, it is not clear to what extent CBD is preferable to other approaches to software engineering or to what extent the core component selection and adaptation activities of CBD can be implemented to operate without human intervention in an efficient and reliable manner. In this paper, we use computational complexity analysis to compare the computational characteristics of software system design and reconfiguration by {\em de novo} design, component selection, and component selection with adaptation. Our results show that none of these approaches can be implemented to operate both efficiently and reliably either in general or relative to a surprisingly large number of restrictions on software system, component, and component library structure. We also give the first restrictions under which all of these approaches can be implemented to operate both efficiently and reliably. \end{abstract} % A category with the (minimum) three required fields \category{D.2.13}{Software Engineering}{Resuable Software}[Reuse models] \category{D.2.2}{Software Engineering}{Design Tools and Techniques} \category{F.2.2}{Analysis of Algorithms and Problem Complexity}{Nonnumerical algorithms and problems}[computations on discrete structures] %A category including the fourth, optional field follows... \terms{Algorithms, Design, Measurement, Performance, Theory} \keywords{component-based development, parameterized computational complexity} % NOT required for Proceedings \newcommand{\lb}{} \newcommand{\la}{\langle} \newcommand{\ra}{\rangle} \newcommand{\nolb}{\nolinebreak} \newtheorem{theorem}{Theorem} \newtheorem{lemma}{Lemma} \newdef{definition}{Definition} \section{Introduction} \label{SectIntro} Component-based development (CBD) is a popular approach to mitigating the monetary and time costs of creating and maintaining software systems \cite{AF97,Bro00,HC01}. In CBD, previously-developed software modules called components are stored in libraries and connected together (possibly with some adaptation of the component code and architecture) as needed to generate new software systems from given requirements. Over the last 20 years, a number of technologies have been implemented to assist human programmers in creating com- ponent-based systems, {\em e.g.}, CORBA, CCM, EJB, COM+, and much effort has been put into automating the key CBD activities of component selection and adaptation. There are two ongoing issues of great importance in the CBD community: (1) the circumstances (if any) under which the cost of selecting and adapting components is less than the cost of developing software systems from scratch, {\em i.e.}, {\em de novo} \cite{GT05} and (2) the need for CBD to operate fully automatically and efficiently to accommodate ubiquitous and autonomic computing systems which need to create and reconfigure software without or with minimal human intervention at runtime \cite{FK05,MV14}. To address these issues, it would be most useful to know if efficient and reliable methods are available for selecting and adapting components in CBD and, if so, under what circumstances these methods outperform other approaches to software engineering. In this paper, we present results addressing both of these questions. First, using computational complexity analysis \cite{GJ79}, we show that both creating and reconfiguring software systems either by {\em de novo} design, component selection, or component selection with adaptation are all $NP$-hard and thus intractable in general. % This holds even % in the case of basic software system, component, and component library % models. Second, using parameterized complexity analysis \cite{DF13}, we give restrictions under which all of these activities are tractable and prove that surprisingly few restrictions on either software system structure or the allowable degree of adaptation render these activities tractable. Though these results are derived relative to basic models of software systems and components, we show that they also apply to more realistic models. The remainder of this paper is organized as follows. In Section \ref{SectFormCBS}, we present our software system, component, and component library models and formalize the problems of {\em de novo} and component-based software system design and reconfiguration relative to these models. Section \ref{SectCIRes} demonstrates the intractability of all of these problems in general. Section \ref{SectTCM} describes a methodology for identifying conditions for tractability, which is then applied in Section \ref{SectTCRes} to identify such conditions for our problems. In order to accommodate conference page limits and focus in the main text on the implications of our results for CBD, proofs of selected results are given in Appendix \ref{AppProof}. Finally, our conclusions and directions for future work are given in Section \ref{SectConc}. \subsection{Related Work} Computational complexity analyses of the component selection problem have been done previously \cite{BBR05, PO99,PWM03}. However, the formalizations used in these analyses focused on the satisfaction of sets of desired system objectives, and did not include specifications of software system and component structure that are detailed enough to investigate the conditions under which restrictions on these structures would make component selection tractable. They also did not address the issue of component adaptation. \section{Formalizing Component-based \\ Design and Reconfiguration} \label{SectFormCBS} Our goal in this paper is to assess whether or not component-based development has advantages over conventional software engineering relative to different activities in the software life cycle. This assessment can be stated most simply along two dimensions: \begin{enumerate} \item{ \textit{Software design mode}: creating software using only components drawn from component libraries versus creating software by adapting components drawn from component libraries or creating software {\em de novo} that is organized in a specified component-like fashion. } \item{ \textit{Software lifecycle activity}: designing the initial version of a software system relative to a set of requirements versus reconfiguring an existing system to accommodate one or more changes to the requirements. } \end{enumerate} \noindent The possibilities implicit in these dimensions result in the following six informal computational problems: \noindent {\sc Software Design} \\ {\em Input}: Software requirements $R$, software-structure specification $X$ \\ {\em Output}: A software system $S$ whose structure is consistent with $X$ and whose operation satisfies $R$. \noindent {\sc Software Design from Adapted Components} \\ {\em Input}: Software requirements $R$, a set of software-component libraries $\cal{C}$ $= \{C_1, C_2, \ldots, C_{|C|}\}$. \\ {\em Output}: A software system $S$ whose structure consists of connected components derived from components drawn from the libraries in $\cal{C}$ and whose operation satisfies $R$. \noindent {\sc Software Design from Components} \\ {\em Input}: Software requirements $R$, a set of software-component libraries $\cal{C}$ $= \{C_1, C_2, \ldots, C_{|C|}\}$. \\ {\em Output}: A software system $S$ whose structure consists of connected components drawn from the libraries in $\cal{C}$ and whose operation satisfies $R$. \noindent {\sc Software Reconfiguration} \\ {\em Input}: A software system $S$ whose structure is consistent with specification $X$ and whose operation satisfies requirements $R$, new software requirements $R_{new}$. \\ {\em Output}: A software system $S'$ derived from $S$ whose structure is consistent with $X$ and whose operation satisfies $R \cup R_{new}$. \noindent {\sc Software Reconfiguration from \\ Adapted Components} \\ {\em Input}: A software system $S$ whose structure consists of connected components from a set of software-component libraries $\cal{C}$ $= \{C_1, C_2, \ldots, C_{|C|}\}$ and whose operation satisfies requirements $R$, new software requirements $R_{new}$. \\ {\em Output}: A software system $S'$ derived from $S$ whose structure consists of connected components derived from components drawn from the libraries in $\cal{C}$ and whose operation satisfies $R \cup R_{new}$. \noindent {\sc Software Reconfiguration from Components} \\ {\em Input}: A software system $S$ whose structure consists of connected components from a set of software-component libraries $\cal{C}$ $= \{C_1, C_2, \ldots, C_{|C|}\}$ and whose operation satisfies requirements $R$, new software requirements $R_{new}$. \\ {\em Output}: A software system $S'$ derived from $S$ whose structure consists of connected components drawn from the libraries in $\cal{C}$ and whose operation satisfies $R \cup R_{new}$. To assess the computational difficulty of and (if necessary) explore algorithmic options for efficiently solving these problems, we need formalizations of all of the entities comprising these problems. There is a vast existing literature on various types of software requirements, system-structures, structure specifications, and components and component libraries. We want to avoid introducing spurious computational difficulty due to powerful formalisms, as this would complicate the interpretation our results. Hence, we shall choose the simplest such formalizations\footnote{ These formalizations are based on those developed in \cite{OS+15,Swe15} to analyze the computational complexity of the adaptive toolbox theory of human decision-making \cite{GT99}. } (additional advantages gained by such a parsimonious approach are given in Section \ref{SectGenRes}): \begin{figure}[t] % \begin{center} \begin{tabular}{| c || c | c | c | c | c || c |} \hline req.\ & $i_1$ & $i_2$ & $i_3$ & $i_4$ & $i_5$ & action \\ \hline\hline $r_1$ & T & T & T & T & T & $a_2$ \\ \hline $r_2$ & T & F & F & F & T & $a_1$ \\ \hline $r_3$ & F & F & F & F & F & $a_2$ \\ \hline $r_4$ & F & F & F & F & F & $a_2$ \\ \hline $r_5$ & T & T & T & F & T & $a_3$ \\ \hline \end{tabular} \\ \vspace*{0.05in} (a) \vspace*{0.05in} {\tt \begin{tabular}{l l} procedure p1: & procedure p2 \\ ~ if $i_4$ then $a_2$ & ~ if $\neg i_2$ then $a_1$ \\ ~ else if $\neg i_3$ then $a_1$ & ~ else if $\neg i_4$ then $a_2$ \\ ~ else if $i_5$ then $a_3$ & ~ else $a_3$ \\ ~ else $a_1$ & \\ & \\ procedure p3: & procedure p4: \\ ~ if $i_4$ then $a_2$ & ~ $a_2$ \\ ~ else $a_2$ & \\ \end{tabular} } \\ \vspace*{0.05in} (b) \vspace*{0.05in} {\tt \begin{tabular}{l l} selector s1: & selector s2: \\ ~ if $i_1$ then ??? & ~ if * then ??? \\ ~ else if $i_5$ then ??? & \\ ~ else ??? & \\ \end{tabular} } \vspace*{0.05in} (c) \vspace*{0.05in} {\tt \begin{tabular}{l l} system S1: & system S2: \\ ~ if $i_1$ then call p1 & ~ if * then call p2 \\ ~ else if $i_5$ then call p3 & \\ ~ else call p4 & \\ \end{tabular} } \vspace*{0.05in} (d) \end{center} \caption{ Example Requirements, Procedures, Selectors, and Software Systems. (a) Software requirements $R = \{r_1, r_2, r_3, r_4, r_5\}$ defined on situation-variables $I = \{i_1, i_2, i_3, i_4, i_5\}$ and action-set $A = \{a_1, a_2, a_3\}$. (b) Four procedures. (c) Two selectors as they would appear in a selector-component library with blank procedure calls. (d) Two software systems created by instantiating the procedure-calls in the selectors from (c) with procedures from (b). } % \label{FigCSS} \end{figure} \begin{itemize} \item{ \textit{Software Requirements}: The requirements will be a set $R = \{r_1, r_2, \ldots r_{|R|}\}$ of situation-action pairs where each pair $r_j (s_j,a_j)$ consists of a situation $s_j$ defined by a particular set of truth-values $s_j = \langle v(i_1), v(i_2), \ldots$ $v(i_{|I|})\rangle$, $v(i_k) \in \{True, False\}$, relative to each of the Boolean variables $i_k$ in set $I = \{i_1, i_2, \ldots, i_{|I|}\}$ and an action $a_j$ from set $A = \{a_1, a_2, \ldots a_{|A|}\}$. } \item{ \textit{Software system-structure}: We will here consider the simplest possible complex structure consisting of a multiple \texttt{IF-THEN-ELSE} statement block (a {\bf selector}) whose branches are in turn other \texttt{IF-THEN-ELSE} statement blocks ({\bf procedures}) whose branches execute actions from $A$. Each selector and procedure \texttt{IF-THEN} condition is a Boolean formula that is either a variable from $I$ {\em e.g.}, $i_j$, or its negation, {\em e.g.}, $\neg i_j$. Each selector and procedure with one or more situation-variable conditions terminates in a final \texttt{ELSE} statement. In addition, the selector may consist of single special statement \texttt{IF * THEN} which evaluates to $True$ in all cases (the default selector) and a procedure may consist of a single executed action; such selectors and procedures have no associated conditions. } \item{ \textit{Software components and component libraries}: Two-level software systems of the form above consist of two types of components, selectors and procedures, which shall be stored in libraries $L_{sel}$ and $L_{prc}$, respectively. } \item{ \textit{Software structure specification}: The basic characteristics of two-level software systems of the form above are the situation-variable and action sets on which they are based ($I$ and $A$), the maximum number of conditions allowed in the selector ($|sel|$) and the maximum number of conditions allowed in any procedure ($|prc|$). } \end{itemize} \noindent Examples of these entities are given in Figure \ref{FigCSS}. \noindent This allows us to formalize various actions and properties in the problems given above as follows: \begin{itemize} \item A software system $S$ is consistent with a structure-specification $X = \langle I, A, |sel|, |prc|\rangle$ if it has the two-level structure described above where \texttt{IF-THEN} conditions are (un)negated members of $I$, all procedure-executed actions are drawn from $A$, the number of conditions in the selector is at most $|sel|$ , and the number of conditions in each procedure is at most $|prc|$. For example, both software-systems in Figure \ref{FigCSS}(d) are consistent with $X = \{ \{i_1, i_2, i_3, i_4, i_5\}, \{a_1, a_2, a_3\}, 2, 3\}$. \item A software system $S$ is constructed from components drawn from $\cal{C}$ $= \{C_{sel}, C_{prc}\}$ if the selector-component is from $C_{sel}$ and each procedure-component is from $C_{prc}$. Note that a member of $C_{prc}$ may appear zero, one, or more times in $S$. For example, both software systems in Figure \ref{FigCSS}(d) are constructed from $\cal{C}$ $= \{\{{\tt s1, s2}\}, \{{\tt p1, p2, p3, p4}\}\}$. \item The operation of a software system $S$ satisfies requirements $R$ if for each situation-action pair $(s,a)$ in $R$, the execution of $S$ relative to the truth-settings in $s$ results in the execution of $a$. For example, software system {\tt S1} in Figure \ref{FigCSS}(d) satisfies the requirements in Figure \ref{FigCSS}(a) but software system {\tt S2} does not (because it produces different outputs ($a_3$, $a_1$, $a_1$, and $a_2$ respectively) for requirements $r_1$, $r_3$, $r_4$, and $r_5$). \end{itemize} \vspace*{-0.08in} %Given all this, we can now state the following formal versions of the six %problems given at the beginning of this section: We can now state the following formal problems: \noindent {\sc Software Design} (SDes-Spec) \\ {\em Input}: Software-structure specification $X = \langle I, A, |sel|, |prc|\rangle$, software requirements $R$ based on sets $I$ and $A$. \\ {\em Output}: A software system $S$ whose structure is consistent with $X$ and whose operation satisfies $R$, if such an $S$ exists, and special symbol $\bot$ otherwise. \noindent {\sc Software Design from \\ Adapted Components} (SDes-CompA) \\ {\em Input}: Software requirements $R$ based on sets $I$ and $A$, a set of software-component libraries $\cal{C}$ $= \{C_{sel}, C_{prc}\}$, positive integers $d, c_c \geq 0$. \\ {\em Output}: A software system $S$ whose structure consist of connected components derived by at most $c_c$ changes to at most $d$ components drawn from the libraries in $\cal{C}$ and whose operation satisfies $R$, if such an $S$ exists, and special symbol $\bot$ otherwise. \noindent {\sc Software Design from Components} (SDes-Comp) \\ {\em Input}: Software requirements $R$ based on sets $I$ and $A$, a set of software-component libraries $\cal{C}$ $= \{C_{sel}, C_{prc}\}$, a positive integer $d \geq 0$. \\ {\em Output}: A software system $S$ whose structure consist of connected components based on at most $d$ components drawn from the libraries in $\cal{C}$ and whose operation satisfies $R$, if such an $S$ exists, and special symbol $\bot$ otherwise. \noindent {\sc Software Reconfiguration} (SRec-Spec) \\ {\em Input}: A software system $S$ whose structure is consistent with specification $X = \langle I, A, |sel|, |prc|\rangle$ and whose operation satisfies requirements $R$, a set $R_{new}$ of new situation-action pairs based on $I$ and $A$, a positive integer $c_c \geq 0$. \\ {\em Output}: A software system $S'$ derived by at most $c_c$ changes to $S$ whose structure is consistent with $X$ and whose operation satisfies $R \cup R_{new}$, if such an $S'$ exists, and special symbol $\bot$ otherwise. \noindent {\sc Software Reconfiguration from \\ Adapted Components} (SRec-CompA) \\ {\em Input}: A software system $S$ whose structure consists of connected components from a set of software-component libraries $\cal{C}$ $= \{C_{sel}, C_{prc}\}$ and whose operation satisfies requirements $R$, a set $R_{new}$ of new situation-action pairs based on $I$ and $A$, positive integers $c_l, c_c, d \geq 0$. \\ {\em Output}: A software system $S'$ derived from $S$ by at most $c_l$ component-changes relative to the libraries in $\cal{C}$ and $c_c$ code-changes whose structure consist of at most $d$ types of connected components and whose operation satisfies $R \cup R_{new}$, if such an $S'$ exists, and special symbol $\bot$ otherwise. \noindent {\sc Software Reconfiguration from \\ Components} (SRec-Comp) \\ {\em Input}: A software system $S$ whose structure consists of connected components from a set of software-component libraries $\cal{C}$ $= \{C_{sel}, C_{prc}\}$ and whose operation satisfies requirements $R$, a set $R_{new}$ of new situation-action pairs based on $I$ and $A$, positive integers $c_l, d \geq 0$. \\ {\em Output}: A software system $S'$ derived from $S$ by at most $c_l$ component-changes relative to the libraries in $\cal{C}$ whose structure consists of at most $d$ types of connected components and whose operation satisfies $R \cup R_{new}$, if such an $S'$ exists, and special symbol $\bot$ otherwise. \noindent We have included parameter $d$ in all component-based problems to allow control over the number of retrievals from libraries. The two types of adaptation and reconfiguration changes are: (1) changes to the system code: changing the condition in or action executed by any \texttt{IF-THEN-ELSE} statement ($c_c$) and (2) changes to the system component-set: using a different selector-component from $C_{sel}$ or changing any used procedure-component to another from $C_{prc}$ ($c_l$). Note in the case of a selector-change, both the original and new selector must have the same number of \texttt{IF-THEN} statements and the procedures called by the original selector are mapped to the corresponding positions in the new selector. \section{Component-based Design and Reconfiguration are Intractable} \label{SectCIRes} % In this section, we address whether or not component-based design % and reconfiguration % can be done efficiently relative to the model described in Section % \ref{SectFormCBS}. Following general practice in Computer Science \cite{GJ79}, we define tractability as being solvable in the worst case in time polynomially bounded in the input size. We show that a problem is not polynomial-time solvable, {\em i.e.}, not in the class $P$ of polynomial-time solvable problems, by proving it to be at least as difficult as the hardest problems in problem-class $NP$ (see \cite{GJ79} for details). \noindent {\em Result A}: SDes-Spec, SDes-CompA, SDes-Comp, SRec-Spec, SRec-CompA, and SRec-Comp are $NP$-hard. \noindent Modulo the conjecture $P \neq NP$ which is widely believed to be true \cite{For09}, the above shows that even the basic versions of component-based design and reconfiguration considered here are not solvable in polynomial time. This $NP$-hardness hold for problems SRec-Spec and SRec-CompA when the new requirements consist of a single situation-action pair. Two frequently-adopted responses to intractability are to consider poly-time algorithms which generate solutions that (1) approximate within provable bounds the wanted solutions, {\em e.g.}, software systems whose structure are close to the values specified in $X$ or which satisfy a large proportion of the requirements in $R$ \cite{NH08}, or (2) are of acceptable quality most of the time, {\em e.g.}, genetic or simulated annealing algorithms \cite{HMZ12}. In the remainder of this paper, we will consider a third option described in more detail in the next section. \section{A Method for Identifying \\ Tractability Conditions} \label{SectTCM} A computational problem that is intractable for unrestricted inputs may yet be tractable for non-trivial restrictions on the input. This insight is based on the observation that some $NP$-hard problems can be solved by algorithms whose running time is polynomial in the overall input size and non-polynomial only in some aspects of the input called \textbf{parameters}. %In other words, the main part of the input contributes %to the overall complexity in a ``good'' way, whereas only the parameters contribute % to the overall complexity in a ``bad'' way. In such cases, the problem $\Pi$ is said to %be fixed-parameter tractable for that respective set of parameters. The The following states this idea more formally. \vspace*{-0.1in} \begin{definition} Let $\Pi$ be a problem with parameters $k_1, k_2,$ $\ldots$. Then $\Pi$ is said to be {\bf fixed-parameter (fp-) tractable} for parameter-set $K = \{k_1, k_2, ...\}$ if there exists at least one algorithm that solves $\Pi$ for any input of size $n$ in time $f(k_1, k_2, ...)n^c$, where $f(\cdot)$ is an arbitrary function and $c$ is a constant. If no such algorithm exists then $\Pi$ is said to be {\bf fixed-parameter (fp-) intractable} for parameter-set $K$. % \label{DefFPT} \end{definition} \vspace*{-0.1in} \noindent In other words, a problem $\Pi$ is fp-tractable for a parameter-set $K$ if all superpolynomial-time complexity inherent in solving $\Pi$ can be confined to the parameters in $K$. % In this sense the ``unbounded" nature of the parameters in $K$ can be % seen as a reason for the intractability of the unconstrained version of $\Pi$. There are many techniques for designing fp-tractable algorithms \cite{CF+15,DF13}, and fp-intractability is established in a manner analogous to classical polynomial-time intractability by proving a parameterized problem is at least as difficult as the hardest problems in one of the problem-classes in the $W$-hierarchy $\{W[1], W[2], ...\}$ (see \cite{DF13} for details). Additional results are typically implied by any given result courtesy of the following lemmas: \vspace*{-0.1in} \begin{lemma} \cite[Lemma 2.1.30]{War99} If problem $\Pi$ is fp-tractable relative to parameter-set $K$ then $\Pi$ is fp-tractable for any parameter-set $K'$ such that $K \subset K'$. % \label{LemProp1} \end{lemma} \vspace*{-0.1in} \begin{lemma} \cite[Lemma 2.1.31]{War99} If problem $\Pi$ is fp-intract-able relative to parameter-set $K$ then $\Pi$ is fp-intractable for any parameter-set $K'$ such that $K' \subset K$. % \label{LemProp2} \end{lemma} \vspace*{-0.1in} It follows from the definition of fp-tractability that if an intractable problem $\Pi$ is fp-tractable for parameter-set $K$, then $\Pi$ can be efficiently solved even for large inputs, provided only that the values of all parameters in $K$ are relatively small. This strategy has been successfully applied to many intractable problems (see \cite{DF13,Ste12} and references). In the next section we show how this strategy may be used to render component-based design and reconfiguration tractable. \section{What Makes Component-based \\ Design and Reconfiguration \\ Tractable?} \label{SectTCRes} Our component-based software design and reconfiguration problems have a number of parameters whose restriction could render these problems tractable in the sense defined in Section \ref{SectTCM}. An overview of the parameters that we considered in our fp-tractability analysis is given in Table \ref{TabPrm}. These parameters can be divided into three groups: \begin{table} \caption{Parameters for Component-based Design and Reconfiguration Problems} \label{TabPrm} \centering \begin{tabular}{| c || l | c |} \hline \hline Parameter & Description & Applicability \\ \hline $|I|$ & \# situation-variables & All \\ \hline $|A|$ & \# possible actions & All \\ \hline $|sel|$ & Max \# selector-conditions & All \\ \hline $|prc|$ & Max \# procedure-conditions & All \\ \hline $d$ & Max \# component-types & *-CompA, \\ & ~~ in software system & *-Comp \\ \hline\hline $|L_{sel}|$ & \# selector-components & *-CompA, \\ & ~~ in selector-library & *-Comp \\ \hline $|L_{prc}|$ & \# procedure-components & *-CompA, \\ & ~~ in procedure-library & *-Comp \\ \hline\hline $|R_{new}|$ & \# new requirements & SRec-* \\ \hline $c_c$ & Max \# code-changes & *-CompA, \\ & ~~ allowed & SRec-Spec \\ \hline $c_l$ & Max \# component-changes & SRec-CompA, \\ & ~~ allowed & SRec-Comp \\ \hline \end{tabular} \end{table} \vspace*{-0.15in} \begin{enumerate} \item Restrictions on system and component structure \\ ($|I|$, $|A|$, $|sel|$, $|prc|$, $d$); \item Restrictions on component libraries structure \\ ($|L_{sel}|$, $|L_{prc}|$); and \item restrictions on reconfigurability ($|R_{new}|, c_c$, $c_l$). \end{enumerate} \vspace*{-0.15in} \noindent We will assess the fixed-parameter tractability of our problems relative to the parameters in Table \ref{TabPrm} (Section \ref{SectCBSRes}), show how these results apply in more general settings (Section \ref{SectGenRes}), and discuss the implications of these results for component-based development (Section \ref{SectDisc}). \subsection{Results} \label{SectCBSRes} Our parameterized intractability results are as follows: \noindent \textit{Result B}: SDes-Spec is $W[2]$-hard for $\{ |A|, |sel|, |prc| \}$ when $|A| = 2$ and $|sel| = 0$. \noindent \textit{Result C}: SDes-CompA is $W[2]$-hard for $\{ |A|, |sel|, |prc|, d,$ $|L_{sel}|, |L_{prc}|, c_c \}$ when $|A| = d = 2$, $|sel| = 0$, $|L_{sel}| = |L_{prc}| = 1$. \noindent \textit{Result D}: SDes-Comp is $W[2]$-hard for $\{ |A|, d, |L_{sel}| \}$ when $|A| = 2$ and $|L_{sel}| = 1$. \noindent \textit{Result E}: SRec-Spec is $W[2]$-hard for $\{ |A|, |sel|, |prc|, |R_{new}|, c_c \}$ when $|A| = 3$, $|sel| = 0$, and $|R_{new}| = 1$. \noindent \textit{Result F}: SRec-CompA is $W[2]$-hard for $\{ |A|, |sel|, |prc|, d,$ $|L_{sel}, |L_{prc}|, |R_{new}|, c_l, c_c \}$ when $|A| = 3$, $|R_{new}| = |L_{sel}| = |L_{prc}| = 1$, $d = 2$, and $|sel| = c_l = 0$. \noindent \textit{Result G}: SRec-Comp is $W[2]$-hard for $\{ |A|, d, |L_{sel}| \}$ when $|A| = 3$ and $|L_{sel}| = 1$. \noindent At present, we have the following fp-tractability results: \noindent \textit{Result H}: SDes-Spec, SDes-CompA, SDes-Comp, SRec-Spec, SRec-CompA, and SRec-Comp are fixed-parameter tractable for $\{ |I| \}$. \noindent \textit{Result I}: SDes-Comp and SRec-Comp are fixed-parameter tractable for $\{ |sel|, |L_{prc}| \}$. \noindent Note that Results B, C, E, F, and H in combination with Lemmas \ref{LemProp1} and \ref{LemProp2} completely characterize the parameterized complexity of problems SDes-Spec, SDes-CompA, SRec-Spec, and SRec-CompA relative to the parameters in Table \ref{TabPrm}. % While we do not yet have such characterizations for problems % SDes-Comp and SRec-Comp, the results above are a first step in % this direction. \subsection{Generality of Results} \label{SectGenRes} Our intractability results, though defined relative to basic models of software requirements, software systems, components, and component libraries, have a broad applicability. Observe that the models for which these results hold are in fact restricted versions of more realistic alternatives, {\em e.g.}, \begin{itemize} \item software requirements that explicitly list all situations to which software should respond are a special case of more complex requirements which are based on compact specifications of software behaviour such as finite-state automata or statecharts and/or incorporate other required properties of software systems such as degree of reliability and response time; \item two-level selector / procedure software systems that act as simple functions are a special case of more complex persistent software systems whose components invoke each other in more complex manners; \item components consisting of a single condition-statement block procedure without input parameters or return values and which have no dependencies on other components are a special case of more complex components consisting of multiple data types and complex procedures which have dependencies on other components such as data-type sharing or inheritance; and \item component libraries that are simply lists of components are a special case of component libraries that incorporate component behaviour-specifications and / or metadata to aid in selection and adaptation. \end{itemize} \noindent Intractability results for these alternatives then follow from the observation that intractability results for a problem $\Pi$ also hold for any problem $\Pi'$ that has $\Pi$ as a special case (suppose $\Pi$ is intractable; if $\Pi'$ is tractable by algorithm $A$, then $A$ can be used to solve $\Pi$ efficiently, which contradicts the intractability of $\Pi$ --- hence, $\Pi'$ must also be intractable). Our fp-tractability results are much more fragile, as innocuous changes to software requirements, software system, component, or component library structure may in fact violate assumptions critical to the operation of the algorithms underlying these results. Hence, they may only apply to certain more complex models, and this needs to be assessed on a case-by-case basis. \subsection{Discussion} \label{SectDisc} We have found that designing and reconfiguring software systems by {\em de novo} design, component selection, and component selection with adaptation are all $NP$-hard (Result A). This implies that it is unlikely that deterministic polynomial-time methods exist for any of these problems. It also answers the question of which of {\em de novo} design, component selection, or component selection with adaptation is best for creating software systems -- computationally speaking, all three methods are equally good (or bad) in general. This $NP$-hardness has interesting additional implications. It is widely believed that $P = BPP$ \cite[Section 5.2]{Wig07} where $BPP$ is considered the most inclusive class of problems that can be efficiently solved using probabilistic methods (in particular, methods whose probability of correctness can be efficiently boosted to be arbitrarily close to probability one). Hence, our results also imply that unless $P = NP$, there are no probabilistic polynomial-time methods which correctly design or reconfigure software systems using the three approaches considered here with high probability for all inputs. Taken together, the above constitutes the first proof that {\em no} currently-used method (including search-based methods based on evolutionary algorithms (see \cite[Section 5]{HMZ12} and references) can guarantee both efficient and correct operation for all inputs for these problems. As described in Section \ref{SectTCM}, efficient correctness-guaranteed methods may yet exist relative to plausible restrictions on the input and output. It seems reasonable to conjecture that some restrictions relative to the parameters listed in Table \ref{TabPrm} should render these problems tractable. However, almost none of these restrictions or indeed many possible combinations of these restrictions can yield tractability, even when the parameters involved are restricted to very small constants (Results B--G). We do have some initial fp-tractability results (Results H and I). Taken together, our fp-results paint a disconcerting picture for problems SDes-Spec, SDes-CompA, SRec-Spec, and SRec-CompA, as they suggest that making both the software systems and the degree of allowable adaptation small under the approaches encoded in these problems does not yield tractability. However, the situation for problems SDes-Comp and SRec-Comp may not be so dire. To date, we have not been able to prove fp-intractability relative to a number of the individual parameters and parameter-combinations considered here for these problems. Hence, if fp-tractability holds in at least some of those cases, this would constitute proof that component selection without adaptation is tractable in a wider set of circumstances than either {\em de novo} design or component selection with adaptation. Two valid objections to our fp-tractability results are that (1) the algorithms underlying these results are crude and rely on brute-force search and (2) the running times of these algorithms are (to be blunt, ludicrously) impractical. These objections are often true of the initial fp-algorithms derived relative to a parameter-set. However, once fp-tractability is proven, surprisingly effective fp-algorithms are often subsequently developed with greatly diminished non-polynomial terms and polynomial terms that are quadratic or even linear in the input size (see \cite{CF+15,DF13} and references). A final very important proviso is in order -- namely, as illuminating as the results given here are in demonstrating basic forms of (in)tractability for software design and reconfiguration problems relative to the three approaches considered, these results do not necessarily imply that methods currently being applied to design or reconfigure software are impractical. Differing software and component models, the particular situations in which these currently-used methods are being applied, and accepted standards by which method practicality is assessed may render the results given here irrelevant. For example, current methods may already be implicitly exploiting restrictions on the input and output such that both efficient and correct operation (or operation that is correct with probability very close to one) are guaranteed. That being said, not knowing the precise conditions under which such practicality holds could have serious consequences, {\em e.g.}, drastically slowed software creation time and/or unreliable software operation, if these conditions are violated. These consequences would be particularly damaging in the case of runtime-based applications like ubiquitous and autonomic computing. Given that reliable software operation is very important and efficient software design and reconfiguration is at the very least desirable, the acquisition of such knowledge via a combination of rigorous empirical and theoretical analyses should be a priority. With respect to theoretical analyses, it is our hope that the techniques and results in this paper comprise a useful first step. \section{Conclusions}\label{SectConc} We have presented a formal characterization of the problems of software system design and reconfiguration by {\em de novo} design, component selection, and component selection with adaptation. Our complexity analyses reveal that, while these problems are computationally intractable in general, there are restrictions that render them tractable. Though the immediate practical utility of our tractability results is questionable given the basic models of software requirements, software systems and components relative to which they were derived, our intractability results give the first rigorous computational comparison between the three approaches to software design considered here. In particular, our results as a whole establish that all three approaches are equally computationally difficult in general but suggest that software creation by component selection may be tractable under more circumstances than the other two approaches. There are several possible directions for future research. The first is to complete the analysis begun here to see if software creation by component selection really is fp-tractable for software systems that are small and/or created with small amounts of adaptation. The second is to extend this analysis to the more realistic models of software requirements, software systems, components, and component libraries sketched in Section \ref{SectGenRes}. Last but certainly not least, derived tractability results should be implemented and tested in designing and reconfiguring actual software systems. Such testing will give invaluable guidance in phrasing future theoretical analyses along the lines sketched here; in turn, such analyses will hopefully help to guide future research in comp-onent-based software development. \newpage \section{Acknowledgments} The authors extend most grateful thanks to Iris van Rooij and Maria Otworowska (Donders Institute for Brain, Cognition, and Behaviour, Radboud University Nijmegen) with whom they collaborated on the formalization of the adaptive toolbox theory of human decision-making that underlies the formalizations of component-based design and reconfiguration analyzed here. They would also like to thank the three reviewers for comments that helped greatly to improve the presentation of this paper. TW was supported by NSERC Discovery Grants RGPIN 228104-2010 and 228104-2015. % trigger a \newpage just before the given reference % number - used to balance the columns on the last page % adjust value as needed - may need to be readjusted if % the document is modified later %\IEEEtriggeratref{8} % The "triggered" command can be changed if desired: %\IEEEtriggercmd{\enlargethispage{-5in}} % references section % can use a bibliography generated by BibTeX as a .bbl file % BibTeX documentation can be easily obtained at: % http://www.ctan.org/tex-archive/biblio/bibtex/contrib/doc/ % The IEEEtran BibTeX style support page is at: % http://www.michaelshell.org/tex/ieeetran/bibtex/ \bibliographystyle{abbrv} % argument is your BibTeX string definitions and bibliography database(s) %\bibliography{IEEEabrv,paper} \bibliography{paper} % % manually copy in the resultant .bbl file % set second argument of \begin to the number of references % (used to reserve space for the reference number labels box) %\begin{thebibliography}{1} % %\bibitem{IEEEhowto:kopka} %H.~Kopka and P.~W. Daly, \emph{A Guide to \LaTeX}, 3rd~ed.\hskip 1em plus % 0.5em minus 0.4em\relax Harlow, England: Addison-Wesley, 1999. \appendix \section{Proofs of Selected Results} \label{AppProof} All of our intractability results will be derived using reductions from the following $NP$-hard problem: \noindent {\sc Dominating set} \cite[Problem GT2]{GJ79} \\ {\em Input}: An undirected graph $G = (V, E)$ and an integer $k$. \\ {\em Question}: Does $G$ contain a dominating set of size $\leq k$, {\em i.e.}, is there a subset $V' \subseteq V$, $|V'| \geq k$, such that for all $v \in V'$, either $v \in V'$ or there is a $v' \in V'$ such that $(v, v') \in E$? \noindent For each vertex $v \in V$, let the complete neighbourhood $N_C(v)$ of $v$ be the set composed of $v$ and the set of all vertices in $G$ that are adjacent to $v$ by a single edge, {\em i.e.}, $v \cup \{ u ~ | ~ u ~ \in V ~ \rm{and} ~ (u,v) \in E\}$. We assume below an arbitrary ordering on the vertices of $V$ such that $V = \{v_1, v_2, \ldots, v_{|V|}\}$. \vspace*{-0.1in} \begin{lemma} {\sc Dominating Set} polynomial-time many-one reduces to SDes-Spec such that in the constructed instance of SDes-Spec, $|A| = 2$, $|sel| = 0$, and $|prc|$ is a function of $k$ in the given instance of {\sc Dominating Set}. % \label{LemRedSDesSpec} \end{lemma} \begin{proof} Given an instance $\langle G = (V, E), k\rangle$ of {\sc Dominating set}, the constructed instance $\langle I, A, R, X = \langle |sel|,|prc|\rangle \rangle$ of SDes-Spec has $I = \{i_1, i_2, \ldots i_{|V|}\}$, $A = \{0, 1\}$, $|sel| = 0$, and $|prc| = k$. There are $|V| + 1$ situation-action pairs in $R$ such that (1) for $r_i = (s_i, a_i)$, $1 \leq i \leq |V|$, $v(i_j) = True$ if $v_j \in N_C(v_i)$ and is $False$ otherwise and $a_i = 1$, and (2) for $r_{|V|+1} = (s_{|V|+1}, a_{|V|+1})$, all $v(i_j)$ are $False$ and $a_{|V|+1} = 0$. Note that the instance of SDes-Spec described above can be constructed in time polynomial in the size of the given instance of {\sc Dominating set}. If there is a dominating set of size at most $k$ in the given instance of {\sc Dominating set}, construct a software system consisting of a default \texttt{*}-condition selector and a single procedure in which the $k$ \texttt{IF-THEN} statements have situation-variable conditions corresponding to the vertices in the dominating set (adding arbitrary other vertex situation-variables if the size of the dominating set is less than $k$) and action $1$ and the final \texttt{ELSE} statement has action $0$. Observe that this software system satisfies all situation-action pairs in $R$ and has $|sel| = 0$ and $|prc| = k$. Conversely, suppose that the constructed instance of SDes-Spec has a software system satisfying $R$ with $|sel| = 0$ and $|prc| \leq k$. The selector in this system must be the default selector as it is the only selector with $|sel| = 0$. As for the single procedure attached to that selector, it has two possible structures: \begin{enumerate} \item{ \textit{No negated situation-variable conditions}: As $r_{|V|+1}$ has no situation-variables set to $True$, it can only be processed correctly by the final \texttt{ELSE}-statement, which must thus execute action $0$. In order to accept all other situation-pairs in $R$, the $k$ conditions must then have situation-variables whose corresponding vertices form a dominating set in $G$ of size at most $k$. } \item{ \textit{Negated situation-variables are present}: Let $c$ be the first negated situation-variable condition encountered moving down the code in the procedure, $C$ be the set of unnegated situation-variable conditions encountered before $c$, and $R' \subseteq R$ be the set of situation-action pairs not recognized by the situation-variables in $C$. As $|prc| \leq k$, $|C| \leq k - 1$. Moreover, as situation-action pair $r_{|V|+1}$ has no situation-variable with value $True$ and hence cannot be recognized by an \texttt{IF-THEN} statement with an unnegated situation-variable condition, $r_{|V|+1} \in R'$. Let $R'' \subset R$ be such that $R' = R'' \cup \{r_{|V|+1}\}$. If $R''$ is empty, then the variables in $C$ must have recognized all situation-action pairs in $R$ except $r_{|V|+1}$, and hence the vertices corresponding to the situation-variables in $C$ form a dominating set in $G$ of size at most $k - 1$. If $R''$ is not empty, situation-variable $c$ cannot have value $False$ for any of the situation-action pairs in $R''$ because having either $0$ or $1$ as the action executed by the associated \texttt{IF-THEN} statement would result in the procedure executing the wrong action for at least one situation-action pair in $R'$ (if $0$, at least one of the situation-action pairs in $R''$; if $1$, $r_{|V|+1}$). However, this implies that all situation-action pairs in $R''$ have value $True$ for $c$, which in turn implies that the vertices corresponding to the situation-variables in $C \cup \{c\}$ form a dominating set in $G$ of size at most $k$. } \end{enumerate} \noindent Hence, the existence of a satisfying software system for the constructed instance of SDes-Spec implies the existence of a dominating set of size at most $k$ for the given instance of {\sc Dominating Set}. To complete the proof, note that in the constructed instance of SDes-Spec, $|A| = 2$, $|sel| = 1$, and $|prc| = k$. \end{proof} % \newpage %\begin{lemma} %{\sc Dominating Set} polynomial-time many-one reduces to SDes-CompA such that %in the constructed instance of SDes-CompA, $|A| = d = 2$, $|sel| = 0$, %$|L_{sel}| = L_{prc}| = 1$, and $|prc|$ and $c_c$ are functions of $k$ in %the given instance of {\sc Dominating Set}. %% %\label{LemRedSDesCompA} %\end{lemma} % %\begin{proof}[(sketch)] %Given an instance $\langle G = (V, E),$ $k\rangle$ of {\sc Dominating set}, %the constructed instance $\langle I, A, R,$ $L_{sel},$ $L_{prc}, d, %c_c \rangle$ %of SDes-CompA has $I$, $A$, and $R$ as in the reduction in Lemma %\ref{LemRedSDesSpec} above. Let $L_{sel}$ consist of the default selector and %$L_{prc}$ consist of a single procedure whose $k$ \texttt{IF-THEN} statements %have conditions that are arbitrarily-selected situation-variables in $I$ and %execute action $1$ and whose \texttt{ELSE} statement executes action $0$. %Finally, set $d = 2$ and $c_c = k$. %Note that the instance of SDes-Spec described above can be constructed in %time polynomial in the size of the given instance of {\sc Dominating set}. %The proof of correctness is a modification of that given for the reduction %in Lemma \ref{LemRedSDesSpec}. %To complete the proof, note that in the constructed instance of SDes-CompA, %$|A| = 2$, $|sel| = 0$, $|L_{sel}| = |L_{prc}| = 1$, and $|prc| = c_c = k$. %\end{proof} \begin{lemma} {\sc Dominating Set} polynomial-time many-one reduces to SDes-Comp such that in the constructed instance of SDes-CompA, $|A| = 2$, $|L_{sel}| = 1$, and $d$ is a function of $k$ in the given instance of {\sc Dominating Set}. % \label{LemRedSDesComp} \end{lemma} \begin{proof} Given an instance $\langle G = (V, E), k\rangle$ of {\sc Dominating set}, the constructed instance $\langle I, A, R, L_{sel}, L_{prc}, d\rangle$ of SDes-Comp has $I = \{i_1, i_2, \ldots i_{2|V|}\}$ and $A = \{0, 1\}$. There are $|V| + 1$ situation-action pairs in $R$ such that (1) for $r_i = (s_i, a_i)$, $1 \leq i \leq |V|$, $v(i_i) = True$, $v(i_{|V| + j}) = True$ if $v_j \in N_C(v_i)$, all other $v(i_j)$ are $False$, and $a_i = 1$, and (2) for $r_{|V|+1} = (s_{|V|+1}, a_{|V|+1})$, all $v(i_j) = False$ and $a_{|V|+1} = 0$. There is a single selector in $L_{sel}$ whose $|V| - 1$ \texttt{IF-THEN} statement conditions are the first $|V| - 1$ situation-variables in $I$. There are $|V|$ procedures in $L_{prc}$ such that procedure $i$, $1 \leq i \leq |V|$, has an \texttt{IF-THEN} statement for each of the vertices in $N_C(v_i)$ whose condition is the situation-variable associated with that vertex and which executes action $1$ and an \texttt{ELSE} statement that executes action $0$. Finally, let $d = k + 1$. Note that the instance of SDes-Comp described above can be constructed in time polynomial in the size of the given instance of {\sc Dominating set}. If there is a dominating set of size at most $k$ in the given instance of {\sc Dominating Set}, construct a software system consisting of the single selector in $L_{sel}$ and the at most $k$ procedures from $L_{prc}$ corresponding to the vertices in the dominating set. For each of the $|V| - 1$ \texttt{IF-THEN} statements in the selector, call the procedure encoding the neighbourhood of the vertex in the dominating set which dominates the vertex corresponding to the situation-variable in that statement's condition. For the \texttt{ELSE} statement in the selector, execute the procedure encoding the neighbourhood of the vertex in the dominating set that dominates vertex $v_{|V|}$. Observe that this software system satisfies all situation-action pairs in $R$ and has $d = k + 1$. Conversely, suppose that the constructed instance SDes-Comp has a software system constructed from at most $d = k + 1$ distinct components from $L_{sel}$ and $L_{prc}$ that satisfies all of the situation-action pairs in $R$. As the selector is constructed such that each of the first $|V|$ situation-action pairs in $R$ has its own associated procedure and each procedure accepts the vertices in a specific vertex-neighbourhood in $G$, in order for these situation-action pairs to be satisfied, the distinct procedures in the software system must correspond to a dominating set for $G$ (note that both $r_{|V|}$ and $r_{|V|+1}$ are satisfied by the procedure associated with the \texttt{ELSE} statement in the selector). As $d = k + 1$ and the system had to incorporate a selector from $L_{sel}$, this means that there are at most $k$ such procedures and hence a dominating set of size at most $k$ in the given instance of {\sc Dominating Set}. To complete the proof, note that in the constructed instance of SDes-Comp, $|A| = 2$, $|L_{sel}| = 1$, and $d = k + 1$. \end{proof} \noindent {\bf Result A}: {\em SDes-Spec and SDes-Comp are $NP$-hard.} \begin{proof} Follows from the $NP$-hardness of {\sc Dominating Set} and the reductions in Lemmas \ref{LemRedSDesSpec} and \ref{LemRedSDesComp}, respectively. \end{proof} \noindent {\bf Result B}: {\em SDes-Spec is $W[2]$-hard for $\{ |A|, |sel|, |prc|\}$ when $|A| = 2$ and $|sel| = 0$.} \begin{proof} Follows from the $W[2]$-hardness of $\{ k \}$-{\sc Dominat-ing Set} \cite{DF13} and the reductions from {\sc Dominating Set} to SDes-Spec given in Lemma \ref{LemRedSDesSpec}. \end{proof} %\noindent %{\bf Result C}: %{\em SDes-CompA is $W[2]$-hard for $\{ |A|, |sel|, |prc|, d,$ $|L_{sel}|, % |L_{prc}|, c_c\}$ when $|A| = d = 2$, $|sel| = 0$ and $|L_{sel}| = % |L_{prc}| = 1$.} % %\begin{proof} %Follows from the $W[2]$-hardness of $\{ k \}$-{\sc Dominat-ing Set} %\cite{DF13} and the reductions from {\sc Dominating Set} to SDes-CompA %given in Lemma \ref{LemRedSDesCompA}. %\end{proof} % %\noindent %{\bf Result D}: %{\em SDes-CompA is $W[2]$-hard for $\{ |A|, d, |L_{sel}|\}$ % when $|A| = 2$ and $|L_{sel}| = 1$.} % %\begin{proof} %Follows from the $W[2]$-hardness of $\{ k \}$-{\sc Dominat-ing Set} %\cite{DF13} and the reductions from {\sc Dominating Set} to SDes-Comp %given in Lemma \ref{LemRedSDesComp}. %\end{proof} %\noindent %{\bf Result H}: %{\em SDes-Spec, SDes-CompA, SDes-Comp, SRec-Spec, SRec-CompA, and SRec-Comp % are fp-tractable for $\{ |I| \}$.} % %\begin{proof}[(sketch)] %All six problems can be solved by first generating all %possible two-level software systems %that are based on $|I|$ situation-variables and $|A|$ actions and then %checking each generated system for required problem-specific properties, %{\em e.g.}, at most $c_l$ component-changes were made in transforming $S$ into %$S'$ (SRec-CompA, SRec-Comp). All systems can be generated in time that is %upper-bounded by a function of $|I|$ and all checks can be done in time that %is either polynomial in the input size or upper-bounded by a function of $|I|$. %\end{proof} % that's all folks \end{document}