9:59:59.000,9:59:59.000
(Offscreen) So welcome to the talk from Niels

9:59:59.000,9:59:59.000
about dependency resolution in[br]polynomial time.

9:59:59.000,9:59:59.000
(Neils) I'm Neils, I'm doing my second[br]talk today.

9:59:59.000,9:59:59.000
This time about something slightly[br]more technical.

9:59:59.000,9:59:59.000
I wanted to do dependency resolution[br]in deterministic polynomial time,

9:59:59.000,9:59:59.000
which is what this is all about.

9:59:59.000,9:59:59.000
I didn't get as far with this as I wanted.

9:59:59.000,9:59:59.000
I wanted to have a tool ready and have[br]some results, which I didn't quite finish.

9:59:59.000,9:59:59.000
So these will be my findings work in[br]progress notes.

9:59:59.000,9:59:59.000
We have six topics I have to cover.

9:59:59.000,9:59:59.000
A quick introduction.

9:59:59.000,9:59:59.000
Then something about the hard problem.

9:59:59.000,9:59:59.000
Then the part the part where it actually[br]turns out to be highly tractable

9:59:59.000,9:59:59.000
in practice, if you don't think too much[br]about it.

9:59:59.000,9:59:59.000
And then there is some installing,[br]upgrading, and installing again

9:59:59.000,9:59:59.000
for how to improve your solvers.

9:59:59.000,9:59:59.000
Starting with introduction.

9:59:59.000,9:59:59.000
I'm hoping mostly to debunk the myth[br]that dependency resolution is a very

9:59:59.000,9:59:59.000
hard problem that we cannot solve,

9:59:59.000,9:59:59.000
and we should remove packages in the hopes[br]that they will somehow keep the archive

9:59:59.000,9:59:59.000
from exploding, and the dependency[br]resolvers to break, and apt to die,

9:59:59.000,9:59:59.000
and god knows what.

9:59:59.000,9:59:59.000
I've been working on Britney, which is a[br]different problem to solve, but it

9:59:59.000,9:59:59.000
involves the same techniques, or uses some[br]of the same techniques.

9:59:59.000,9:59:59.000
Some will be directly applicable to apt,[br]some will not.

9:59:59.000,9:59:59.000
There's not a one size fits all solution, sorry.

9:59:59.000,9:59:59.000
And I much less haven't wrote it yet,[br]even if there was.

9:59:59.000,9:59:59.000
So defining the problem.

9:59:59.000,9:59:59.000
When you try to install a package on your[br]system,

9:59:59.000,9:59:59.000
there's actually two problems[br]being solved.

9:59:59.000,9:59:59.000
One is the part where apt figures out if I[br]have to install Eclipse.

9:59:59.000,9:59:59.000
You'll be needing a lot of Java packages,[br]you'll be needing a lot of other stuff.

9:59:59.000,9:59:59.000
And so it figures out which packages are[br]needed for this to make sense.

9:59:59.000,9:59:59.000
The separate part of the problem,[br]the second problem is,

9:59:59.000,9:59:59.000
once you have this list, they have to be[br]unpackaged and configured in a certain

9:59:59.000,9:59:59.000
order for this all to make sense.

9:59:59.000,9:59:59.000
They are in theory two distinct problems.

9:59:59.000,9:59:59.000
I'll be talking about the first problem,

9:59:59.000,9:59:59.000
because that's actually[br]dependency resolution.

9:59:59.000,9:59:59.000
The other thing is just ordering.

9:59:59.000,9:59:59.000
The ordering thing is certainly also very[br]important part.

9:59:59.000,9:59:59.000
I don't want to dismiss that, it's just

9:59:59.000,9:59:59.000
it is in fact theoretically a polynomial[br]time problem.

9:59:59.000,9:59:59.000
So to solve the ordering problem, you[br]basically compute all the action-

9:59:59.000,9:59:59.000
Given a set of actions that need[br]to be done,

9:59:59.000,9:59:59.000
then there are some constraints between[br]some of them,

9:59:59.000,9:59:59.000
like you unpack things before you[br]configure it.

9:59:59.000,9:59:59.000
Maybe you deconfigure something else[br]before that.

9:59:59.000,9:59:59.000
So you end up with a list of partial ??[br]constraints.

9:59:59.000,9:59:59.000
From that you build a graph with ordering.

9:59:59.000,9:59:59.000
It's fairly simple to do, in practice,[br]if you have the right tools for it.

9:59:59.000,9:59:59.000
Then without cycles, this is a trivial[br]things where it just orders it

9:59:59.000,9:59:59.000
and gives you this is the order,[br]go fix.

9:59:59.000,9:59:59.000
When there's cycles you will get a single[br]action consisting of multiple things

9:59:59.000,9:59:59.000
to do at the same time, which is really[br]impossible to do.

9:59:59.000,9:59:59.000
It turns out that the way we defined this[br]whole thing,

9:59:59.000,9:59:59.000
if you have a package that does not have a[br]post install script,

9:59:59.000,9:59:59.000
it does not need to be configured separately.

9:59:59.000,9:59:59.000
That means that it's just unpacked or[br]not unpacked.

9:59:59.000,9:59:59.000
That tends to break most cylcles.

9:59:59.000,9:59:59.000
If you want, there's problems with[br]ordering constraints.

9:59:59.000,9:59:59.000
Help us to find a way to get rid of most[br]of the post install scripts,

9:59:59.000,9:59:59.000
such as the ones just running lvconfig[br]and nothing else.

9:59:59.000,9:59:59.000
That could solve some of the cycles,

9:59:59.000,9:59:59.000
and otherwise it's just feeding it to dpkg[br]and it works.

9:59:59.000,9:59:59.000
If you have a cycle, it's a separate[br]problem fixing that.

9:59:59.000,9:59:59.000
I won't be covering that.

9:59:59.000,9:59:59.000
As I said, the runtime is polynomial.

9:59:59.000,9:59:59.000
It's something like the size of the[br]package, a regular graph.

9:59:59.000,9:59:59.000
Which is fairly polynomial.

9:59:59.000,9:59:59.000
This even covers finding cycles.

9:59:59.000,9:59:59.000
Again breaking cycles is just removing[br]post install scripts.

9:59:59.000,9:59:59.000
And of course if you think this is too[br]simple,

9:59:59.000,9:59:59.000
you can always implement more features[br]on top of it,

9:59:59.000,9:59:59.000
such as trying to optimize for minimal[br]downtime of services and all that.

9:59:59.000,9:59:59.000
You can make any trivial problem very hard[br]very soon with that.