Dynamic membership

[seancribbs]

[11:01 AM] Sean Cribbs: there are some challenges around how to stand it up, and how to change membership of the replicas/acceptors/leaders/etc the pseudo-code seems to assume static membership

[11:01 AM] justinsheehy .: membership change is hard, I can talk a bit about that if you want almost all papers on things like that ignore dynamic membership

[11:02 AM] Sean Cribbs: yeah, i'm like "it's just a proposal"

[11:02 AM] justinsheehy .: NOPE

[11:02 AM] Sean Cribbs: worse than that?

[11:02 AM] justinsheehy .: almost, but not quite yeah you can't just bootstrap that way as the definition of an adequate quorum can change at a dangerous time in that case you essentially need to propose that a new epoch, with new membership, should begin nodes that learn about the success of this must make a special promise to no longer make proposals in the prior epoch it's kind of like another layer of the same algorithm so you have to establish a bottom turtle somewhat manually but that's generally okay

[11:05 AM] Sean Cribbs: so… you keep the current epoch as part of the ballots, and then > the acceptors ignore/reject ballots that are not part of that epoch

[11:05 AM] justinsheehy .: right

[11:05 AM] Sean Cribbs: ok, but then the leaders and replicas have to respond specially to the epoch change decision

[11:06 AM] justinsheehy .: correct. they can mostly use the same mechanism, but it's not "just another proposal"

[11:06 AM] Sean Cribbs: gotcha

• [ ] Add membership epochs to appropriate processes
• [ ] Implement membership change proposals
• [ ] Remove actors from state when deciding the change
• [ ] Persist membership somehow

[timgestson]

This project looks to be abandoned, but I don't really think its as complicated as described above to do dynamic membership. Since multi-paxos can concurrently have multiple instances of paxos happening concurrently (multiple slots being decided at once), we would have to cap the number of concurrent instances. We can call that number beta. So if the proposal value for slot 7 is a membership change, we would have to wait for slot 7+beta in order to make that change active. This means that every replica would have to see the membership change. Of course we can pass a bunch of noop proposals to make this change happen in a timely fashion.

[seancribbs]

This was the beginnings of a prototype. riak_ensemble is probably a better implementation.

[rystsov]

Update this thread for those who find it by googling "paxos membership change".

It's possible to apply an idea of Raft's joint consensus to change membership in the middle of reaching agreement on an individual state-machine command (on single decree paxos level). The result is very similar to the Vertical Paxos, please see the details in the post on changing membership in Paxos with Raft's joint consensus.

This approached was used in the TreodeDB.