Stoppable Paxos

A stoppable state machine is one whose execution can be terminated by a special stopping command. Stoppable state machines can be used to implement reconfiguration in a replicated state machine; a reconfigurable state machine is implemented by a sequence of stoppable state machines, each running in a fixed configuration. Stoppable Paxos, a variant of the ordinary Paxos algorithm, implements a replicated stoppable state machine.

This paper contains a complete description and proof of the “brick wall” algorithm that was sketched in [171]. It was rejected from the 2008 DISC conference.