The OSGi resolver is an np-complete problem?

[bjhargrave]

Original bug ID: BZ#526 From: @tjwatson Reported version: R4 V4.1

[bjhargrave]

Comment author: @tjwatson

With very large bundle sets which have lots of Export-Package "uses" clauses and lots of different versions of various packages and bundles it becomes clear that the OSGi package resolver can have a very large set of possible solutions to verify a correct class space solution.

I'm opening this bug because I suspect the OSGi resolver problem to be an np-complete problem (see http://en.wikipedia.org/wiki/NP-complete). We need to prove if the problem is np-complete or not. If it is then I think it is pretty unfortunate for very large systems. I believe some level of reduction can be done but this could leave some valid solutions out of the considered set of valid solutions.

At the very least we need to be conscious of such designs and avoid them in future if possible. We also need to avoid adding any more complexity to the resolver which would add more possible solutions to decide from.

[bjhargrave]

Comment author: glyn.normington@springsource.com

According to the wikipedia article, the simplest way to prove that OSGi resolution is NP-complete is to show it is NP and then to express a known NP-complete problem as a problem in terms of OSGi resolution.

So, firstly, is OSGi resolution NP? I'm not sure, but it seems likely. Apart from the state space 'explosion' that occurs with large numbers of bundles and the consequent difficulty of searching for a solution, any proposed solution is relatively easy to verify - a common property of NP problems.

Assuming OSGi resolution is NP, which known NP-complete problem might be expressible in OSGi resolution terms? I wonder if the Boolean satisfiability problem ([1]), 'SAT', would fit the bill?

I think it might be possible to express a Boolean OR using a version range package import with two valid candidate exporters each using require-bundle to wire to bundles representing the Boolean variables to be OR'd. Boolean AND could be expressed by simply using require-bundle to wire to both bundles representing the Boolean variables to be AND'd. I'm not sure how to express Boolean NOT, but it might be as simple as having a bundle representing Boolean variable P export a package p and have another bundle representing NOT P also export the package p and then ensure that uses constraints are put everywhere so that at most one of these two bundles could be resolved.

Then I think the trick would be to arrange for a single bundle to resolve if and only if the Boolean expression in question could be satisfied.

That said, the article on SAT ([1]) makes this relevant observation:

"However, beyond this theoretical significance [of being NP-complete], efficient and scalable algorithms for SAT that were developed over the last decade have contributed to dramatic advances in our ability to automatically solve problem instances involving tens of thousands of variables and millions of constraints."

So even if OSGi resolution is NP-complete, this may not matter. ;-)

[1] http://en.wikipedia.org/wiki/Boolean_satisfiability_problem

[bjhargrave]

Comment author: Pascal Rapicault <pascal@sonatype.com>

So even if OSGi resolution is NP-complete, this may not matter. ;-) Well I kind of agree and disagree.

• I agree because most of the time, the set of bundles being passed to the resolver represent a solvable system that only has one solution and therefore even though it is technically speaking NP, it solves in an apparent polynomial time (or close) because of the limited search space.
• I disagree because we introduced the "uses" concept and we should recommend people to use it (we tried it on the eclipse SDK) to ensure consistency of the class space. However even on a system where there is a solution, the time spent to find it is close to exponential, which then matters.

Now what would be interesting to understand is whether the cause of this speed is the algorithm we use (local optimal search) and if a systematic search algorithm would be better suited.

[bjhargrave]

Comment author: @bjhargrave

CPEG call: The size of the problem sets that OSGi deals with can be solved quickly enough with solvers like SAT solvers. OSGi will continue to pay attention to ensure that changes to the spec do not significantly increase the complexity of the resolver.