|I’ve got a stupid idea that may (or may not) work:
Using patches for Packages.gz and the rest.
First we need to add a version number (maybe a date in ISO format) to the file.
We find out the differences and create a patch. It is then compressed to get the size down.
apt-get has to be modified so it sends version information about Packages.gz or to retrieve such information from the server. The latter is probably easier (go to the default directory and get all the packages that are named *date-I-want* or get the latest version and patches).
Every so long there would be a full release (kinda kernel one) and the new patches will be based on that one, the old ones being left there for people who do not want to upgrade to the latest and greatest.
Used with the package pools it may also provide with a way to upgrade the system to a known state (let’s say last week program “Y” worked, today it doesn’t. I really do need “Y” so I set my system to be as last weeks).
I hope it sounds clear (it probably won’t) but it is an idea.
If I get the idea completely clear in my mind I will try to patch apt (and die trying :P).