1
99:59:59,999 --> 99:59:59,999
(Offscreen) So welcome to the talk from Niels

2
99:59:59,999 --> 99:59:59,999
about dependency resolution in
polynomial time.

3
99:59:59,999 --> 99:59:59,999
(Neils) I'm Neils, I'm doing my second
talk today.

4
99:59:59,999 --> 99:59:59,999
This time about something slightly
more technical.

5
99:59:59,999 --> 99:59:59,999
I wanted to do dependency resolution
in deterministic polynomial time,

6
99:59:59,999 --> 99:59:59,999
which is what this is all about.

7
99:59:59,999 --> 99:59:59,999
I didn't get as far with this as I wanted.

8
99:59:59,999 --> 99:59:59,999
I wanted to have a tool ready and have
some results, which I didn't quite finish.

9
99:59:59,999 --> 99:59:59,999
So these will be my findings work in
progress notes.

10
99:59:59,999 --> 99:59:59,999
We have six topics I have to cover.

11
99:59:59,999 --> 99:59:59,999
A quick introduction.

12
99:59:59,999 --> 99:59:59,999
Then something about the hard problem.

13
99:59:59,999 --> 99:59:59,999
Then the part the part where it actually
turns out to be highly tractable

14
99:59:59,999 --> 99:59:59,999
in practice, if you don't think too much
about it.

15
99:59:59,999 --> 99:59:59,999
And then there is some installing,
upgrading, and installing again

16
99:59:59,999 --> 99:59:59,999
for how to improve your solvers.

17
99:59:59,999 --> 99:59:59,999
Starting with introduction.

18
99:59:59,999 --> 99:59:59,999
I'm hoping mostly to debunk the myth
that dependency resolution is a very

19
99:59:59,999 --> 99:59:59,999
hard problem that we cannot solve,

20
99:59:59,999 --> 99:59:59,999
and we should remove packages in the hopes
that they will somehow keep the archive

21
99:59:59,999 --> 99:59:59,999
from exploding, and the dependency
resolvers to break, and apt to die,

22
99:59:59,999 --> 99:59:59,999
and god knows what.

23
99:59:59,999 --> 99:59:59,999
I've been working on Britney, which is a
different problem to solve, but it

24
99:59:59,999 --> 99:59:59,999
involves the same techniques, or uses some
of the same techniques.

25
99:59:59,999 --> 99:59:59,999
Some will be directly applicable to apt,
some will not.

26
99:59:59,999 --> 99:59:59,999
There's not a one size fits all solution, sorry.

27
99:59:59,999 --> 99:59:59,999
And I much less haven't wrote it yet,
even if there was.

28
99:59:59,999 --> 99:59:59,999
So defining the problem.

29
99:59:59,999 --> 99:59:59,999
When you try to install a package on your
system,

30
99:59:59,999 --> 99:59:59,999
there's actually two problems
being solved.

31
99:59:59,999 --> 99:59:59,999
One is the part where apt figures out if I
have to install Eclipse.

32
99:59:59,999 --> 99:59:59,999
You'll be needing a lot of Java packages,
you'll be needing a lot of other stuff.

33
99:59:59,999 --> 99:59:59,999
And so it figures out which packages are
needed for this to make sense.

34
99:59:59,999 --> 99:59:59,999
The separate part of the problem,
the second problem is,

35
99:59:59,999 --> 99:59:59,999
once you have this list, they have to be
unpackaged and configured in a certain

36
99:59:59,999 --> 99:59:59,999
order for this all to make sense.

37
99:59:59,999 --> 99:59:59,999
They are in theory two distinct problems.

38
99:59:59,999 --> 99:59:59,999
I'll be talking about the first problem,

39
99:59:59,999 --> 99:59:59,999
because that's actually
dependency resolution.

40
99:59:59,999 --> 99:59:59,999
The other thing is just ordering.

41
99:59:59,999 --> 99:59:59,999
The ordering thing is certainly also very
important part.

42
99:59:59,999 --> 99:59:59,999
I don't want to dismiss that, it's just

43
99:59:59,999 --> 99:59:59,999
it is in fact theoretically a polynomial
time problem.

44
99:59:59,999 --> 99:59:59,999
So to solve the ordering problem, you
basically compute all the action-

45
99:59:59,999 --> 99:59:59,999
Given a set of actions that need
to be done,

46
99:59:59,999 --> 99:59:59,999
then there are some constraints between
some of them,

47
99:59:59,999 --> 99:59:59,999
like you unpack things before you
configure it.

48
99:59:59,999 --> 99:59:59,999
Maybe you deconfigure something else
before that.

49
99:59:59,999 --> 99:59:59,999
So you end up with a list of partial ??
constraints.

50
99:59:59,999 --> 99:59:59,999
From that you build a graph with ordering.

51
99:59:59,999 --> 99:59:59,999
It's fairly simple to do, in practice,
if you have the right tools for it.

52
99:59:59,999 --> 99:59:59,999
Then without cycles, this is a trivial
things where it just orders it

53
99:59:59,999 --> 99:59:59,999
and gives you this is the order,
go fix.

54
99:59:59,999 --> 99:59:59,999
When there's cycles you will get a single
action consisting of multiple things

55
99:59:59,999 --> 99:59:59,999
to do at the same time, which is really
impossible to do.

56
99:59:59,999 --> 99:59:59,999
It turns out that the way we defined this
whole thing,

57
99:59:59,999 --> 99:59:59,999
if you have a package that does not have a
post install script,

58
99:59:59,999 --> 99:59:59,999
it does not need to be configured separately.

59
99:59:59,999 --> 99:59:59,999
That means that it's just unpacked or
not unpacked.

60
99:59:59,999 --> 99:59:59,999
That tends to break most cylcles.

61
99:59:59,999 --> 99:59:59,999
If you want, there's problems with
ordering constraints.

62
99:59:59,999 --> 99:59:59,999
Help us to find a way to get rid of most
of the post install scripts,

63
99:59:59,999 --> 99:59:59,999
such as the ones just running lvconfig
and nothing else.

64
99:59:59,999 --> 99:59:59,999
That could solve some of the cycles,

65
99:59:59,999 --> 99:59:59,999
and otherwise it's just feeding it to dpkg
and it works.

66
99:59:59,999 --> 99:59:59,999
If you have a cycle, it's a separate
problem fixing that.

67
99:59:59,999 --> 99:59:59,999
I won't be covering that.

68
99:59:59,999 --> 99:59:59,999
As I said, the runtime is polynomial.

69
99:59:59,999 --> 99:59:59,999
It's something like the size of the
package, a regular graph.

70
99:59:59,999 --> 99:59:59,999
Which is fairly polynomial.

71
99:59:59,999 --> 99:59:59,999
This even covers finding cycles.

72
99:59:59,999 --> 99:59:59,999
Again breaking cycles is just removing
post install scripts.

73
99:59:59,999 --> 99:59:59,999
And of course if you think this is too
simple,

74
99:59:59,999 --> 99:59:59,999
you can always implement more features
on top of it,

75
99:59:59,999 --> 99:59:59,999
such as trying to optimize for minimal
downtime of services and all that.

76
99:59:59,999 --> 99:59:59,999
You can make any trivial problem very hard
very soon with that.