A Review of Consensus Protocols
thomasvilhena.com
thomasvilhena.com
It appears the fantastic Virtual Synchrony wiki page has been unfortunately deleted, and simply replaced with a redirect to a couple sentences on the reliable multicast page (despite not relying on reliable multicast any more than Paxos does) so here's an archive.org capture of the wiki page. https://web.archive.org/web/20181231000827/https://en.wikipe...
Can you point to off the shelf Paxos libraries that both have a focus on mixing strengths of consensus as a first class concept and have been used in extremely high availability circumstances?
whether or not that's a useful place to draw the line: I dunno. wikipedia is what it is with that line, it's hard to say if it's a cause or in spite of it without competition.
And now it's been distilled down to the point of being both inaccurate and difficult to find.
B) It was much smaller than the Paxos page. Should we go delete what exists there too?
As to the paxos page: yeah, that looks like the thing they fairly continuously delete, despite its usefulness. There are other ways and other places to have that kind of information. Wikipedia does not seem to desire to be that location, though it'll happily be a terser summary and link to it.
https://vadosware.io/post/paxosmon-gotta-concensus-them-all/
No implementations/code but if you've ever wondered what the rest of the research landscape looks like for the paxos family tree of coordination (there's also some mention of stuff like SWIM[0], aka batched & randomized gossip at the end as well)
[0]: https://research.cs.cornell.edu/projects/Quicksilver/public_...
Here's a nice paper on this that dives deeper into the matter and also shows how Paxos can be just as "understandable" as Raft with a few vocabulary changes: https://arxiv.org/pdf/2004.05074.pdf
A more recent development is Heidi Howard's work, which provides a framework for thinking about the whole category of Paxos algorithms that many of us find a lot more approachable.
Glad someone has mentioned her here. This talk helped me greatly https://www.youtube.com/watch?v=KTHOwgpMIiU.
[1]: https://dcl.epfl.ch/site/_media/education/sdc_byzconsensus.p...
Anyways, I love all the byzantine stuff but very little of it is actually practical or fast.
http://zoo.cs.yale.edu/classes/cs426/2012/bib/castro02practi...
protected override void Propose(Instance r)
{
proposalNumber = minNumber + 1;
Broadcast(r, MessageType.Propose, proposalNumber);
}If you were to divide the ballot number space, in the event that the owner of the highest values in that space won, every other proposer would immediately need to increase their ballot numbers for all future rounds and so on and so forth or else they would always get rejected.
Recovery path needs to identify if there was a chosen value only from F+1 nodes (out of 2*F+1 nodes total).
When two proposers with same proposal-number, but different values have partially executed the protocol before the crash, then you would end up with all F+1 nodes with same proposal number indicating successful consensus previously, but with divergent values.
Proposer-A received Phase2 votes from nodes n_1,...n_f and Proposer-B received one vote from n_f+1 when power is off and other nodes n_f+2, n_f+3...n_2f+1 don't know anything about the Phase2.
Now, consider the case when power is back and only the first F+1 nodes came back online. System is expected to continue with F+1 live nodes.
Proposer-C now does Phase-1 with the same proposal-number. He is expected to pick the already voted value associated with the max proposal-number from the Phase-1 responses, but there are two different values and he can't determine what to pick.
Maybe read the papers on Paxos, like the "Paxos Made Simple" one, it's not too big (though it's not all that simple either, at least to me...).
Algorithm is not tied to the proposer identity (uuid or fqdn or ip, etc.) The promise in Phase-1 response is not to the proposer, but to the proposal-number.
In your model, proposer cannot change his identity, between Phase-1 and Phase-2 which is not a constraint imposed by the algorithm.
Phase 1.
(a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
(b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.
Important part of the statement is
...with a promise not to accept any more proposals numbered less than n...
But it still should not be an issue, since according to what you quoted an acceptor will not reply to a second proposal that bears the same number ("If an acceptor receives... number n greater than...), which means only one of the two proposers can gather the required majority of promises to move to the next phase, and thus only one of the values can end up being accepted. After the crash you describe, there will be only one accepted value the Proposer-C will receive.