One of Peter's question is: Is the OSGi resolver NP-complete? My answer is Yes. I don't have the time to demonstrate it in full details, however reusing the results from a few recent papers have shown that the Linux "Package installation" problem is NP-complete [1, 2], I think the conclusion is fairly straightforward given the similarities between RPM / DEB dependencies and OSGi dependencies . I have heard the argument that OSGi "use-clause" simplifies the problem and makes it non NP-complete. Independently of the veracity of this claim, since the specification does not mandate the usage of the use-clause, the problem is still NP-complete.
As for the pragmatic of using a SAT solver like outlined in [1, 2, 3], I'm happy to report that it works. Indeed in p2, the new Eclipse/OSGi provisioning solution delivered with Eclipse 3.4, we have used the results of [3] as the underpinning of our resolution technology and it works like a charm. Once the problem has been mapped to SAT problem, the resolver (in our case SAT4J [4]) is simply brutally fast for finding a solution even on the biggest scenarios we have seen. Note that in p2 the dependencies are pretty much the same than in OSGi to the exception of use-clause and a few other attributes that we have not used, but still it is very similar. So, can the OSGi resolution problem be cast to a SAT problem, I say Yes, now it is who will do it first :) [1] http://mancoosi.com/edos/algorithmic.html [2] http://www.edos-project.org/ [3] http://www.cse.ucsd.edu/~rjhala/papers/opium.html [4] http://www.sat4j.org |------------> | From: | |------------> >--------------------------------------------------------------------------------------------------------------------------------------------------| |Dietmar Wolz <[EMAIL PROTECTED]> | >--------------------------------------------------------------------------------------------------------------------------------------------------| |------------> | To: | |------------> >--------------------------------------------------------------------------------------------------------------------------------------------------| |[email protected] | >--------------------------------------------------------------------------------------------------------------------------------------------------| |------------> | Date: | |------------> >--------------------------------------------------------------------------------------------------------------------------------------------------| |06/17/2008 09:42 AM | >--------------------------------------------------------------------------------------------------------------------------------------------------| |------------> | Subject: | |------------> >--------------------------------------------------------------------------------------------------------------------------------------------------| |[osgi-dev] OSGi Research Challenge 2008 - The OSGi Resolver | >--------------------------------------------------------------------------------------------------------------------------------------------------| Hallo, my name is Dr. Dietmar Wolz, I am working at SOPERA GmbH for the Eclipse Runtime SOA Framework in the project Swordfish. At the OSGi Community Meeting in Berlin last week I talked with Peter Kriens about one of the OSGI research challenges for 2008, the "OSGi Resolver" problem, see http://www.osgi.org/blog/2008/02/research-challenges-for-osgi.html . I have some experience with similar kinds of problems so I would like to investigate this a little further. First I would like to collect any written information about this problem, if available. My approach to these kind of problems is quite pragmatic, even for generally NP-complete problems there can often be found good solutions in reasonable time for the specific instances of the problem which occur in practice. I favor a test driven approach, so my first aim would be to set up some kind of test environment which "generates" randomly reasonably sized "typical" instances of the problem. Next I would like to formalize the parameters to optimize in terms of test code. Last would be the test of different algorithms designed to solve the "resolver challenge". From the results we obtain it may be possible to derive a more theoretical paper, but this would be last on my priority list. For my first aim, the generation of test scenarios, it would be helpful to collect some typical instances, can anyone point me to existing projects where a good OSGi resolver would be of some value? Next is the definition which needs exactly to be optimized, can anyone provide me with more detailed information regarding this? Dr. Dietmar Wolz Phone +49 (0)228-182 1 90 17 Fax: +49 (0)228-181 1 90 99 Mobile: +49 (0)17623429219 mailto://[EMAIL PROTECTED] SOPERA GmbH - Open Source SOA Subscription Services, Support & Maintenance, Training, Technical SOA Consulting & Customized Development http://www.sopera.de _____________________________________________________________________ Der WEB.DE SmartSurfer hilft bis zu 70% Ihrer Onlinekosten zu sparen! http://smartsurfer.web.de/?mc=100071&distributionid=000000000066 _______________________________________________ OSGi Developer Mail List [email protected] https://mail.osgi.org/mailman/listinfo/osgi-dev
<<inline: graycol.gif>>
<<inline: ecblank.gif>>
_______________________________________________ OSGi Developer Mail List [email protected] https://mail.osgi.org/mailman/listinfo/osgi-dev
