Vous pouvez vous abonner à nos annonces de séminaires
                     http://gallium.inria.fr/seminaires/

                             S E M I N A I R E
       __                                  
      / _`  _   /  /  o                       /| /|   __  __  __ __    _  _
     /   ) __) /  /  / /  / /\/|    -----    / |/ |  /  )(_  /  /  ) ) ) __)
    (___/ (_/ (_ (_ / (__/ /   |            /     | (__/ __)(_ (__/ (_/ (_/
                                                
                          I N R I A - Rocquencourt
                        Amphi Turing du bâtiment 1

                           Lundi 11 avril, 10h30

                             -----------------
                             Jérôme Vouillon
                             -----------------

                           Laboratoire PPS, CNRS

                    ====================================
                    Software component co-installability
                    ====================================

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 components that cannot be installed together: this is the
co-installability problem, which is related to boolean satisfiability
and is known to be algorithmically hard.

Indeed, from a maintenance point of view, one needs to identify which
components cannot be installed together, in order to check whether
these incompatibilities are justified or due to erroneous
dependencies. The full graph of dependencies between components is
also too rich for end users, which are interested in having a given
set of functionalities provided by some components (for instance, they
want a word processor and a Web browser) but do not care about the
additional components also installed.

We present a theoretical framework, based on semantic preserving
graph-theoretic transformations, that allows to associate to each
concrete component repository a much smaller one with a simpler
structure, but with equivalent co-installability properties. This
smaller repository can be represented graphically, giving a concise
view of the co-installability issues in the original repository, or
used as a basis for various algorithms related to co-installability,
like the efficient computation of strong conflicts between
components.