Paxos Reconfiguration

Introduction

There have been several approaches to dynamic reconfiguration of consensus algorithms.
Dynamic Paxos (Multi-Paxos that supports reconfig) limits the number of concurrent proposals as a pipeline length parameter $\alpha > 0$, therefore a configuration change chosen at instance $i$ does not take effect until instance $i + \alpha$. Raft protocol supports unbounded pipeline by limiting reconfiguration operations to be only add or remove one node at a time. Vertical Paxos and Egalitarian Paxos employ a separate oracle to manage the configuration [^epaxos]. Zab added a limited-pipeline approach much like Dynamic Paxos [^zab].

Flexible Paxos Reconfiguration

Flexible Paxos generalized Paxos quorums from 

Any two quorums intersect
$$q_1, q_2 \in Q \implies q_1 \cap q_2 \neq \emptyset$$

to
Phase I and Phase II quorums intersect
$$q_1 \in Q^{I}, q_2 \in Q^{II} \implies q_1 \cap q_2 \neq \emptyset$$

Turner [^upaxos] describes the unbounded reconfiguration algorithm for Flexible Paxos.

Let $e \in \mathbb{N}$ denotes the era of a configuration, and $b \in \mathbb{B}$ as the ballot number, $b = \langle e, n, a \rangle$ therefore $\mathbb{B} = \mathbb{N} \times \mathbb{N} \times \mathbb{A}$ ordered lexicographically. The new configuration of the system satisfies
$$Q^{I}_e \cap Q^{II}_{e+1} \neq \emptyset.$$

The first observation is that each new configuration requires a new ballot in phase I that increaments the era part.

[^upaxos]: Turner, David C. "Unbounded Pipelining in Dynamically Reconfigurable Paxos Clusters."
[^epaxos]: Need to verify.
[^zab]: Need to verify.