Abstract
Modern software systems are built by composing components drawn from large
repositories, whose size and complexity is increasing at a very fast pace. A
fundamental challenge for the maintainability and the scalability of such
software systems is the ability to quickly identify the components that can or
cannot be installed together: this problem is related to boolean
satisfiability and is known to be algorithmically hard.
We will provide a survey the classic results of this research area, and
conclude with a short presentation of joint work with Jerome Vouillon: a
novel approach to the problem, based on semantic preserving graph-theoretic
transformations, that allows to extract from a concrete component repository
a much smaller one with a simpler structure, but equivalent
co-installability properties.
This approach has been extensively tested on GNU/Linux distributions,
and can be applied to a large class of component based systems.
