Re:Gryadka is not Paxos, so it's probably wrong
by mjb on Friday March 24, 2017 @02:35PM
(#13951115)
While we're here, it's also not true that all correct consensus protocols are Paxos. For example, Viewstamped Replication is correct, but a different algorithm (see https://arxiv.org/pdf/1309.5671v3.pdf). There's a number of correct algorithms, and they all smell an awful lot like Paxos, but aren't all exactly Paxos. That's the hard part: nearly all Paxos-like algorithms are broken, but not all.
Also from the "variants of Paxos" department is Flexible Paxos (https://blog.acolyer.org/2016/09/27/flexible-paxos-quorum-in...) which changes the rules about how to select a quorum.
Re:Gryadka is not Paxos, so it's probably wrong
by Scaevolus on Friday March 24, 2017 @02:55PM
(#13951282)
EPaxos (essentially leaderless Paxos) is interesting as well, but I'm not sure how much deployment it's seen: https://github.com/efficient/epaxos
The repo includes a TLA+ model too, which will hopefully become a trend in newly proposed distributed systems in the future!
Cassandra looked into implementing it, and reached a prototype implementation with ~60% better performance, but it looks like the contributor didn't continue driving it: https://issues.apache.org/jira/browse/CASSANDRA-6246
Re:Gryadka is not Paxos, so it's probably wrong
by mring33621 on Friday March 24, 2017 @06:06PM
(#13952617)
Five bucks says that 'the contributor' got a job at ScyllaDb.
I think it makes a slightly stronger argument about MultiPaxos than it needs to. There are other correct ways to use single-decree Paxos, as long as you recognize it's limitations. The true limitation is "use every register once", and a log is the gold standard way to do that. Another correct pattern could be a set-only K/V store, or a store for monotonic finite state machine states (at the cost of O(N) rounds for every contender). One real-world example is 2PC coordination, where the state machine is very simple, and can be modeled as an ordered pair of three registers.