[Script Info]
Title: 
[Events]
Format: Layer, Start, End, Style, Name, MarginL, MarginR, MarginV, Effect, Text
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,(Offscreen) So welcome to the talk from Niels
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,about dependency resolution in\Npolynomial time.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,(Neils) I'm Neils, I'm doing my second\Ntalk today.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This time about something slightly\Nmore technical.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I wanted to do dependency resolution\Nin deterministic polynomial time,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,which is what this is all about.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I didn't get as far with this as I wanted.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I wanted to have a tool ready and have\Nsome results, which I didn't quite finish.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So these will be my findings work in\Nprogress notes.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We have six topics I have to cover.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,A quick introduction.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then something about the hard problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then the part the part where it actually\Nturns out to be highly tractable
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,in practice, if you don't think too much\Nabout it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And then there is some installing,\Nupgrading, and installing again
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,for how to improve your solvers.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Starting with introduction.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I'm hoping mostly to debunk the myth\Nthat dependency resolution is a very
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,hard problem that we cannot solve,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and we should remove packages in the hopes\Nthat they will somehow keep the archive
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,from exploding, and the dependency\Nresolvers to break, and apt to die,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and god knows what.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I've been working on Britney, which is a\Ndifferent problem to solve, but it
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,involves the same techniques, or uses some\Nof the same techniques.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Some will be directly applicable to apt,\Nsome will not.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,There's not a one size fits all solution, sorry.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And I much less haven't wrote it yet,\Neven if there was.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So defining the problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,When you try to install a package on your\Nsystem,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,there's actually two problems\Nbeing solved.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,One is the part where apt figures out if I\Nhave to install Eclipse.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You'll be needing a lot of Java packages,\Nyou'll be needing a lot of other stuff.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And so it figures out which packages are\Nneeded for this to make sense.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The separate part of the problem,\Nthe second problem is,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,once you have this list, they have to be\Nunpackaged and configured in a certain
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,order for this all to make sense.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,They are in theory two distinct problems.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I'll be talking about the first problem,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,because that's actually\Ndependency resolution.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The other thing is just ordering.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,The ordering thing is certainly also very\Nimportant part.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I don't want to dismiss that, it's just
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it is in fact theoretically a polynomial\Ntime problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So to solve the ordering problem, you\Nbasically compute all the action-
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Given a set of actions that need\Nto be done,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,then there are some constraints between\Nsome of them,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,like you unpack things before you\Nconfigure it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Maybe you deconfigure something else\Nbefore that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So you end up with a list of partial ??\Nconstraints.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,From that you build a graph with ordering.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It's fairly simple to do, in practice,\Nif you have the right tools for it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Then without cycles, this is a trivial\Nthings where it just orders it
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and gives you this is the order,\Ngo fix.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,When there's cycles you will get a single\Naction consisting of multiple things
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,to do at the same time, which is really\Nimpossible to do.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It turns out that the way we defined this\Nwhole thing,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,if you have a package that does not have a\Npost install script,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it does not need to be configured separately.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That means that it's just unpacked or\Nnot unpacked.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That tends to break most cylcles.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If you want, there's problems with\Nordering constraints.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Help us to find a way to get rid of most\Nof the post install scripts,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,such as the ones just running lvconfig\Nand nothing else.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That could solve some of the cycles,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and otherwise it's just feeding it to dpkg\Nand it works.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If you have a cycle, it's a separate\Nproblem fixing that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,I won't be covering that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,As I said, the runtime is polynomial.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It's something like the size of the\Npackage, a regular graph.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Which is fairly polynomial.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,This even covers finding cycles.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Again breaking cycles is just removing\Npost install scripts.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And of course if you think this is too\Nsimple,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,you can always implement more features\Non top of it,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,such as trying to optimize for minimal\Ndowntime of services and all that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You can make any trivial problem very hard\Nvery soon with that.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So, the hard problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,First of all, the players.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We've got apt, aptitude, cupt, whatever.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We've got Britney.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We've got DOSE, edos, whatever its\Nname is today.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,They solve the hard problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Or they should be trying to do.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Notable tools not affected by it.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,dpkg.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So dpkg surely figures out if you are\Nmissing dependencies. It says,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,"I cannot resolve this, and I don't know\Nwhere to fetch it, so I'm just giving up."
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And that is the only thing you can do.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Which means it only verifies the solution\Nwhich is known to be polynomial,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,and is therefore is not a game player.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,DAK rm is also doing a polynomial time\Ncheck, it just happens to be so
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,for other reasons.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That's basically the known players.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,There are probably others.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,But we're moving onto the\Nhard problem itself
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So the problem we actually have is,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,we've got version dependencies,\Nwe've got alternative choices,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,we've got virtual packages.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,All three makes this problem hard.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You basically have to remove all possible\Nalternative choices, guesses, whatever,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,to make this simple.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It just so happens if you move version\Ndependencies among other things,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,things become really fun.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,?? to solve the problem, but upgrading\Ngets really really spicy.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So how do we ensure that dpkg\Nis configured before your new package,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,use a feature new dev package\Nis installed.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That's sort of impossible.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It becomes simple, but we end up with a\Nbroken dependency ??,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,so it's not really an option.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Technically there's also a way to make\Nit simple by having multiple versions
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,of things, and removing negative\Ndependencies,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,but that's not necessarily easy to do either.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Presumably file configs will get in our\Nway or something.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We have to redefine where we place all of\Nthe files, that's not going to be
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,something we're doing anytime soon.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So yeah, it's not really an option.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,To give you a better understanding of the\Nproblem, please consider this example.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,If we have coreutils at some version,\Ndepending on either this version
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,of libc or a newer one.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,From this can we immediately conclude
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,that if libc 2.19 is known to be\Ninstallable,
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,that coreutils will also be installable?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,How many people think we can immediately\Nconclude something from this?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,How many people think we {\i1}cannot{\i0}\Nconclude anything from this?
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,We'll that's good.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,So it turns out that with negative\Ndependencies and without negative
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,dependencies, it doesn't really matter.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,With negative dependencies, libc or\Nwhatever it depends on could
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,just conflict with coreutils, we're\Nbroken, it's out.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,And without negative dependencies, you\Ncould have one of the things where
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,it depends on a version that's newer or\Nolder, and no.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,It's not really trivial to do.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,You can't conclude something locally,\Nin theory.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,That's something that can\Nbecome a problem.
Dialogue: 0,9:59:59.99,9:59:59.99,Default,,0000,0000,0000,,Anyway, it is highly tractable in practice.