(Offscreen) So welcome to the talk from Niels
about dependency resolution in polynomial time.
(Neils) I'm Neils, I'm doing my second talk today.
This time about something slightly more technical.
I wanted to do dependency resolution in deterministic polynomial time,
which is what this is all about.
I didn't get as far with this as I wanted.
I wanted to have a tool ready and have some results, which I didn't quite finish.
So these will be my findings work in progress notes.
We have six topics I have to cover.
A quick introduction.
Then something about the hard problem.
Then the part the part where it actually turns out to be highly tractable
in practice, if you don't think too much about it.
And then there is some installing, upgrading, and installing again
for how to improve your solvers.
Starting with introduction.
I'm hoping mostly to debunk the myth that dependency resolution is a very
hard problem that we cannot solve,
and we should remove packages in the hopes that they will somehow keep the archive
from exploding, and the dependency resolvers to break, and apt to die,
and god knows what.
I've been working on Britney, which is a different problem to solve, but it
involves the same techniques, or uses some of the same techniques.
Some will be directly applicable to apt, some will not.
There's not a one size fits all solution, sorry.
And I much less haven't wrote it yet, even if there was.
So defining the problem.
When you try to install a package on your system,
there's actually two problems being solved.
One is the part where apt figures out if I have to install Eclipse.
You'll be needing a lot of Java packages, you'll be needing a lot of other stuff.
And so it figures out which packages are needed for this to make sense.
The separate part of the problem, the second problem is,
once you have this list, they have to be unpackaged and configured in a certain
order for this all to make sense.
They are in theory two distinct problems.
I'll be talking about the first problem,
because that's actually dependency resolution.
The other thing is just ordering.
The ordering thing is certainly also very important part.
I don't want to dismiss that, it's just
it is in fact theoretically a polynomial time problem.
So to solve the ordering problem, you basically compute all the action-
Given a set of actions that need to be done,
then there are some constraints between some of them,
like you unpack things before you configure it.
Maybe you deconfigure something else before that.
So you end up with a list of partial ?? constraints.
From that you build a graph with ordering.
It's fairly simple to do, in practice, if you have the right tools for it.
Then without cycles, this is a trivial things where it just orders it
and gives you this is the order, go fix.
When there's cycles you will get a single action consisting of multiple things
to do at the same time, which is really impossible to do.
It turns out that the way we defined this whole thing,
if you have a package that does not have a post install script,
it does not need to be configured separately.
That means that it's just unpacked or not unpacked.
That tends to break most cylcles.
If you want, there's problems with ordering constraints.
Help us to find a way to get rid of most of the post install scripts,
such as the ones just running lvconfig and nothing else.
That could solve some of the cycles,
and otherwise it's just feeding it to dpkg and it works.
If you have a cycle, it's a separate problem fixing that.
I won't be covering that.
As I said, the runtime is polynomial.
It's something like the size of the package, a regular graph.
Which is fairly polynomial.
This even covers finding cycles.
Again breaking cycles is just removing post install scripts.
And of course if you think this is too simple,
you can always implement more features on top of it,
such as trying to optimize for minimal downtime of services and all that.
You can make any trivial problem very hard very soon with that.