On the Computational Complexity of Designing and Reconfiguring Component-based Software Systems

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 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.