[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.