Thanks again for bringing this issue up; it's something that hadn't
occurred to us. Let's see if you can break this one :)
I think a key property we need to maintain is that, even if up to a
bare majority of the old cluster servers are down, and up to a bare
majority of the new cluster servers are down, there must always be at
least one server that is eligible to become leader.
The problem you've pointed out occurs when the only servers with
eligible logs (those that are most up-to-date out of a quorum) stop
themselves from becoming candidates because they're not members of the
latest configurations in their logs.
I think there's two approaches to solving this:
1. You can disallow removed servers (those in the old configuration
that are not also in the new configuration) from having the Cnew log
2. You can allow removed servers to become candidates and leaders,
even when they're not part of their latest configuration.
I think both of these can work, but my proposal uses the second approach.
The first change is that, unlike what we wrote in earlier emails,
servers would continue to campaign to become leaders even if they're
not part of the latest configuration in their logs. So now a removed
server that has the Cnew entry can be elected leader. It just doesn't
count its own vote towards anything, as it's seeking only votes from
the majority of the new configuration at that point.
If a removed server is leader when the Cold,new entry is committed,
then as in the paper, it creates the Cnew log entry and steps down
once that entry is committed. The second change is that now such a
leader would also stop accepting new client requests after appending
the Cnew entry in its log. The reason is that in this situation, you
want the system to transition to a leader in the new configuration
quickly, and if the removed server as leader continues to grow its
log, this biases its log over others (it could then be the only
eligible server again).
If that was clear and precise enough, are you able to poke any holes
in it? I'm also open to any alternative ideas that might be easier to