the MANCOOSI research project

MANCOOSI is a research project started in February 2008 which aims to tackle some of the issues involved in dealing with the complexity of inter-related, but independently developed, pieces of software. You can well imagine how Debian is the perfect fit for such a scenario, and how intriguing it can be seen for it scale issues.

MANCOOSI won't be yet another research project about software metrics, bugs count, yada yada, rather it will (try to) tackle 2 very specific topics which affects our everyday life of Debian users and developers. Both are related to the "upgrade" problem of packages installed on a local machine wrt the new packages available on the remote Debian repositories. The first topic is the rollback of the machine to the status which was available before the upgrade run, either because the upgrade failed for some runtime cause (e.g. postscript exit with non-zero ...), or because (possibly days later) the local sysadm wants to roll-back to the previous state because it was "better". In this talk we will briefly touch this topic, just presenting the work packages related to this task, and the people which will be working on it. Mainly those people are research from the software engineering communities which frequently face similar problems in other setting, and also other commercial distributions such as Mandriva and Caixa Magica (a small GNU/Linux distribution from Portugal).

The second topic, which will be discusseed a bit more in detail, is dependency resolution. In this respect, a problem we have in the state of the art in Debian is that none of the dependency solvers we have (apt and aptitude, sbuild, pbuilder mainly) is complete; this means that in some cases a solution to the upgrade problem exists, but it isn't found by the tools we are using. As shown by some of the achievements of the former EDOS project (which will be briefly discussed as well), dependency resolution can be encoded either as a SAT solving problem (satisfiability of a logic formula) or a constrained programming problem. Several efforts in MANCOOSI will be about defining optimizations and specialized algorithms to adapt SAT solvers and automatic theorem provers to the dependency resolution problem we face daily in upgrades.

Other efforts will be in the creation of a challenge for dependency solvers, in the spirit of other international challenges which each year involve several researches in the development of ever better automatic theorem provers and SAT solvers. We plan to start collecting upgrade problems from user machines, similarly to what we already do with popcon though with far more complex datasets, and publish them as challenges for algorithms. Then we will advertise the challenge and run it for the first time at some appropriate research conference.

Practically, a few by products are also expected specifically for Debian, the pluggability of external dependency solvers in our package managers and, as a consequence, the possibility of sharing solvers among different package managers.