Related Work

Recall from the introduction that the general 
workflow of Version Climbing is this: given a configuration of package-version
pairs of a software system, we want to upgrade certain packages Pupgrade
as much as possible given constraints C on certain packages 
The packages constrained in C may overlap in any arbitrary way
with the packages in Pupgrade.

One step in the workflow is to capture the initial
configuration. Most tools that do that use some version ptrace.
The particular tool we use is ReproZip
http://vgc.poly.edu/~fchirigati/papers/chirigati-tapp2013.pdf, 
though CARE or CDE-SP could
also be used.
These tools find the configuration that was used in the initial
execution, but further software must make explicit the package-versions
that are involved.
We are currently developing those.

The next issue is to discover how much upgrading we can
do of the packages in Pupgrade. 
Many excellent package managers are available such as Debian's Apt (with
front end tool Aptitude), and the P2 tool in Eclipse.
(Le Berre, D., Rapicault, P., 2009. Dependency management for the Eclipse ecosystem,
in: IWOCE 2009: International Workshop on Open Component Ecosystems,
ACM. pp. 21-30.)
Package managers fetch components with particular
versions from remote repositories
and perform the deployment, aborting
if there is a problem. 
Version climber is a tool that searches for configurations satisfying
constraints C to optimize Pugrade. Thus, it could use 
these package managers as components.
The essential novelty of Version climber is that it explores the space
of possible configurations without requiring any a priori information
about package-version compatibilities. 

The project CUDF (Common Upgradeability Description Format) assumes
as given compatibility
dependencies, e.g. P1 version 8 depends on P2 version 18 or above and
P3 version 8 or above etc.
Given those, the system supports the user's being able to
state a request of the form 
Px version greater than  4 and Py version greater than 5.
CUDF is based on theoretical work on dependency solving
in http://www.dicosmo.org/Articles/2012-AbateDiCosmoTreinenZacchiroli-Jss.pdf
CUDF thus has similar objectives and a similar query language
to ours.
The fundamental differences are that

1. CUDF depends on having the CUDF information input by someone
or something. One output of Version Climber could be to produce a CUDF
dependency file, but Version Climber discovers compatibilities
through execution.
Thus, CUDF assumes the pre-existence of
information that Version Climber learns.

2. CUDF might be too conservative in that Pi.vi (package Pi version vi)
might be incompatible with Pj.vj, but only for an obscure reason that
is not relevant to a particular application.
Version Climber finds compatibilities empirically with respect to
the computation of interest (or at least a very similar computation
with perhaps minor changes to data).

Operationally, Version Climber follows a 
generate (package-version configurations)
and test paradigm. There is a long history of such work in large
software development projects using tools like
git bisect
to find logical bugs or performance bugs.
Heger13: https://sdqweb.ipd.kit.edu/publications/pdfs/heger2013a.pdf
https://www.kernel.org/doc/mirror/ols2007v1.pdf#page=93


Because our audience consists of natural scientists who have neither
the desire nor the training to become software developers, we note that our tool
is meant to support an interface in which the user simply
states goals and the system is guaranteed to achieve
the best possible outcome.
In this way, it is completely compatible with good scientific
software practices, urged in for example the paper

Software Carpentry, 10 rules Plos Comp. Biol.
http://journals.plos.org/plosbiology/article?id=10.1371/journal.pbio.1001745

That article recommends that scientists who develop their own
software follow some best practices such as:
writing readable well-formatted programs,
using version control, writing test cases, documenting
and using components as much as possible.
Version Climber requires only the use of components and some version 
control system.
So Version Climber would be a good tool for a would-be software carpenter.