Open Source EC Funded Projects: EDOS

Among open source research project funded by the EC the EDOS project aimed to study and solve problems associated with the production, management and distribution of open source software packages.

EDOS (Environment for the Development and Distribution of Open Source software) obtained interesting results, either from an academic point of view or from an industrial perspective.

Stefan Fermigier, Nuxeo CEO and EDOS contributor, speaking about EDOS’s results wrote me:

They proved that the problem of installing packages on a Linux distribution with all the proper dependencies is NP-complete. While this may seem purely theoretical, it’s not, because it means that we can easily transform a dependency problem into a generic NP-complete problem, then use a generic (and efficient) NP-complete problem solver to solve this problem. This way, it’s possible to show that for certain situations (that come from real life, not from contrived examples), a 1000-fold increase in execution speed for the dependency management part of a tool such as yum, urpmi or apt-get can be attained.

Among EDOS findings I read some spectacular results:

  • Time to recompute distribution-wide dependency meta-data: this relates to the execution of Ceve, the generalized package parser produced by EDOS WP2. Ceve typically requires approximately 30 seconds to run against a full-fledged Linux distribution such as Mandriva Linux or Caixa M ́agica. Ceve computation time grows linearly with the number of packages.
  • Time to generate CDs for a distribution: this indicator relates to the execution time of Tart, the personalized distribution generator produced within EDOS WP2. The order of magnitude of the execution time of Tart is one minute for a complete Mandriva Linux distribution, using a standard modern server (2GB RAM, 2GHz). This represents a significant improvement over the tools previously used by Mandriva and Caixa M ́agica for generating distribution CDs: the tool mkcd previously used by Mandriva for this purpose typically required approximately ten minutes for achieving the operation, in a more more error-prone and less customizable manner.

I don’t know if Mandriva is using EDOS tools, but for sure Debian is using edos-debcheck (see also the Debian edos-debcheck page). Debian is also working on Cupt, a re-implementation of the popular APT suite.

The “Debian Weather Report“, developed during the EDOS project, helps Debian developers to check dependency issues inside a given distribution in a graphical fashion. The “weather” is an indication of how safe it is on a given day to attempt some package installation/upgrade.

Stefane talking about the Debian Weather Report says:

I’m not a Debian developer, so I can’t tell if this tool is widely used by Debian developers, but I can tell you that similar dashboards are of tremendous use for us at Nuxeo to manage compatibility of all the components and extensions of the Nuxeo ECM Platform.

Kudos to the EDOS team!