I do not think this is the question that was asked (I asked earlier
for the proof that it was NP complete, and I have not see this one
either :-)
Anyway, I think the biggest use case set for the moment is
SpringSource's bundle repository. I understand they load all these
bundles in a single framework so that should give you a nice set ...
Any of the IBMers on this list, willing to provide Dietmar with the
manifests of Websphere, Lotus,
and Rational?
Kind regards,
Peter Kriens
On 17 jun 2008, at 19:55, Pascal Rapicault wrote:
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
<graycol.gif>Dietmar Wolz ---06/17/2008 09:42:51 AM---Hallo, my name
is Dr. Dietmar Wolz, I am working at SOPERA GmbH for the
<ecblank.gif>
From: <ecblank.gif>
Dietmar Wolz <[EMAIL PROTECTED]>
<ecblank.gif>
To: <ecblank.gif>
[email protected]
<ecblank.gif>
Date: <ecblank.gif>
06/17/2008 09:42 AM
<ecblank.gif>
Subject: <ecblank.gif>
[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
_______________________________________________
OSGi Developer Mail List
[email protected]
https://mail.osgi.org/mailman/listinfo/osgi-dev
_______________________________________________
OSGi Developer Mail List
[email protected]
https://mail.osgi.org/mailman/listinfo/osgi-dev
