Distributed Consensus

shachaf.net

59 points·luu··5 comments

There are actually 2 equivalent problems, (voting) consensus and total order broadcast and solving one directly leading to solve the other.

It's quite difficult to do (voting) consensus like traditional Paxos correctly and quickly in the face of failures. Therefore, most systems (Raft, Zab, Multi-Paxos) aim to do total order broadcast instead, using a leader to sequence all operations and only fall back to (voting) consensus when total order broadcast is not feasible, like during leader election.

The perspective I have in the post is that Multi-Paxos and Raft and so on are still doing pretty much exactly consensus for each log entry, they're just sharing lock IDs/ballots/terms across multiple log entries, and having the leader reuse the first phase -- acquiring the lock, reading the existing state -- across multiple instances of the second phase -- writing with the lock.

I think this is compatible with what you're saying, but maybe makes them seem more similar than treating them as two different problems.

That's a really nice article! Seeing Paxos from different angles always interest me. I wrote an article about the message flow in Fast-Paxos: https://fadhil.id/blogs/posts/fast-paxos/

My article also mentions the trick of leader with lockID=0 and consecutive lockID used in Fast-Paxos.

Shameless plug for my educational focused Paxos implementation: https://github.com/danrl/skinny

Easy to follow talk teaching Paxos: https://youtu.be/nyNCSM4vGF4

I’m taking a graduate course on Distributed Systems next semester! Excited to get into this in more depth. Thanks for the post!

Reply on news.ycombinator.com