Using Paxos in dynamic environment

Question

Paxos algorithm can tolerate up to F failures when using 2F + 1 processors. As far as I understand, this algorithm works only with fixed number of processors. Is it possible to use this algorithm in dynamic environment, where nodes can be added and removed dynamicaly?

Answer 1

Yes it is possible, there are even some papers on it. From what I remember I read a bit on how to do it was described here http://research.microsoft.com/pubs/64634/web-dsn-submission.pdf Hope that's what you were asking about. Look for "dynamic paxos".

Answer 2

The Stoppable Paxos paper is a bit easier to understand and permits safe reconfiguration (addition and subtraction of nodes): http://research.microsoft.com/apps/pubs/default.aspx?id=101826

Answer 3

If you have an absolute maximum number of nodes then it should still work. But you'd be left with a situation where your dynamic node count is 6 your maximum is 11, so if 1 node fails you're out of luck (the non-existent nodes are fails by default). If your removing and adding nodes you could restore the state of a node you removed to a node you add to avoid it being counted as a failure.