The Paxos algorithm for consensus in a distributed system

http://pine.cs.yale.edu/pinewiki/Paxos

by ColinWright • 14 years ago

95 17 14 years ago

pine.cs.yale.edu

parley• 14 years ago

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. :)

sherwin• 14 years ago

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 :)

luriel• 14 years ago

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

vecter• 14 years ago

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

mwcremer• 14 years ago

loeg2• 14 years ago

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.

argvzero• 14 years ago

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

einarvollset• 14 years ago

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)

DenisM2• 14 years ago

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

iradik• 14 years ago

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

stock_toaster• 14 years ago

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

jackowayed• 14 years ago

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.

zaa• 14 years ago

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

nicolast• 14 years ago

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

The Paxos algorithm for consensus in a distributed system

Related Stories