But, debian packages aren't really made for this directly, as they have their pre/post install/remove scripts. My "hack" was to treat every package as an dpkg --unpack version (i.e. not configured) and then at image "build" time (i.e. each image is really a layer that is a manifest of dependent layers + data created at image build time), we would dpkg --configure --pending all the composed layers (with a bit of magic happening behind the scenes to make dpkg realize that the packages were unpacked but not configured yet).
This mostly worked well, but you could have some ordering issues. A bigger issue is because debian doesn't expect this to happen, it creates encryption at install time (say for ssh), not at first run time. So for example, if one created an ssh daemon image, any instance run from it would have the same key. not a great idea. Of course, its possible to engineer my way out of this (simple case would be to write tooling to recognize these cases and inject it into the created images), but it goes to why a direct conversion from debian packges into layer wasn't a silver bullet solution. I had the thought that perhaps an Ubuntu type approach would work, where some packages are wholesale imported from Debian into Unbutu without any changes but "important" packages ae modified to fit Ubuntu better could work.
As an aside, the 2 papers referenced above were my "job talk" for my post doc at IBM Research, and got me the job. I tried to get support to continue this line of work there, but that never happened (and then my manager left, and I was left working on unrelated cloud stuff for the last 1.5 years there). Of course, this is now important to IBM (see Red Hat purchase).
I wasn't approaching this from the pet/cattle metaphor, so I also gave my system the ability to upgrade instances in place by mark removeding layers as unlinked (i.e. ignored by readdir/lookup), and adding new layers. A big advantage here over traditional package management is that this made upgrades "atomic". For example, when you upgrade libc in the traditional package managed world, your system is temporarily "broken", in the sense that any executable that tries to run in between old libc removal and new libc installation will fail as its not on the file system. However, in the cattle world of containers, this is probably unnecessary complexity.