how about we use consensus to queue restarts? here's the idea:
A new transaction, call it NodeRestart. A validator submits a NodeRestart txn when it wants to restart. Parameters include a start and end ledger sequence. The meaning is that if a validator's NodeRestart txn is accepted and wins (more on that later), then it promises to shutdown after it validates the start sequence and to return before the end sequence. Other honest validators try to avoid restarting in that window.
Most of the network doesn't care about these txns, so they don't have to be part of the ledger. They get a separate section in proposals. They update a separate shared state. The validators apply these txns to their copy of that state; all other nodes just ignore the txns.
NodeRestart txns signed by anyone outside your UNL are dropped. You propose NodeRestart txns signed by someone outside your UNL only if they appeared in a proposal from a node in your UNL.
Within a transaction set, there may be multiple (and possibly conflicting) NodeRestart txns. We can have deterministic rules to decide which ones are applied. The rest are ignored and have to be retried.
To keep a malicious node from holding up the queue, we can have a rate limit as part of the shared state, e.g. your NodeRestart txn is ignored if it is within X ledger sequences of your last NodeRestart txn. Further, we need a cap on the size of the window.