The Paxos algorithm for consensus in a distributed system | Hacker News Reader

The Paxos algorithm for consensus in a distributed system

pine.cs.yale.edu

95 pointsColinWright17 comments

Recommended reading: Paxos Made Simple by Leslie Lamport (http://research.microsoft.com/en-us/um/people/lamport/pubs/p...)

    Abstract

    The Paxos algorithm, when presented in plain English, is very simple.

Compare that to the original paper, which is pretty obtuse: http://research.microsoft.com/en-us/um/people/lamport/pubs/l...

I've read both Paxos papers from the parent and grandparent comments. Comparatively, the linked article is succinct, well-written, and (relatively) easy to understand.

Which linked article of the three?

(As he hasn't responded:) I'm guessing he means the article linked by this entire article thread, as opposed to any of the alternatives mentioned by the comments that he responded to.

Yes, I meant the topic article. I have some dog-eared printouts of "Paxos Made Simple" and "Paxos Made Live" lying on my floor.

I can really recommend implementing (and testing) Paxos (and the failure detector Omega mentioned at the end of the linked page) if you're interested in learning distributed systems, message passing-based communication and juggling state machines.

It may look tricky, but once you penetrate the formalities and understand it, you'll love it. It's a nice kick when you get it working.

Edit: Although you may not want to do it in C, as I had to. At the time, I'd have given my left hand for some tuples, pattern matching and other stuff. :)

Funny you mention this -- this was almost exactly what I and a friend did for a final project last semester. we did it in Go, which was probably much more enjoyable than C :)

Funny you mention this, the folks at Heroku did the same: http://blog.golang.org/2011/04/go-at-heroku.html / https://github.com/ha/doozerd

If you're looking to actually implement Paxos, check out "Paxos Made Moderately Complex" by Robert van Renesse: http://www.cs.cornell.edu/courses/cs7412/2011sp/paxos.pdf

Robbert is indeed one of (if not the) smartest men you'll ever meet in relation to fault tolerance in distributed systems. However, if you're looking to build a fault tolerant consensus algorithm, you owe it to yourself to check out randomized consensus (which predates Paxos, and really is the same algorithm - just simpler)

Google search for "randomized consensus" turns up a paper comparing several such algorithms. Which one did you have in mind?

Why isn't there a good open-source paxos implementation out there? Or is there?

https://news.ycombinator.com/item?id=4052123 ?

I think Apache Zookeeper is a Paxos implementation. I've heard very good things about it. Various pieces of Hadoop use it, and I know of people who use it for medium-sized webapps that need a canonical, fault-tolerant configuration system.

Zookeeper uses its own consensus protocol - ZAB (http://wiki.apache.org/hadoop/ZooKeeper/Zab).

http://www.arakoon.org uses (Multi-)Paxos. Version 2.0 in development at https://github.com/Incubaid/arakoon (e.g. see https://github.com/Incubaid/arakoon/blob/2.0/src/hope/mp.ml for the state machine implementation).

Reply on news.ycombinator.com