Home » forums » LtU Forum

Proper Library Versioning no longer NP-Complete

Long time no see. Your inspiring comments in Review NP-complete Library Versioning Problem and especially encouragement like

show us why this needs solving and can't just be avoided

made me think about possible solutions. One of them was the suggested adherence to backward compatibility, however as that is not always possible, I searched more.

As a result I came to idea of complete module repositories. As far as I can tell (and prove) they seem to eliminate the NP-Completeness of the general problem. However I have to admit I am not absolutely sure. This is a new, just born formalization (although I suspected this is the case for a while) and it might be even less consistent than the previous NP-Complete proof. It would not be wise to mix them together. Thus I am starting new thread to isolate your comments from the previous claim.

Please comment on Proper Library Versioning no longer NP-Complete proof. Thanks.

By Jaroslav Tulach at 2009-09-02 08:23 | LtU Forum | previous forum topic | next forum topic | other blogs | 4317 reads

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

I am surprised this has not

I am surprised this has not been studied already! I think that a formal study on repository design is important nowadays.

It will have applications on OSGi repositories, Linux and OpenSolaris distributions, Maven projects, SOA Service Registries and in general on complex applications built on different parts. It could even be used for quality metrics on these repositories.

I haven't had time enough to go through the details, but I think the problem could be modeled either with plain graphs or with hypergraphs (where edges may connect different package+version nodes).

There're important results on hypergraph theory that could then be re-used in the analysis of the problem. As many LtU readers will remember, hypergraph acyclicity is important in database schema design as it ensures that many joins can be performed in polynomial time (see On the Desirability of Acyclic Database Schemes).

Maybe this result could be mapped directly to the structure of repositories, so that a repository that can be modeled as a gamma-acyclic hypergraph can be queried in polinomial time as well.

A formal study and characterization of desirable repository structure would be an important achievement, so I encourage you to keep on working on this!.

Update: a short introduction to yannaki's algorithm that requires no ACM membership.

By vieiro at Wed, 2009-09-02 20:49 | login or register to post comments

Seconded

I'd just like to second this. I've spent a fair amount of time in my career thinking about and dealing with component/module dependency issues. I think it's an insufficiently studied and poorly handled problem, and I've really enjoyed the recent threads on the subject.

By Matt Hellige at Wed, 2009-09-02 21:41 | login or register to post comments

What is a re-export, sorry

What is a re-export, sorry for asking?

Is it when library A uses library B publicly, and the program imports library A and library B? I can see that could lead to version inconsistencies.

The linker could see that the version of library B is different and flag incompatibilities if these are explicit.

By Denis Bredelet -jido at Fri, 2009-09-04 11:47 | login or register to post comments

I had a similar question....

Does uninstalling software count as a re-export?

That is to say, is Export : A -> NullPort

a re-export? In other words, given everything in A, can I force all uses of A to be opaque to the system, and thus logically uninstalled, while not affecting some module B?

This is certainly a scenario in modern .NET GAC Hell. If you've ever tried running a couple of different CTPs side by side, you know what I mean. The frustration is that when uninstalling CTPs you never know whether you're fixing the problem or not.

By Z-Bo at Fri, 2009-09-04 14:53 | login or register to post comments

Public exposure of another API

Yes, it is when library A uses library B publicly, such that if A is loaded then so must a compatible B, and the names in B are exposed to the user of A. Often, this can be avoided. Sometimes, it cannot be wholly avoided... e.g. when A requires inputs described by types in B.

By dmbarbour at Fri, 2009-09-04 16:00 | login or register to post comments