Re:The truth about Goobuntu: Google's in-house desktop Ubunt...
by morsch on Thursday August 30, 2012 @08:15AM
(#4454179)
What are the practical benefits of using a SAT-solver? Is it faster? I haven't had any problems with the results of apt's algorithms, but maybe others have. When installing/upgrading stuff, the update step seems to be much slower than the other steps.
Re:The truth about Goobuntu: Google's in-house desktop Ubunt...
by rwmj on Thursday August 30, 2012 @01:14PM
(#4455640)
Package upgrades are an example of SAT (the satisfiability problem)[1]. Apt and yum don't recognize this result and instead use a bunch of ad hoc rules. These often fail, when they could succeed. SAT will always find the answer, eventually, if there is one.
Now the issue is that SAT is NP-complete, so it could run for a very long time before it finds a solution. But there are very good solvers which "most of the time" (meaning, basically always) find a solution in a short time. They are also open source projects[2].
There's been an existence proof (zypper) that using a standard SAT solver is possible, works, and is fast.
[1] http://arxiv.org/pdf/1007.1021 [2] http://www.cs.sunysb.edu/~algorith/implement/minisat/impleme...
I do a lot of packaging for both Fedora and Debian and here are my thoughts:
* Building Debian packages is a horrible experience. Writing an RPM spec file is much nicer and easier.
* Apt is much much faster than yum.
* Using a true (NP-complete!) SAT-solver (ie. zypper) is lightyears ahead of anything Debian or Fedora are currently doing, although there's a project underway in Fedora to fork yum to use a SAT-solver.