Extremely fast booting server

I'm changing the way that our DHCP/DNS stuff works at work. Currently we've got 3 DNS servers, and a DHCP box. All of them are VMs.

There's a circular dependency where stuff booting requires NFS, which requires DNS. So when we reboot stuff, things might come back subtly broken until the DNS is up, and we restart some services.

What I want to do is have a few low power servers, probably dual core Atoms or similar, running from SSDs, so that they boot damn fast. I want to make the whole thing boot as near to instantaneously as possible.

Ideally I'd like to use Ubuntu 11.10, or Debian 6 as the OS. I'm not interested in Gentoo or compiling my own kernel. This needs to be reasonably supportable by myself.

Other than SSD drives, what other optimization steps can I take to improve boot speed?

Isn't this a situation where you should engineer around the circular dependencies? Set power-on delays in the server BIOS. You have multiple DNS servers, so that's a plus. DNS caching? Would this be as simple as using IP addresses or host files for your NFS or storage network? You didn't mention the particular virtualization technology, but it's possible to set VM boot priority in VMWare, for instance... Is this across multiple host servers?

Otherwise, SSD-based boot drives can help. Use a distro with Upstart boot processes. Trim down daemons.

Depending on your UPS status, this could be one of the few use-cases where an ACPI hibernate may be a good idea. Generally restore-from-hibernate beats out a boot-from-scratch, especially in the case of low-RAM SSD-based systems. If you have the ability, the 'shutdown' step for your UPS software can be set to hibernate the DNS server.