Following my talk about Optimizing boot time (slides and the raw material now available), we had several discussions along DebConf6 as to how to make parallel booting a real option.
So, Maxy decided to write a small C program called rcpar, that basically has the same functionality of the "shell" concurrency of /etc/init.d/rc, but since it's written in C, it's able to handle the output in a much cleaner way (and it will also handle interactive scripts in the near future).
Darcs repository: http://maxy.com.ar/~maxy/darcs/rcpar
I will probably be uploading an rcpar package to Debian experimental this weekend.