Is the resolution problem in OSGi NP-Complete?

Question

The resolution problem is described in the modularity chapter of the OSGi R4 core specification. It's a constraint satisfaction problem and certainly a challenging problem to solve efficiently, i.e. not by brute force. The main complications are the uses constraint, which has non-local effects, and the freedom to drop optional imports to obtain a successful resolution.

NP-Completeness is dealt with elsewhere on StackOverflow.

There has already been plenty of speculation about the answer to this question, so please avoid speculation. Good answers will include a proof or, failing that, a compelling informal argument.

The answer to this question will be valuable to those projects building resolvers for OSGi, including the Eclipse Equinox and Apache Felix open source projects, as well as to the wider OSGi community.

Answer 1

Yes.

The approach taken by the edos paper Pascal quoted can be made to work with OSGi. Below I’ll show how to reduce any 3-SAT instance to an OSGi bundle resolution problem. This site doesn’t seem to support mathematical notation, so I’ll use the kind of notation that’s familiar to programmers instead.

Here’s a definition of the 3-SAT problem we’re trying to reduce:

First define A to be a set of propositional atoms and their negations A = {a(1), … ,a(k),na(1), … ,na(k)}. In simpler language, each a(i) is a boolean and we define na(i)=!a(i)

Then 3-SAT instances S have the form: S = C(1) & … & C(n)

where C(i) = L(i,1) | L(i,2) | L(i,3) and each L(i,j) is a member of A

Solving a particular 3-SAT instance involves finding a set of values, true or false for each a(i) in A, such that S evaluates to true.

Now let’s define the bundles we’ll be use to construct an equivalent resolution problem. In the following all bundle and package versions are 0 and import version ranges unrestricted except where specified.

• The whole expression S will be represented by Bundle BS
• Each clause C(i) will be represented by a bundle BC(i)
• Each atom a(j) will be represented by a bundle BA(j) version 1
• Each negated atom na(j) will be represented by a bundle BA(j) version 2

Now for the constraints, starting with the atoms:

BA(j) version 1
-export package PA(j) version 1
-for each clause C(i) containing atom a(j) export PM(i) and add PA(j) to PM(i)’s uses directive

BA(j) version 2
-export package PA(j) version 2
-for each clause C(i) containing negated atom na(j) export PM(i) and add PA(j) to PM(i)’s uses directive

BC(i)
-export PC(i)
-import PM(i) and add it to the uses directive of PC(i)
-for each atom a(j) in clause C(i) optionally import PA(j) version [1,1] and add PA(j) to the uses directive of the PC(i) export
-for each atom na(j) in clause C(i) optionally import PA(j) version [2,2] and add PA(j) to the uses directive of the PC(i) export

BS
-no exports
-for each clause C(i) import PC(i)
-for each atom a(j) in A import PA(j) [1,2]

A few words of explanation:

The AND relationships between the clauses is implemented by having BS import from each BC(i) a package PC(i) that is only exported by this bundle.

The OR relationship works because BC(i) imports package PM(i) which is only exported by the bundles representing its members, so at least one of them must be present, and because it optionally imports some PA(j) version x from each bundle representing a member, a package unique to that bundle.

The NOT relationship between BA(j) version 1 and BA(j) version 2 is enforced by uses constraints. BS imports each package PA(j) without version constraints, so it must import either PA(j) version 1 or PA(j) version 2 for each j. Also, the uses constraints ensure that any PA(j) imported by a clause bundle BC(i) acts as an implied constraint on the class space of BS, so BS cannot be resolved if both versions of PA(j) appear in its implied constraints. So only one version of BA(j) can be in the solution.

Incidentally, there is a much easier way to implement the NOT relationship - just add the singleton:=true directive to each BA(j). I haven’t done it this way because the singleton directive is rarely used, so this seems like cheating. I’m only mentioning it because in practice, no OSGi framework I know of implements uses based package constraints properly in the face of optional imports, so if you were to actually create bundles using this method then testing them could be a frustrating experience.

Other remarks:

A reduction of 3-SAT that doesn't use optional imports in also possible, although this is longer. It basically involves an extra layer of bundles to simulate the optionality using versions. A reduction of 1-in-3 SAT is equivalent to a reduction to 3-SAT and looks simpler, although I haven't stepped through it.

Apart from proofs that use singleton:=true, all of the proofs I know about depend on the transitivity of uses constraints. Note that both singleton:=true and transitive uses are non-local constraints.

The proof above actually shows that the OSGi resolution problem is NP-Complete or worse. To demonstrate that it’s not worse we need to show that any solution to the problem can be verified in polynomial time. Most of the things that need to be checked are local, e.g. looking at each non-optional import and checking that it is wired to a compatible export. Verifying these is O(num-local-constraints). Constraints based on singleton:=true need to look at all singleton bundles and check that no two have the same bundle symbolic name. The number of checks is less than num-bundlesnum-bundles. The most complicated part is checking that the uses constraints are satisfied. For each bundle this involves walking the uses graph to gather all of the constraints and then checking that none of these conflict with the bundle’s imports. Any reasonable walking algorithm would turn back whenever it encountered a wire or uses relationship it had seen before, so the maximum number of steps in the walk is (num-wires-in-framework + num-uses-in framework). The maximum cost of checking that a wire or uses relationship hasn't been walked before is less than the log of this. Once the constrained packages have been gathered the cost of the consistency check for each bundle is less than num-imports-in-bundlenum-exports-in-framework. Everything here is a polynomial or better.

Answer 2

This paper provides a demonstration: http://www.cse.ucsd.edu/~rjhala/papers/opium.html