Reconfiguring a State Machine

This paper describes several methods of reconfiguring a state machine. All but one of them can be fairly easily derived from the basic state-machine reconfiguration method presented in the Paxos paper [122]. We felt that it was worthwhile publishing them because few people seemed to understand the basic method. (The basic method has a parameter α that I took to be 3 in [122] because I stupidly thought that everyone would realize that the 3 could be any positive integer.) The one new algorithm, here called the “brick wall” method, is just sketched. It is described in detail in [172].

This paper was rejected by the 2008 PODC conference. Idit Keidar invited us to submit it as a tutorial to her distributed computing column in SIGACT News.