Yeah, but that is a largely useless conclusion isn’t it? Navigation is NP complete but my TomTom (ok, Google Maps) does a wonderful job in no time. Most NP complete problems have heuristics that make them work well in most natural cases. I do think uses constraints for example can help prune the search space but they translate to a significantly wider SAT expression.
Kind regards,
Peter Kriens
> On 18 nov. 2016, at 13:47, Todor Boev <[email protected]> wrote:
>
> It may be useful to see how the bundle resolution problem is proven to be
> NP-Complete through 3-SAT:
> http://stackoverflow.com/questions/2085106/is-the-resolution-problem-in-osgi-np-complete
>
> <http://stackoverflow.com/questions/2085106/is-the-resolution-problem-in-osgi-np-complete>
>
> On Fri, Nov 18, 2016 at 10:32 AM, Todor Boev <[email protected]
> <mailto:[email protected]>> wrote:
> My math is very rusty and my math background is in a different area. Because
> of this I hoped to do the mostly programming exercise to integrate the
> Resolver service in p2 rather than to extend the SAT mapping. I need to look
> at the OSGi-to-SAT mapping paper in order to understand if this is possible
> with the current design of the Resolver.
>
> Regards
>
> On Fri, Nov 18, 2016 at 5:17 AM, Pascal Rapicault <[email protected]
> <mailto:[email protected]>> wrote:
> On 11/17/2016 8:54 AM, Peter Kriens wrote:
>> I remember trying to map uses constraints to a boolean expression but could
>> not find any way that did not blow up the expression size. This seemed very
>> unfortunate because I think they can actually be used to reduce the search
>> space considerably.
> I'm really happy to see that there is at least 3 people if not more
> interested in the exercise of seeing how to encode uses constraints to SAT.
> How do you guys want to get moving on this?
> Peter, would you happen to still have what you had done?
>
>
>>
>> From an API level I do not think there is a big deal. The resolver could
>> just fetch all resources at start. It can of course only return a single
>> solution. This might be unfortunate but I find it hard to see why that is a
>> limitation since any solution that satisfies all requirements should be ok.
>>
>> Kind regards,
>>
>> Peter Kriens
>>
>>
>>
>>> On 17 nov. 2016, at 14:41, Thomas Watson <[email protected]
>>> <mailto:[email protected]>> wrote:
>>>
>>> I will be interested to see if you can successfully map the OSGi uses
>>> concept into the SAT solver p2 uses. I briefly looked at that a long time
>>> ago when we were refactoring the Equinox framework (Luna) and were
>>> replacing the old Equinox resolver. It was far from obvious how you would
>>> achieve this. At that time I opt'ed to collaborate with a common resolver
>>> in Felix for the Equinox framework. But this is no magic implementation.
>>> There are still cases where the OSGi resolver algorithm will blow up. In
>>> Equinox we try to minimize that possibility by avoiding the resolution of
>>> all (10000) bundles at once. But as Pascal states, this does leave out
>>> some possible valid solutions that you will then not discover while
>>> resolving.
>>>
>>> If you do focus on how to map uses into the SAT solver in p2 I would be
>>> interested in collaborating to see if such a resolver would outperform the
>>> Felix resolver we use at runtime. My hope at the time I was looking into
>>> this was to map an OSGi Resolver service on top of the SAT solver
>>> implementation. But I cannot remember how the SAT solver is driven. I
>>> suspect the split between the OSGI Resovler and the OSGi ResolveContext
>>> will not fit well into the SAT implementation model.
>>>
>>> Tom
>>>
>>>
>>>
>>>
>>>
>>> From: Todor Boev <[email protected] <mailto:[email protected]>>
>>> To: Equinox development mailing list <[email protected]
>>> <mailto:[email protected]>>
>>> Date: 11/17/2016 02:22 AM
>>> Subject: Re: [equinox-dev] Convergence between p2 and the OSGi
>>> resolver+repository
>>> Sent by: [email protected]
>>> <mailto:[email protected]>
>>>
>>>
>>>
>>> - Regarding batch resolution:
>>> Ultimately I think the batch processing is about performance. At
>>> provisioning time where finding the best solution trumps speed the resolver
>>> can be executed against the entire set. But I have to try this. After than
>>> the equinox runtime should be able to re-create a correct (maybe not
>>> identical) resolution from the much smaller set of resources. I have tried
>>> the resolver against about 700 bundles and it did okay, but this is well
>>> short of 10,000. More research required....some day.
>>>
>>> - Regarding the additional p2 concepts:
>>> Can you point me to the documentation of how the resolution problem is
>>> converted to a SAT formula?
>>>
>>> Best regards
>>>
>>> On Thu, Nov 17, 2016 at 6:20 AM, Pascal Rapicault <[email protected]
>>> <mailto:[email protected]>> wrote:
>>> On 11/16/2016 10:49 AM, Todor Boev wrote:
>>> - Regarding resolver behavior:
>>> The goal is actually to replace the behavior of the objective function
>>> with the behavior of the resolver. This is the best way to guarantee that
>>> both p2 and the OSGi runtime agree on what is a consistent set of bundles.
>>> For example p2 does not take into account package uses constraints which
>>> leads to p2 selecting bundles that later fail to resolve at runtime. It
>>> does not matter which way to resolve is better, so long as they agree.
>>> Since the OSGi resolver is very unlikely to change it falls on p2 to match
>>> it's behavior. My current company (software ag) has had quite a number of
>>> issues where essentially p2 sets up the resolver to fail.
>>>
>>> - Regarding resolver scalability:
>>> The resolution is split between the resolver which processes the current
>>> set of resources and the resolver context which selects candidates when
>>> asked. If the goal is to support a very high number of candidates - a
>>> resolver context impl optimized for searches in a large candidate space can
>>> be provided. If the goal is to produce a solution that includes a very high
>>> number of resources - more research is required. Even if the initial set is
>>> 10,000 the resolver can be asked to process them not all at once, but
>>> incrementally in batches or even one by one. Which is in fact what equinox
>>> does today.
>>> The thing is that if you look at a subset of the available bundles, you
>>> may find a solution that is not the optimal one. p2 will consider all the
>>> possible candidates in one resolution invocation.
>>>
>>>
>>> I am trying to determine if it makes sense to invest effort in prototyping
>>> this given that subtle changes in behavior are in fact a goal, rather than
>>> an issue.
>>> Even though on the surface p2 resolver looks similar to what the OSGi
>>> resolver does, p2 has at least 2 additional concepts:
>>> 1) the expression of strict negation
>>> 2) the concept of patch
>>>
>>> I'm tempted to think that it is probably simpler to add support for the
>>> uses-clause in p2 (this has been a known issue for years, but I can't seem
>>> to find the bug tonight) than it is to replace the resolver completely and
>>> get all the tests to pass. The encoding of dependencies to a SAT formula is
>>> well documented and so are the optimization functions.
>>>
>>>
>>> On Wed, Nov 16, 2016 at 4:44 AM, Pascal Rapicault <[email protected]
>>> <mailto:[email protected]>> wrote:
>>> On 11/15/2016 12:52 PM, Todor Boev wrote:
>>> Hello,
>>>
>>> Are there any plans to bring together p2 and OSGi resolver+repository
>>> standards?
>>> There is no immediate plan for this.
>>>
>>> It should be beneficial to have similar (maybe identical?) dependency
>>> resolution at provisioning time and later at runtime.
>>> The install time and runtime resolvers resolve a slightly different
>>> problem because the install time resolver has to look for candidates in a
>>> large space, whereas the runtime one has to connect as many components
>>> together.
>>> I have not tried replacing the p2 resolver with the new OSGi resolver
>>> so I can't tell how it would perform.
>>>
>>>
>>> Specifically:
>>> - Is it possible to publish the bundle generic capabilities/requirements to
>>> the p2 repository?
>>> Yes this should be possible. The underlying p2 capability / requirement
>>> model is really extensible and the current limitation is only the
>>> serialized format.
>>>
>>> - Is it possible to use the equinox Resolver inside the p2 Planner?
>>> It is possible to get something going but I'm not sure if this will
>>> scale (p2 resolver is able to perform seamlessly on 10's of thousands of
>>> IUs), nor if you will be able to replicate the subtleties that result from
>>> having an objective function.
>>>
>>> - Even if the equinox Resolver can not be used is it possible for p2 to
>>> handle generic requirements/capabilities?
>>> Yes. This should not be too much work.
>>>
>>>
>>>
>>> Regards,
>>> Todor Boev
>>>
>>>
>>> _______________________________________________
>>> equinox-dev mailing list
>>> [email protected] <mailto:[email protected]>
>>> To change your delivery options, retrieve your password, or unsubscribe
>>> from this list, visit
>>> https://dev.eclipse.org/mailman/listinfo/equinox-dev
>>> <https://dev.eclipse.org/mailman/listinfo/equinox-dev>
>>> _______________________________________________ equinox-dev mailing list
>>> [email protected] <mailto:[email protected]>To change your
>>> delivery options, retrieve your password, or unsubscribe from this list,
>>> visit https://dev.eclipse.org/mailman/listinfo/equinox-dev
>>> <https://dev.eclipse.org/mailman/listinfo/equinox-dev>
>>> _______________________________________________
>>> equinox-dev mailing list
>>> [email protected] <mailto:[email protected]>
>>> To change your delivery options, retrieve your password, or unsubscribe
>>> from this list, visit
>>> https://dev.eclipse.org/mailman/listinfo/equinox-dev
>>> <https://dev.eclipse.org/mailman/listinfo/equinox-dev>
>>>
>>> _______________________________________________
>>> equinox-dev mailing list
>>> [email protected] <mailto:[email protected]>
>>> To change your delivery options, retrieve your password, or unsubscribe
>>> from this list, visit
>>> https://dev.eclipse.org/mailman/listinfo/equinox-dev
>>> <https://dev.eclipse.org/mailman/listinfo/equinox-dev>
>>> _______________________________________________
>>> equinox-dev mailing list
>>> [email protected] <mailto:[email protected]>
>>> To change your delivery options, retrieve your password, or unsubscribe
>>> from this list, visit
>>> https://dev.eclipse.org/mailman/listinfo/equinox-dev
>>> <https://dev.eclipse.org/mailman/listinfo/equinox-dev>
>>>
>>>
>>> _______________________________________________
>>> equinox-dev mailing list
>>> [email protected] <mailto:[email protected]>
>>> To change your delivery options, retrieve your password, or unsubscribe
>>> from this list, visit
>>> https://dev.eclipse.org/mailman/listinfo/equinox-dev
>>> <https://dev.eclipse.org/mailman/listinfo/equinox-dev>
>>
>>
>> _______________________________________________
>> equinox-dev mailing list
>> [email protected] <mailto:[email protected]>
>> To change your delivery options, retrieve your password, or unsubscribe from
>> this list, visit
>> https://dev.eclipse.org/mailman/listinfo/equinox-dev
>> <https://dev.eclipse.org/mailman/listinfo/equinox-dev>
>
> _______________________________________________
> equinox-dev mailing list
> [email protected] <mailto:[email protected]>
> To change your delivery options, retrieve your password, or unsubscribe from
> this list, visit
> https://dev.eclipse.org/mailman/listinfo/equinox-dev
> <https://dev.eclipse.org/mailman/listinfo/equinox-dev>
>
>
> _______________________________________________
> equinox-dev mailing list
> [email protected]
> To change your delivery options, retrieve your password, or unsubscribe from
> this list, visit
> https://dev.eclipse.org/mailman/listinfo/equinox-dev
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ equinox-dev mailing list [email protected] To change your delivery options, retrieve your password, or unsubscribe from this list, visit https://dev.eclipse.org/mailman/listinfo/equinox-dev
