Dynamic Plain Paxos

Abstract. The classic Paxos consensus algorithm requires a static set of 2F+1 processes to tolerate F transient failures. Dynamic Plain Paxos is an extension and a drop-in replacement for the classic Paxos algorithm that allows to change the membership during the reaching of consensus. It satisfies the requirements of the real world systems to replace a permanently failed node or to extend the size of the cluster to tolerate more transient failures.

The article describes a generic way to prove the correctness of paxos-based distributes systems during the change of configuration and uses it to prove the correctness of membership changes.

Article. http://rystsov.info/files/dynamic-plain-paxos.pdf

Please don't read this paper, the proposed solution doesn't fit real world because it reduces node failure tolerance while changing membership, there're algorithms with better operating characteristics (Vertical Paxos, Raft's joint consensus)

But I encourage you to take a look on the Best of both worlds: Raft's joint consensus + Single Decree Paxos post where I described how to apply Raft's joint consensus to Single Decree Paxos (Synod). It's worth reading because some systems don't require the distibuted log abstraction so it's excessive to introduce it just to solve the membership change problem.