>> dependencies represent an acyclic graph > AFAICT that's not always true. And you are right. apt-get has "upgrade" and "dist-upgrade" commands for a long, l

>> dependencies represent an acyclic graph > AFAICT that's not always true. And you are right. apt-get has "upgrade" and "dist-upgrade" commands for a long, long time for a reason (the latter allows to upgrade packages in the presence of dependency cycles and some other cases that would be nasty if left in the middle of upgrade; obviously, no changes that need dist-upgrade land in Debian stable).