We introduce a class of Paxos algorithms called Vertical Paxos, in which
reconfiguration can occur in the middle of reaching agreement on an
individual state-machine command. Vertical Paxos algorithms
use an auxiliary configuration master that facilitates agreement on reconfiguration. A special case of these algorithms leads to traditional
primary-backup protocols. We show how primary-backup systems in
current use can be viewed, and shown to be correct, as instances of
Vertical Paxos algorithms.