Linked by Thom Holwerda on Mon 4th Jun 2007 16:38 UTC, submitted by anonymous
Benchmarks "We have developed a new package-management tool, called Opium, that improves on current tools in two ways: Opium is complete, in that if there is a solution, Opium is guaranteed to find it, and Opium can optimize a user-provided objective function, which could for example state that smaller packages should be preferred over larger ones. We performed a comparative study of our tool against Debian's apt-get on 600 traces of real-world package installations. We show that Opium runs fast enough to be usable, and that its completeness and optimality guarantees provide concrete benefits to end users."
Thread beginning with comment 245205
To read all comments associated with this story, please click here.
Solving the wrong problem
by Tom5 on Mon 4th Jun 2007 18:03 UTC
Tom5
Member since:
2005-09-17

From the paper:

Libraries and software packages have dependencies that must be satisfied, and conflicts that must be avoided. Otherwise the entire system, not just a single application, may become unstable.


The solution isn't a better solver (although that's nice to have anyway), the solution is remove the possibility of conflicts.

Why do I need to use a massively complex algorithm to find the single version of some libfoo that works with all of the one thousand packages on my machine? What the system needs is a bit of slack. If there's a period of a few months when one program needs libfoo > 3 and another needs libfoo == 3 that shouldn't matter. Just keep two copies of libfoo on my system until the problem is fixed.

This is how Zero Install works:

http://0install.net

Reply Score: 4

RE: Solving the wrong problem
by chris_dk on Mon 4th Jun 2007 19:04 in reply to "Solving the wrong problem"
chris_dk Member since:
2005-07-12

I completely agree.

Package manager seem to get increasingly complex while they should strive for simplicity.

Zeroinstall has my support.

Reply Parent Score: 1

christucker Member since:
2007-06-04

I would argue that OPIUM is much simpler than APT in the way it solves dependencies. :-) We make a trivial rewriting of the problem into a logical form, and then just throw it at an off-the-shelf solver to give us an answer. No mucking about with traversing graphs, choosing which path to take, back-tracking, or anything. Sometimes simplicity comes from an elegant new representation, not from a reduction in flexibility or power.

Reply Parent Score: 2

RE: Solving the wrong problem
by christucker on Mon 4th Jun 2007 19:17 in reply to "Solving the wrong problem"
christucker Member since:
2007-06-04

There are several alternative packaging mechanisms that do this kind of partitioning of your library space, and I agree that they are interesting. However, the vast majority of the Linux world currently runs on Debian or RPM; switching to something like Zero Install requires replacing this architecture. Beyond that, even with Zero Install OPIUM offers the optimality benefit: if you eliminate conflicts you don't have to worry about the uninstall problem, but you do still have to figure out what is the best set of packages (or equivalent) to install to, for example, download the fewest bytes or get the most up-to-date system.

Reply Parent Score: 2

RE[2]: Solving the wrong problem
by Tom5 on Mon 4th Jun 2007 20:30 in reply to "RE: Solving the wrong problem"
Tom5 Member since:
2005-09-17

Even with Zero Install OPIUM offers the optimality benefit: if you eliminate conflicts you don't have to worry about the uninstall problem, but you do still have to figure out what is the best set of packages (or equivalent) to install to, for example, download the fewest bytes or get the most up-to-date system.


Sure, putting a solver like this in Zero Install would be interesting. The overhead might be a bit high (Zero Install runs its solver* each time a program is run; I guess we'd have to cache the result instead if using this).

* The current solver is very naive, but we mainly get away with it because we only worry about conflicts between the libraries required by a single program.

Good paper, BTW.

Reply Parent Score: 1

RE: Solving the wrong problem
by deanlinkous on Mon 4th Jun 2007 19:35 in reply to "Solving the wrong problem"
deanlinkous Member since:
2006-06-19

The solution isn't a better solver (although that's nice to have anyway), the solution is remove the possibility of conflicts.

Why do I need to use a massively complex algorithm to find the single version of some libfoo that works with all of the one thousand packages on my machine? What the system needs is a bit of slack. If there's a period of a few months when one program needs libfoo > 3 and another needs libfoo == 3 that shouldn't matter. Just keep two copies of libfoo on my system until the problem is fixed.

Exactly! Trying to correct the actual problem instead of trying to be more complex in order to alleviate the already complex nature of something. The version system and model is a rough-spot to my untrained eye.

That is along a similar line of thought that I TRIED to discuss with Chris at the forums. Not that I have used 0install or anything but that the development model version system needs to be standardized or some slack put into it to allow some flex and maintain some backward/forward compatibility/flexibility.If we could assure that packageB1.2.x would work with the handful of packages that rely on packageB instead of requiring packageB1.2.8 or > then that IMO would alleviate a lot of the dependency issues and conflicts.

IOW - if something requires libfoo4 and you have stuff that requires libfoo3 then libfoo4 SHOULD be all that is required and should automatically register as libfoo4 but also inform the package manager that libfoo3 is also satisfied. Of course, that isn't always possible depending on changes but often it IS possible to use a newer library for something that thinks it needs a older one.

Heck, how many of us hasn't symlinked a mis-match version and it worked fine or simply went in and fudged the requirements listed in a deb?

But I am not a big fan of standardizing anything either...

I am just not sure that apt has as many failures and problems as this study makes it out to have.

Edited 2007-06-04 19:41

Reply Parent Score: 2

christucker Member since:
2007-06-04


Exactly! Trying to correct the actual problem instead of trying to be more complex in order to alleviate the already complex nature of something. The version system and model is a rough-spot to my untrained eye.


There are many different problems in any system. I don't disagree that there are serious complexities and difficulties in the packaging system, and in particular in creating and testing packages. I'm afraid we can't solve all the world's problems in one go, though: the OPIUM paper addresses three clearly identified (and demonstrated) problems; it doesn't preclude you or anyone else from tackling the others (see the comments on Zero Install and my responses: all this work is good and productive!).


IOW - if something requires libfoo4 and you have stuff that requires libfoo3 then libfoo4 SHOULD be all that is required and should automatically register as libfoo4 but also inform the package manager that libfoo3 is also satisfied. Of course, that isn't always possible depending on changes but often it IS possible to use a newer library for something that thinks it needs a older one.


You're describing a packaging problem. If X depends on libfoo it has a couple of choices:
1) Depends: libfoo == 3
2) Depends: libfoo
3) Depends: libfoo > 3
Either of the last two will work when installing X on a system with libfoo3. The first should only be used if X is known to only work with version 3 of libfoo. If something declares it explicitly needs libfoo version 3 when in fact it doesn't there is *nothing* that APT or OPIUM or any other package installation algorithm can do to fix it. We have to be able to rely on the rules the packages lay down because they're all we have to go on: imagine if in a real world system we said "Oh, it says it needs libc6 v.2.2, but we're going to upgrade to 2.3 because we think everything will be OK". You'd have a lot of broken systems and a lot of angry people.

Reply Parent Score: 3