4 ms·
Are there higher throughout versions of Paxos that are not multi-paxos/raft? Closest thing I can think of is Egalitarian Paxos but it's super complex and introd
by jimsimmons 5y ago
Are there higher throughout versions of Paxos that are not multi-paxos/raft? Closest thing I can think of is Egalitarian Paxos but it's super complex and introduces a bunch of other trade offs.
I don't find multi paxos appealing because it feels like a step back from leaderless vanilla paxos. I have been itching to implement a neat consensus protocol that's a cut above the common ones and has better throughout than etcd. Unfortunately I haven't found anything
- dnautics 5y agoTry VSR (Viewstamped replication). Also supposedly Heidi Howard was working on a consensus protocol appropriate for geographically replicated datacenters, which have fast almost always reliable networks intra-datacenter but fallible slow networks inter-datacenter... That sounds amazing to me.
- jimsimmons 5y agoI've come across a few hierarchical consensus protocol papers. AFAIU, you'll gain immensely in terms of local latency but lose in terms of global latency. But yeah, something in this space would be very interesting. For example Kubernetes and nomad deploy multiple container pods per machine. Instead of sending heartbeats from each pod it would make sense to batch heartbeats of all pods in each machine and send a single beat instead.
- hawk_ 5y ago> hierarchical consensus protocol papers do you have any examples handy? would like to explore that direction.
- jimsimmons 5y agohttps://arxiv.org/abs/2004.06215 https://arxiv.org/abs/2004.06215 https://nsl.cs.rpi.edu/nagawiecki_ms_2021.pdf https://nsl.cs.rpi.edu/nagawiecki_ms_2021.pdf
- hawk_ 5y agocheers! i will check these out.
- ryanworl 5y agohttps://mwhittaker.github.io/publications/compartmentalized_paxos.pdf https://mwhittaker.github.io/publications/compartmentalized_... This is both recent enough that you've probably not seen it and extremely relevant to what you're interested in!
- _benedict 5y agoMost of the trade-offs inherent to EPaxos are resolved by Accord[1], the protocol being developed by the Apache Cassandra community (myself included). There's also Tempo[2] and Caesar[3], amongst others, but they retain some of the trade-offs (and introduce their own). All of these protocols are also capable of supporting multi-shard operations, making them a significant advance over MultiPaxos and Raft. [1] https://cwiki.apache.org/confluence/download/attachments/188744725/Accord.pdf https://cwiki.apache.org/confluence/download/attachments/188... [2] https://arxiv.org/abs/2104.01142 https://arxiv.org/abs/2104.01142 [3] https://arxiv.org/abs/1704.03319 https://arxiv.org/abs/1704.03319
- jimsimmons 5y agoDidn't find any benchmarks in the Accord paper. Do you have pointers?
- _benedict 5y agoIt's still under development, this paper proposes it as an enhancement for Cassandra, so benchmarks are a way off. Given its properties it is likely to have similar performance to Tempo and Caesar for consensus (perhaps lower throughput than Tempo but better latency than Caesar). It is not dissimilar to Calvin for multi-shard execution, trading away the NxN sequencing layer (and poor failure properties) for dependency tracking.
- jimsimmons 5y agoPerfect. Will dig through it! I didn't realise leaderless protocols are less robust and the paper sets up the situation quite well.
- _benedict 5y agoThanks, glad to hear it is helpful. Do let me know if you have any feedback, particularly that might help clarify things.