Like I said, it's not entirely impossible (a while ago I was using checkrestart on my Debian machine with pretty good results), but the result is still somewhat

Like I said, it's not entirely impossible (a while ago I was using checkrestart on my Debian machine with pretty good results), but the result is still somewhat clunky. There are a lot of things that aren't so easily checked: changes in interpreted code (needrestart can, fortunately, deal with Java, Perl, Python and Ruby, but I don't know how well, and there's no shortage of packages that rely on old-fashioned bash scripts or -- hey, Polkit! -- JavaScript), changes in configuration files and so on. This is a reasonable solution if you're running relatively non-critical processes on a single machine. If you really want to avoid downtime, a cluster with rolling updates seems like a solution with far fewer headaches. Non-critical covers a lot these days, fortunately :-).