4 ms·

This is a very good analysis. I think it makes a slightly stronger argument about MultiPaxos than it needs to. There are other correct ways to use single-decre

by mjb 10y ago

This is a very good analysis. 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.

mjb 10y ago
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 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-intersection-revisited/ https://blog.acolyer.org/2016/09/27/flexible-paxos-quorum-in...) which changes the rules about how to select a quorum.
- Scaevolus 10y ago
  EPaxos (essentially leaderless Paxos) is interesting as well, but I'm not sure how much deployment it's seen: https://github.com/efficient/epaxos 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 https://issues.apache.org/jira/browse/CASSANDRA-6246
  - mring33621 10y ago
    Five bucks says that 'the contributor' got a job at ScyllaDb.
    - sulam 10y ago
      Apple, actually.
rystsov 10y ago
It's good but wrong because it's based on a false assumption about how the read operation works. I explained it in the comments.
- tschottdorf 10y ago
  I'm not really on wifi good enough to reply extensively, but I pushed an update to the post explaining this better. If you carry out the read explicitly, you can still get the anomaly in much the same way. I should've done so from the beginning, but I tried to simplify the argument and went too far.

by mjb 10y ago

mjb 10y ago

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 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-intersection-revisited/ https://blog.acolyer.org/2016/09/27/flexible-paxos-quorum-in...) which changes the rules about how to select a quorum.

Scaevolus 10y ago
EPaxos (essentially leaderless Paxos) is interesting as well, but I'm not sure how much deployment it's seen: https://github.com/efficient/epaxos 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 https://issues.apache.org/jira/browse/CASSANDRA-6246
- mring33621 10y ago
  Five bucks says that 'the contributor' got a job at ScyllaDb.
  - sulam 10y ago
    Apple, actually.

rystsov 10y ago

It's good but wrong because it's based on a false assumption about how the read operation works. I explained it in the comments.

tschottdorf 10y ago
I'm not really on wifi good enough to reply extensively, but I pushed an update to the post explaining this better. If you carry out the read explicitly, you can still get the anomaly in much the same way. I should've done so from the beginning, but I tried to simplify the argument and went too far.