>  3. More generally, should the history of generations be linear, or
>     should it be a DAG like Git commits?

If the latter is the case, then we can probably use a simple tree.  Here
is a related link: [1].

> Regarding (3), it seems that a linear history not only simplifies the
> implementation, but also the user interface, while covering most
> practical use cases.

I agree.

> Let me illustrate.  Suppose these generations:

>      A ------> B ------> C

> When doing a roll-back from C, one should obviously get back at B.  At
> that point, C would still be available.  Keeping it around means that
> users can easily switch back to C if B turned out to be less appropriate
> (this answers questions (1) and (2)).

> Once at B, installing or removing packages would delete C, thus allowing
> its generation number to be reused, and create a new generation C’ with
> the same generation number as C:

>      A ------> B ------> C’

> At this point, switching back to C is no longer possible.

I like the idea.

Nikita

[1] http://learnyouahaskell.com/zippers#a-very-simple-file-system