The mancoosi project is organizing MISC (for Mancoosi International Solver Competition), an international competition of solvers for package/component installation and upgrade problems.

Who is Mancoosi?

Mancoosi is a research project financed by the European Commission, consisting of a consortium of 10 academic and industrial partners. Our common goal is to develop better tools for package-based system administration, in particular support for rollback of package installations, and better tools for the resolution of relationships between packages, like for instance dependencies or conflicts. The Mancoosi project is entirely committed to Free and Open Source Software. To learn more about the project please consult our home page.

What kind of solvers are we talking about?

We are addressing the following problem: The solver is given

  • a set of available packages,
  • a set of currently installed packages,
  • a user request, for instance to install or remove certain packages.

A solution to such a problem would be a new set of installed packages, that is the installation status after having satisfied the user request. The resulting installation must be consistent, that is satisfy all package relationships like Depends, Conflicts, etc., even when the initial installation status was inconsistent.

Solvers of this kind are currently an integral part of package managers like for instance apt-get, urpmi, or YaST. We are concentrating on the problem solving aspect, and abstract away from all other aspects like downloading files, actually performing a package installation or de-installation on disk, or configuring a package.

Why a competition?

Our experience from the daily life as FOSS users and developers, and also from our previous project EDOS, shows that many of the currently used package installation tools are unsatisfactory in several respects. We want package installation tools that are

  • complete: they should find a solution whenever there exists one;
  • powerful: they should understand complex optimization criteria;
  • efficient: they should find a good solution fast, despite of the theoretically high complexity of the problem.

All these requirements make for an interesting challenge, and organizing a competition is a good way to stimulate research on this problem. The rules of the competition are based on these three requirements in decreasing order of priority.

So one needs a common format for inputs and results, right ?

Yes. We have defined such a format called Common Upgradeability Description Format (CUDF). The CUDF format combines features of the RPM and the Debian packaging world, and also allows to encode other formats like for instance metadata of Eclipse plugins. However, we have simplified the format a bit with respect to what you might know from your favorite GNU/Linux distribution in order to make life easier for the developer of problem solvers. To learn more about this format please start with the CUDF primer, and then read the complete specification. You'll have to understand completely syntax and semantics of CUDF if you want to participate in the competition.

How do you tell good solutions from bad solutions ?

The semantics of the CUDF format only defines what a solution is. In order to compare the quality of two different solutions we need a precisely defined optimization criterion. MISC competition of different years may use different sets of optimization criteria.

Interested?

Please subscribe to our announcement mailing list so that you'll be informed of all future developments of the competition.