A More Flexible Paxos
ssougou.blogspot.com
A More Flexible Paxos
1–10 of 23 posts
Re: A More Flexible Paxos
#2Just like the author, I'm no Paxos expert.
However, I see a clear issue with the proposed model.
Taking the authors 11 node set up. 9 nodes are required for leader election. 3 nodes are needed for proposals.
Assume that a network partition splits the nodes with 5 nodes on side A and 6 nodes on side B. Assume also that the leader is on side B (though it works without loss of generality for side A as well).
At this point, no leader re-election can occur, since no side has the 9 total nodes required for a re-election. It's obvious that if the leader dies (or died as part of the partition) that no leader can be re-elected.
With the partition in place:
1.) let 1 node in side A make the proposal "X=3"
2.) Let 2 other nodes in side A agree to the proposal that "X=3"
3.) Let 1 node in the side B make the proposal "X=0"
4.) Let 2 other nodes in side B agree to the proposal that "X=0"
5.) Let the partition heal
6.) The cluster is now split brain on whether "X=0" or "X=3". According to the rule provided, the leader must accept any successful proposal.
Note that this split brain does not even require a network partition. Assume no network partition, and nodes are labeled 0-10. The leader is currently node 10.
1.) Let node 1 propose that "X=4"
2.) Let node 2 propose that "X=5"
3.) Let nodes 3 and 9 agree to the proposal that "X=4"
4.) Let nodes 6 and 8 agree to the proposal that "X=5"
5.) Split brain occurs as the leader has to accept any successful proposal, which includes "X=4" from nodes 1, 3 and 9, and also "X=5" from nodes 2, 6 and 8.
Re: A More Flexible Paxos
#3See Lamport's "Cheap Paxos" and "Vertical Paxos" papers for a treatment of what seems like very similar ideas. Vertical Paxos describes using a 'configuration master' (or, possibly, a larger quorum on a larger jury) to make changes to a smaller jury. The details are a bit subtle, but the PlusCal code in the paper lays things out very clearly.
Also check out Check out Peleg and Wool, "The Availability of Quorum Systems" (it's a bit old-fashioned, but still very interesting) for a thorough discussion of the availability argument (separate from Paxos, but in context of Quorum systems in general).
Re: A More Flexible Paxos
#4Just like the author, I'm no Paxos expert. However, I see a clear issue with the proposed model. Taking the authors 11 node set up. 9 nodes are required for leader election. 3 nodes are needed for proposals. Assume that a network partition splits the nodes with 5 nodes on side A and 6 nodes on side B. Assume also that the leader is on side B (though it works without loss of generality for side A as well). At this poi…
Once you're planning work arounds for the "assume half your servers fail" scenario, I think it's time to admit that eventually, something is going to go down that is not automatically recoverable.
Re: A More Flexible Paxos
#5Just like the author, I'm no Paxos expert. However, I see a clear issue with the proposed model. Taking the authors 11 node set up. 9 nodes are required for leader election. 3 nodes are needed for proposals. Assume that a network partition splits the nodes with 5 nodes on side A and 6 nodes on side B. Assume also that the leader is on side B (though it works without loss of generality for side A as well). At this poi…
The split-brain scenarios you mention cannot occur, since all the proposals have to go through the leader before they are agreed to by any processes.
Moreover, the leaders are lease-based in the author's proposal, so I believe that what he describes correctly solves consensus. However, his proposal doesn't really give much of a resilience improvement over the original Paxos, since the system, in the worst case, tolerates only 2 failures (leader + one more process), same as a 5-process Paxos. Nevertheless, an interesting idea, one that I don't think I've seen elsewhere.
Re: A More Flexible Paxos
#6Just like the author, I'm no Paxos expert. However, I see a clear issue with the proposed model. Taking the authors 11 node set up. 9 nodes are required for leader election. 3 nodes are needed for proposals. Assume that a network partition splits the nodes with 5 nodes on side A and 6 nodes on side B. Assume also that the leader is on side B (though it works without loss of generality for side A as well). At this poi…
Once you're planning work arounds for the "assume half your servers fail" scenario, I think it's time to admit that eventually, something is going to go down that is not automatically recoverable.
The problem is that half the servers failing is indistinguishable from a switch connecting two racks being flaky, or anything else which can lead to half the servers being temporarily disconnected from the others.
Re: A More Flexible Paxos
#7There was some discussion of this post on the raft-dev mailing list the other day: https://groups.google.com/forum/?fromgroups=#!topic/raft-dev...
Re: A More Flexible Paxos
#8Just like the author, I'm no Paxos expert. However, I see a clear issue with the proposed model. Taking the authors 11 node set up. 9 nodes are required for leader election. 3 nodes are needed for proposals. Assume that a network partition splits the nodes with 5 nodes on side A and 6 nodes on side B. Assume also that the leader is on side B (though it works without loss of generality for side A as well). At this poi…
The split-brain scenarios you mention cannot occur, since all the proposals have to go through the leader before they are agreed to by any processes. Moreover, the leaders are lease-based in the author's proposal, so I believe that what he describes correctly solves consensus. However, his proposal doesn't really give much of a resilience improvement over the original Paxos, since the system, in the worst case, toler…
So I'm pretty a similar problem could exist. If to accept a proposal we only need 3 nodes, not a majority, and we manipulate network latency in arbitrarily bad ways, a similar split brain could occur. Basically, you could commit the same transaction twice under different proposal numbers.
Re: A More Flexible Paxos
#9"With systems getting more and more distributed, the Paxos algorithm has been gaining popularity."
Has it though? I feel like many of the new distributed systems I read about are Raft based consensus.
Re: A More Flexible Paxos
#10"With systems getting more and more distributed, the Paxos algorithm has been gaining popularity." Has it though? I feel like many of the new distributed systems I read about are Raft based consensus.
> Has it though?
AFAICT, Yes.
> I feel like many of the new distributed systems I read about are Raft based consensus.
Sure, and Raft has probably been gaining popularity even more than Paxos has. With more and more distributed systems and more attention on guarantees for such systems, its possible for both Paxos and Raft (and perhaps other techniques) to be getting more popular.