In "Part-time Parliament" why does using the membership from decree n-3 work to add or remove members?

Question

Section 3.3.6 of "The Part-Time Parliament" suggests that membership in the parliament (and thus the quorum for decisions) can be changed safely "by letting the membership of Parliament used in passing decree n be specified by the law as of decree n-3".

Translated into more common MultiPaxos terms, that means that the set of acceptors becomes part of the replicated state machine's state, changed by proposals to add or remove acceptors. The quorum for slot N would be taken from the set of acceptors defined in the state when slot N-3 was decided.

Lamport offers no justification for this decision, and while his next paragraph says that changes must be handled with care and describes the ultimate failure of the algorithm, it fails for reasons unrelated to this particular issue.

Is this an adequate safeguard to ensure consistency? If so, what literature supports it?

Answer 1

On further reading of the Paxos slides for the raft user study linked by Michael, I see that my suggestion is close, but in fact every decision needs to be made in a view that is agreed on by all participants. If we choose that view to be that in effect at slot N-1, that limits the whole machine to lock-step: each slot can only be decided once the previous slot has been decided.

However, N-1 can be generalized to N-α, where Lamport sets α=3. As long as all participants agree on α, they agree on the view for each slot, which means that the rest of the algorithm's correctness holds.

This adds a fairly trivial amount of storage overhead, then: leaders must track the view for the most recent slot executed at the replica and the preceding α-1 slots. This is sufficient information to either determine the view for slot N (slot_views[N-α]) or know that the view is undefined (slot N-α or some previous slot is not yet decided) and thus ignore the proposal.

Answer 2

I maintain a Paxos system that is a core component to several large web services. The system runs Basic Paxos, and not Multi-Paxos. In that system changes to the set of acceptors can be proposed like any other transition. The set of acceptors for a paxos instance N is the one that was approved in N-1.

I am unsure if any literature supports this, but it trivial to see that it works. Because Paxos guarantees consensus of the transition N-1, it is guaranteed that hosts agree on which can act as acceptors for transition N.

However, things get a little more complicated with Multi-Paxos and Raft--or any pipelined consensus algorithm. According to the Raft video lecture, this must be a two-phased approach, but I don't recall that he explains why.