[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: SAT based britney - formalisation of the problem


there seems to be no urgend need for this system, hence we can take the
time to collect more ideas and vary the design a bit:

Am Mittwoch, den 29.06.2011, 17:55 +0200 schrieb Ralf Treinen:
> The important question here would be to define what are precisely the
> "interesting" installation requests. Candidates are:
> - install one arbitrary single package A. This seems to be the definition
>   currently used in britney.
> - install an arbitray *set* of packages together. This might be interesting
>   in some cases, but seems to be too restrictive.

this is in interesting idea. Looking at each installable subset in
testing and enforcing its installability after the migration sounds far
too complex, but it leads to this (not fully thought through) ansatz¹ to
be able to fully support Conflicts.

The idea is to look at a partition of testing into installable subsets
(or a covering by installable subsets). Assume we find such a partition,
and their number is low (for some value of low). Then we can generate a
PMAX-SAT instance that ensures that after transition, the same subsets
are still co-installable.

This could be explained less formally this way: We assume we have a
(small) number of exemplary machines that run Testing, such that every
package is installed on at least one of the machines. After the
migration, each of these machines can fully upgrade to the new testing.

The effect would be, for example, that for each MTA we have a different
subset. All of Haskell, on the other side, can reside in one such

This way, a migration as found by the tool would always ensure
installability in testing (as installability of the “machines” ensures
installability of each individual package). This is an improvement over
the previous idea of ignoring some Conflicts. The downside is that a
transition might be prevented that would be allowed previously, most
notable if a Conflict in introduced by new versions of A and B which are
in in the same set. In that case, this fact needs to be made explicit by
the tool and then the release team can look at the conflict and say:
„This conflict may be in testing.“ Then the system would choose a
different partition with A and B in different sets to start with and the
Conflict would not prevent the migration any more. Once A and B are in
testing, they ensure that a proper partition is chosen and the manual
interaction can be forgotten.

The handling of new packages needs to be addressed as well.

In effect, the SAT problem would solve a distcheck-problem per each
“machine” × each arch, in addition to the migration-related constraints
connecting these. Whether this is still feasible performancewise is not
clear. Also it is not clear whether it is better to have smaller or
larger (and fewer) sets, or maybe one very large for everything
non-conflicting and a few small ones for conflicting stuff.


¹ I’m on a train, so no dict.leo.org available. Plus, I sometimes do
read “ansatz” in English literature. Might have been from the beginning
of the last century, though :-)

Joachim "nomeata" Breitner
Debian Developer
  nomeata@debian.org | ICQ# 74513189 | GPG-Keyid: 4743206C
  JID: nomeata@joachim-breitner.de | http://people.debian.org/~nomeata

Attachment: signature.asc
Description: This is a digitally signed message part

Reply to: