Hacker News Reader

Comment by jimsimmons | Hacker News Reader

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

View on HN

Most 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/188...

[2] https://arxiv.org/abs/2104.01142

[3] https://arxiv.org/abs/1704.03319

Didn't find any benchmarks in the Accord paper. Do you have pointers?

It'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.

Perfect. Will dig through it! I didn't realise leaderless protocols are less robust and the paper sets up the situation quite well.

Thanks, glad to hear it is helpful. Do let me know if you have any feedback, particularly that might help clarify things.

Try 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.

I'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.

> hierarchical consensus protocol papers

do you have any examples handy? would like to explore that direction.

https://arxiv.org/abs/2004.06215

https://nsl.cs.rpi.edu/nagawiecki_ms_2021.pdf

cheers! i will check these out.

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!

Reply on news.ycombinator.com