Our work is related to what has been called Software Release Management [vdHHHW97], i.e., the process through which software is made available and obtained by the final users. While our goal was not to address the problem pertaining to physical distribution our efforts have been directed in providing tools that can improve the quality of the Software Release Management. Notice though that the problem of physical distribution has been addressed by other workpackages of the EDOS Project.
But most of these approaches are targeted at designing component systems, with a clear top-down process typical of a software architecture viewpoint, while the component systems we have to handle come from the huge pre-existing infrastructures and legacy systems (e.g. well established GNU/Linux distributions) that have been conceived without having such a kind of architectural specifications in mind.
Our long term goal is to integrate these systems by abstracting and enriching their features while maintaining backward compatibility. For example by proposing extensions to the dependency specification that enables the checking of more sophisticated properties as in [VR02a, VR02b]
On the algorithmic side, an interesting work is [Bix03], that uses adjacency matrices to represent different kinds of dependency graphs. By performing operation on these matrices it is possible to verify some kinds of properties related to the evolution of the system (e.g., the number of components that are required if a given component has to be reused).
Notice though that in all the approaches just mentioned, the notion of conflict is not taken into account, as we do in ours. This makes all these approaches not suitable in a context, like the one we have analyzed, where conflicts are an essential (and complex) part of the dependency requirement specification.
A more similar work is [vdS04] that uses feature diagrams to model dependencies and configurations, and BDD algorithms to perform automated checking of model properties.
Finally, there is a wealth of largely used tools in the Free Software Community, known as meta-package managers [Sil04, Nie05, Man05] that are clearly the most similar in spirit to what we have developed here, as they are able to explore the dependency requirements of a given package and perform all the steps needed to correctly install it by automatically finding the missing dependent packages, downloading and, finally, installing them, taking into acocunt dependencies and conflicts. The essential difference between our tools and those meta-package manager is that meta-package manager try to optimize the installation of packages on a user machine, which is a task radically different, and in principle much more difficult than veryfying that a repository does not contain broken packages. As a consequence, many of these tools contain specific heuristics that make them incomplete (some packages are actually reported broken while they are installable), while those tools, like Smart, that strive to be complete are unacceptably inefficient when used to verify installability. And none of them has a formal basis.