\documentclass{sigplanconf}

\usepackage{amsmath}


\begin{document}

\special{papersize=8.5in,11in}
\setlength{\pdfpageheight}{\paperheight}
\setlength{\pdfpagewidth}{\paperwidth}

\conferenceinfo{CONF 'yy}{Month d--d, 20yy, City, ST, Country} 
\copyrightyear{20yy} 
\copyrightdata{978-1-nnnn-nnnn-n/yy/mm} 
\doi{nnnnnnn.nnnnnnn}

\title{Liquid Version Climber: an automated tool for upgrading complex software systems}
%\subtitle{Subtitle Text, if any}

\authorinfo{Christophe Pradal}
           {UMR AGAP, CIRAD and Inria, Montpellier, France}
           {christophe.pradal@cirad.fr}
\authorinfo{Sarah Cohen-Boulakia}
           {Inria, Montpellier, LRI CNRS 8623, U.Paris Sud, France} 
					 {cohen@lri.fr}
\authorinfo{Patrick Valduriez}
           {Inria and LIRMM, Montpellier, France}
           {Patrick.Valduriez@inria.fr}
\authorinfo{Dennis Shasha}
           {Courant Institute, New York University, USA\\Inria and LIRMM, Montpellier, France} 
					 {shasha@cs.nyu.edu}
					
\maketitle

\begin{abstract}
Suppose you are given a software system that is composed of a set of packages each at a particular version. 
You want to update some packages to their most recent versions possible, but you want your software to run after the upgrades, 
thus perhaps entailing changes to the versions of other packages.
One approach is trial and error, but that quickly ends in frustration.
We advocate a provenance-style approach in which tools like {\em ptrace}, {\em reprozip}, {\em pip}, and virtual machines 
combine to enable us to explore 
version combinations of different packages even on a variety of platforms. 
Our approach may, as a beneficial side effect, 
contribute to reproducibility by allowing the replay 
of an experiment from
a given configuration of software and data package-versions 
to work on a new configuration.
Because the space of versions to explore grows exponentially with the number of packages, we have developed a memoizing algorithm that avoids exponential search while guaranteeing an optimum version combination.
We have ideas for more efficient algorithms under certain assumptions.\footnote{
Work and performed within the Institut 
de Biologie Computationnelle (www.ibc-montpellier.fr).
Support for Shasha through an INRIA international chair and 
grants
Work performed within the Institut 
de Biologie Computationnelle (www.ibc-montpellier.fr).
Support for Shasha through an INRIA International Chair and 
the U.S. National Science
Foundation under grants
DBI-0445666,
DBI-0421604,
NSF IOS-0922738,
MCB-0929339,
and
N2010 IOB-0519985 as well as U.S. NIH
2R01GM032877-25A1.
This support is greatly appreciated.
}
\end{abstract}

\section{Introduction}
Software systems are increasingly complex and compositional. This 
is particularly evident in the context 
of free and open source software which may involve very large groups of independently developed packages all evolving at different rates.  End-user scientists use software systems but they have neither the interest nor the technical skill to engage in any of the continuous development practices [Christophe, references] that are currently considered best practices. More likely, they find themselves needing to update some software system (often embedded in a workflow)  whose original developer has left. When they fail, they suffer from what has been called
"workflow analysis decay" \cite{zhao2012workflows} where scientific experiments relying on intertwined packages cannot be executed even only a few months after they have been developed. 

Ideally, such researchers want to create a running systems with some packages/data updated to recent versions. One issue is that updating one package may entail changes in the versions of other packages. One approach to explore
this package-version space can be trial and error among version combinations, 
but that would be unsustainably time-consuming given the number of combinations to be tested. 
The goal of the \textit{Liquid Version Climber} system is to provide an intelligent automation of this version space exploration. 


The remainder of this paper is organized as follows: Section 2 provides a complete motivated example,


\section{Running Example}
[we could extend it to then use it to provide an example of the algorithm and the new optimization of Dennis?
Christophe: feel free to change the name of the software and versions and dependencies.]

Consider a scientist Lucy who has designed a machine learning experiment on image analysis in a given environment represented by  configuration C that uses scikit-learn version V1, scikitimage V2, SciPy version V3, Numpy version V4, and Python version V2. scikit-learn and scikitimage depend on SciPy, both scikit-learn and scipy depend on Numpy, and all packages depend on Python.  Configuration C works, that is, the experiment of Lucie completes to execution with such versions of the scikit-learn, Numpy and Python packages. Now, imagine that a new version of scikit-learn appears (V10) with possibly new features that Lucie is very interested in experimenting with her new data set. Lucie would thus like to upgrade scikit-learn V1 to V10. However, if scikit-learn is modified in isolation (\textit{i.e.}, the other packages remain at the same versions as the versions they have in the initial configuration C), the new configuration will not work because scikit-learn V10 requires a newer version of SciPy which in turn may depend on Numpy and Python. 

Even if release notes (when they are available) provides some dependency information, end-user scientist Lucie should not have to deal with the integration of packages. Instead, some easy-to-use software should figure out which versions to advance to when advancing.
That's what the \textit{Liquid Version Climber } system does.

Building such a system entails achieving several capabilities:
\begin{enumerate}
\item To identify  the packages and versions of the original working configuration C. 

\item To combine and link different versions of the packages from C to form a new configuration C' (a new set of package-versions).

\item To execute such a new configuration C' and to detect where it failed if it fails.

\item To use failure information to find the best possible configuration
as quickly as possible.
\end{enumerate}

\section{Context}
In this section, we provide the main definitions underlying our approach.

\paragraph{Queries.}
Users express queries describing their desires (which packages to upgrade) and constraints (e.g. don't use .0 releases). Queries are of the form: \textit{maximize versions of the following packages P1, P2, P3, ... Pk in that order (so it is more important for the user to maximize P1 than P2 ...)}. 
Constraints may be of the form: Pi should be either version 1, 4, or 5.

\paragraph{Configurations.}
A configuration is a set of package-version pairs.
The initial configuration is the configuration initially used and which works.\\ 

\noindent \textbf{Definition:} Two configurations are equal if they have the same versions for every package.\\ 

\noindent \textbf{Definition:} We say that configuration 
C' = P1.v1', P2.v2', ..., Pk.vk', ..., Pn.vn'
is lexicographically greater ($>$) than
C = P1.v1, P2.v2, ...., Pk.vk, ..., Pn.vn

if either P1.v1' $>$ P1.v1
or (P1.v1' = P1.v1 and P2.v2' $>$ P2.v2)
or ...
or (P1.v1' = P1.v1 and P2.v2' = P2.v2 and ... and Pk-1.vk-1' = Pk-1.vk-1
and Pk.vk' $>$ Pk.vk)\\

\noindent \textbf{Definition:} A configuration "works" if it executes to completion.\\ 

\paragraph{Pushing.}

\noindent \textbf{Definition:} Pushing a package means advancing by one version level.
We distinguish maximization-push from failure-push.
A \textbf{maximization-push} is done for purposes of maximizing the version of
a package (given user preferences) while a \textbf{failure-push} is done for purposes of trying to avoid incompatibilities between package versions.

\paragraph{Assumptions.}
We now introduce a single assumption now to reduce the need to
do an exhaustive (and therefore exponential) 
search in the space of package-versions.
This gives us a polynomial but somewhat expensive algorithm.
With stronger assumptions we can reduce this to linear time.

\textbf{Pairwise/Global compatibility} 
(pairwise compatible implies 
global compatibility):
An execution using configuration
P1.v1, .... , Pn.vn works 
if for all i, j (1 $\leq$ i,j $\leq$ n) Pi.vi is compatible with (can
call any function in)  Pj.vj.

\textbf{Historicity}
Suppose vi $<$ vi' $<$ vi'' and vj $<$ vj' $<$  vj''
and that Pi.vi' works with Pj.vj'
but Pi.vi'' does not work with Pj.vj'.
Then (i) Pi.vi'' will not work with Pj.vj
and (ii) if vi''' $>$  vi'', then Pi.vi''' will not work with Pj.vj'.

\textbf{(to be rephrased but to be said)  Note that with the Historicity assumption (in particular (ii)), we suppose that only major version changes (API versions?) occurs, no version can make work something that didn't work.}
  
\textbf{?Weak Monotonicity?.} If
(i) neither Pi nor Pj has been maximization-pushed and
(ii) Pi.vi calls Pj.vj fails,
then for all x $\geq$ vi and for all y $\leq$ vj
Pi.x will fail on Pj.y.


\textbf{Like in History, this assumption supposes that only API/major versions are considered. I don't understand why the fact that the packages have been maxpushed is important... did you really want to consider this assumption in the "`basic"' version of the algorithm or is it a bad copy-paste on your document and this should have been placed elsewhere?... If only major version changes are considered then I found strong Monotonicity fine...}
 
\paragraph{Problem statement.}
Given a query and an initial configuration, the problem we address is to produce a revised configuration
that is lexicographically maximum and that satisfies the user constraints.

\section{Implementation} 
(liquid virtual machine/tools we use) 
[Copy-pasted from previous emails/ to be updated]

Our implementation uses the following general strategy:
\begin{itemize}

\item When executing the original configuration C, wrap all relevant parts of the execution into a virtual machine.
We call such a virtual machine "frozen" because all its versions are fixed in binary.
We use the Reprozip system for this.

\item  Be able to abstract from a frozen virtual machine into a "liquid"
virtual machine that has no fixed binding to particular versions of packages. From the liquid virtual machine, multiple frozen ones can be built each corresponding to a different configuration.

\item Given a query consisting of packages whose versions should be maximized (in descending order of priority) and constraints on the versions of other packages, find an efficient way to search the space of configurations to satisfy the query.
\end{itemize}

\section{Algorithm} 
We now introduce the LiquidClimber algorithm.
LiquidClimber starts from a configuration that works (for instance, the \textit{original} configuration ).
It assumes that there is some query that maximizes the versions
of some packages (perhaps with constraints) and may have constraints
but no maximization function on other versions.
The result of the algorithm is a revised configuration
that is lexicographically maximum and that satisfies the constraints.
This is under the assumption that the original configuration satisfies
the constraints. If not, then LiquidClimber will return the original configuration.

THE FOLLOWING SHOULD BE MODIFIED GIVEN THE NEW VERSION IN THE WORD DOC
\begin{small}
\begin{verbatim}
current    := package version pairs in the initial 
              configuration
todolist   := packages requiring maximization in 
              descending order of priority
constraints := some constraints on versions of 
               various packages
sourcemap := for each package the versions that 
             exist and satisfy constraints

for each package p in todolist in descending order of priority
      update current to the highest version of p that works 
		# use git binary on sourcemap
       if current has less than last version of p then 
          versionstodo = find all greater versions 
                         of p or major releases in 
                         ascending order of version 
                         number within sourcemap
       for each v in versionstodo in order
       # could be parallelized but then we have to make
       # sure we take lexicographically greatest ret
          temp := current with p set to v # maximization push
          ret := trytomakework(p, temp) 
          if ret is not null then # we've had success
             current:= ret

# adjust temp to make it work
trytomakework(p, temp)
  initialtemp := temp
  while temp doesn't work in the execution of temp
    Find the first call, say from Pi.vi' to Pj.vj', 
    that fails
    Record in memo that Pi.vi' calling Pj.vj' fails
    Form a new version of temp with Pj.vj'' which is 
    the next version above vj' in Pj and for which 
    we don't know from the memo that
    Pi.vi' calling Pj.vj'' will fail.
    if there is no such version vj'' then 
         advance Pi within temp to the next version vi'' 
         for which we don't know from the memo that 
         Pi.vi'' calling Pj.vj' fails
         and start Pj from the version in initialtemp
         if there is neither a version for Pi nor Pj
             return null
             execute temp
  endwhile
  return temp
\end{verbatim}
\end{small}

\section{Experiments}
?

\section{Related Work}
Given a configuration of package-version
pairs of a software system, the general approach of Version Climbing is 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.

The first step in our approach is to capture the initial
configuration. Most tools that do that use some version ptrace.
The particular tool we use is ReproZip \cite{reproziptapp}, 
though CARE \cite{care} or CDE-SP \cite{pham2014auditing} 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 \cite{berre2009dependency}
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) \cite{treinen2009common} 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 \cite{abate2012dependency} CUDF thus has similar objectives and a similar query language
to ours. 
However, there are two fundamental differences between our approach and CUDF. 
First, 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.
Second, 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 \cite{heger2013automated,chen2007keeping}.\\


Last but not least, 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 in the paper \cite{softcarpentry}:
The software carpentry initiative 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.

\section{Conclusion}

\acks

This work has been done funded in part by the Institute of Computational Biology (RecProv Project).

\bibliographystyle{abbrvnat}
\bibliography{bibtapp}
% The bibliography should be embedded for final submission.

%\begin{thebibliography}{}
%\softraggedright
%\end{thebibliography}


\end{document}

