Ubuntu - The following packages have been kept back

If you've used Ubuntu for long enough, you'll find that eventually you'll run into a problem when upgrading the installed packages. When running apt-get from the command line, the problem manifests itself as the following:

$ sudo apt-get upgrade
[sudo] password for srdan:
Reading package lists... Done
Building dependency tree      
Reading state information... Done
The following packages have been kept back:
  linux-headers-server linux-image-server linux-server
0 upgraded, 0 newly installed, 0 to remove and 3 not upgrade

The short answer is that you should be able to upgrade by running the "apt-get dist-upgrade" command:

$ sudo apt-get dist-upgrade
Reading package lists... Done
Building dependency tree      
Reading state information... Done
Calculating upgrade... Done
The following NEW packages will be installed:
  linux-headers-3.2.0-27 linux-headers-3.2.0-27-generic linux-image-3.2.0-27-generic
The following packages will be upgraded:
  linux-headers-server linux-image-server linux-server
3 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
Need to get 51.2 MB of archives.
After this operation, 217 MB of additional disk space will be used.
Do you want to continue [Y/n]?

The long answer comes from the man page of the "apt-get" command. In particular, if you look at the description of the "upgrade" argument, two sentences stick out:

"under no circumstances are currently installed packages removed, or packages not already installed retrieved and installed."

"New versions of currently installed packages that cannot be upgraded without changing the install status of another package will be left at their current version."

Because you can't upgrade the "linux-image-server" (a.k.a. the kernel) without upgrading the headers as well (technically you can, but it can lead to serious problems) it won't let you upgrade them using the "upgrade" command. Either that, or the "new" linux image package requires that a "new" linux headers package be installed, violating the requirement that packages not already installed not be installed.

The reason that the "dis-upgrade" command works, where the "upgrade" command does not is that "dist-upgrade" takes into account dependencies between packages. Also from the man page:

"dist-upgrade ... intelligently handles changing dependencies with new versions of packages; apt-get has a 'smart' conflict resolution system, and it will attempt to upgrade the most important packages at the expense of less important ones if necessary."

This does beg the question though as to why not just use "dist-upgrade" all the time or incorporate the conflict resolution system into the "upgrade" command?

I suspect the answer has something to do with how each "edition" of a distribution is defined. i.e. Ubuntu 12.04 will ship with version 3.1.13 of the "at" package and all other packages that are a part of this "edition" should work with that version. Having many different packages depend on specific versions of other packages could end up in a situation where it becomes very difficult to upgrade any individual package.