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.

77
99:59:59,999 --> 99:59:59,999
So, the hard problem.

78
99:59:59,999 --> 99:59:59,999
First of all, the players.

79
99:59:59,999 --> 99:59:59,999
We've got apt, aptitude, cupt, whatever.

80
99:59:59,999 --> 99:59:59,999
We've got Britney.

81
99:59:59,999 --> 99:59:59,999
We've got DOSE, edos, whatever its
name is today.

82
99:59:59,999 --> 99:59:59,999
They solve the hard problem.

83
99:59:59,999 --> 99:59:59,999
Or they should be trying to do.

84
99:59:59,999 --> 99:59:59,999
Notable tools not affected by it.

85
99:59:59,999 --> 99:59:59,999
dpkg.

86
99:59:59,999 --> 99:59:59,999
So dpkg surely figures out if you are
missing dependencies. It says,

87
99:59:59,999 --> 99:59:59,999
"I cannot resolve this, and I don't know
where to fetch it, so I'm just giving up."

88
99:59:59,999 --> 99:59:59,999
And that is the only thing you can do.

89
99:59:59,999 --> 99:59:59,999
Which means it only verifies the solution
which is known to be polynomial,

90
99:59:59,999 --> 99:59:59,999
and is therefore is not a game player.

91
99:59:59,999 --> 99:59:59,999
DAK rm is also doing a polynomial time
check, it just happens to be so

92
99:59:59,999 --> 99:59:59,999
for other reasons.

93
99:59:59,999 --> 99:59:59,999
That's basically the known players.

94
99:59:59,999 --> 99:59:59,999
There are probably others.

95
99:59:59,999 --> 99:59:59,999
But we're moving onto the
hard problem itself

96
99:59:59,999 --> 99:59:59,999
So the problem we actually have is,

97
99:59:59,999 --> 99:59:59,999
we've got version dependencies,
we've got alternative choices,

98
99:59:59,999 --> 99:59:59,999
we've got virtual packages.

99
99:59:59,999 --> 99:59:59,999
All three makes this problem hard.

100
99:59:59,999 --> 99:59:59,999
You basically have to remove all possible
alternative choices, guesses, whatever,

101
99:59:59,999 --> 99:59:59,999
to make this simple.

102
99:59:59,999 --> 99:59:59,999
It just so happens if you move version
dependencies among other things,

103
99:59:59,999 --> 99:59:59,999
things become really fun.

104
99:59:59,999 --> 99:59:59,999
?? to solve the problem, but upgrading
gets really really spicy.

105
99:59:59,999 --> 99:59:59,999
So how do we ensure that dpkg
is configured before your new package,

106
99:59:59,999 --> 99:59:59,999
use a feature new dev package
is installed.

107
99:59:59,999 --> 99:59:59,999
That's sort of impossible.

108
99:59:59,999 --> 99:59:59,999
It becomes simple, but we end up with a
broken dependency ??,

109
99:59:59,999 --> 99:59:59,999
so it's not really an option.

110
99:59:59,999 --> 99:59:59,999
Technically there's also a way to make
it simple by having multiple versions

111
99:59:59,999 --> 99:59:59,999
of things, and removing negative
dependencies,

112
99:59:59,999 --> 99:59:59,999
but that's not necessarily easy to do either.

113
99:59:59,999 --> 99:59:59,999
Presumably file configs will get in our
way or something.

114
99:59:59,999 --> 99:59:59,999
We have to redefine where we place all of
the files, that's not going to be

115
99:59:59,999 --> 99:59:59,999
something we're doing anytime soon.

116
99:59:59,999 --> 99:59:59,999
So yeah, it's not really an option.

117
99:59:59,999 --> 99:59:59,999
To give you a better understanding of the
problem, please consider this example.

118
99:59:59,999 --> 99:59:59,999
If we have coreutils at some version,
depending on either this version

119
99:59:59,999 --> 99:59:59,999
of libc or a newer one.

120
99:59:59,999 --> 99:59:59,999
From this can we immediately conclude

121
99:59:59,999 --> 99:59:59,999
that if libc 2.19 is known to be
installable,

122
99:59:59,999 --> 99:59:59,999
that coreutils will also be installable?

123
99:59:59,999 --> 99:59:59,999
How many people think we can immediately
conclude something from this?

124
99:59:59,999 --> 99:59:59,999
How many people think we <i>cannot</i>
conclude anything from this?

125
99:59:59,999 --> 99:59:59,999
We'll that's good.

126
99:59:59,999 --> 99:59:59,999
So it turns out that with negative
dependencies and without negative

127
99:59:59,999 --> 99:59:59,999
dependencies, it doesn't really matter.

128
99:59:59,999 --> 99:59:59,999
With negative dependencies, libc or
whatever it depends on could

129
99:59:59,999 --> 99:59:59,999
just conflict with coreutils, we're
broken, it's out.

130
99:59:59,999 --> 99:59:59,999
And without negative dependencies, you
could have one of the things where

131
99:59:59,999 --> 99:59:59,999
it depends on a version that's newer or
older, and no.

132
99:59:59,999 --> 99:59:59,999
It's not really trivial to do.

133
99:59:59,999 --> 99:59:59,999
You can't conclude something locally,
in theory.

134
99:59:59,999 --> 99:59:59,999
That's something that can
become a problem.

135
99:59:59,999 --> 99:59:59,999
Anyway, it is highly tractable in practice.