Debian ist frei und seine Entwickler sind Kosmopoliten. Das Linux-Magazin berichtet regelmäßig Interna aus der Debian-Entwicklerszene und angrenzenden Projekten.

Akademiker lieben schwierige Sachverhalte, die einfach zu formulieren sind. Dazu gehören NP-äquivalente Probleme aus der theoretischen Informatik. NP bezeichnet einen Komplexitätslevel, auf dem es für eine mathematische Frage anscheinend keine effiziente Lösung gibt. Ein Beispiel ist das Problem des Handlungsreisenden, bei dem der kürzeste Weg einer Rundreise zu bestimmen ist. Das Installationsproblem von Debian entpuppt sich ebenfalls als eines dieser Probleme: Kann man alle Debian-Pakete installieren (Abbildung 1)?

Abbildung 1: Das Problem heißt: Kann man alle Debian-Pakete installieren? (Bold: © Sebastian Kaulitzki, Fotolia.com)

Installations-Sudoku

Das Installationsproblem wurzelt in Konflikten und Abhängigkeiten zwischen Paketen. Zum Beispiel sagt eine Debian-Bedingung, dass man nicht zwei verschiedene Versionen des gleichen Pakets gleichzeitig installieren kann. Kürzlich demonstrierte Apt-Maintainer Daniel Burrows, dass das Installationsproblem so komplex ist wie ein Sudoku. Sein Python-Skript namens »debsudoku.py«, konvertiert in Ksudoku gespeicherte Spiele zu Paketdateien [1]. Keine Chance für eine einfachere Lösung?

Ein raffiniertes Tool

Zurück ins Jahr 2004: Das europäische Forschungsprojekt Edos lief an (Environment for the development and Distribution of Open Source Software). Um dem Installationsproblem nachzugehen, analysierte es die Paketabhängigkeiten Depends, Conflicts und Provides. Das Team kreierte auf dieser Grundlage das Tool »debcheck«.

Das Projekt hat sich nicht damit begnügt, Papiere auf wissenschaftlichen Konferenzen zu veröffentlichen. Die Ergebnisse hat es stattdessen in Form des Debian-Pakets »edos-debcheck« in die Qualitätssicherung von Linux-Distributionen einfließen lassen. Auf einer Paketliste gestartet, spuckt es eine Liste aller nicht installierbaren Pakete aus:

edos-debcheck -failures -explain  < /var/lib/apt/lists/Mirror

Für die über 22000 Pakete in Lenny zum Beispiel braucht Edos-debcheck nur wenige Sekunden.

Das Geheimnis dahinter heißt SAT-Solver. Diese Werkzeuge entscheiden, ob logische Formeln eine Lösung besitzen. Sämtliche NP-äquivalenten Probleme lassen sich auf aussagenlogische Erfüllbarkeitsprobleme (SAT, vom englischen Satisfiablility) zurückführen, damit auch das Installationsproblem. SAT-Solver sind raffiniert: Sie leiten aus fehlgeschlagenen Lösungsversuchen ab, welche weiteren Versuche aussichtslos sind. Damit ist schnell ersichtlich, ob ein Problem lösbar ist oder nicht.

Paket-Wetter

Für die Debian-Versionen entsteht dank Edos eine tägliche Liste der nicht installierbaren Pakete [2]. Der “Debian-Wetterbericht” veranschaulicht die Ergebnisse (Abbildung 2). Seit Februar 2008 dokumentiert das Nachfolgeprojekt Mancoosi die Früchte der Edos-Forschung und hat sich vorgenommen, Systemverwaltern weitere Werkzeuge zur Paketinstallation an die Hand zu geben [3]. Geplant ist auch ein internationaler Wettbewerb für Installationswerkzeuge. (ake)

Abbildung 2: Debian-Wetterbericht für Sid am Sonntag, 26. Oktober 2008.