5 ms·
The Paxos algorithm for consensus in a distributed system
- parley 14y agoI 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 14y agoFunny 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 14y agoFunny you mention this, the folks at Heroku did the same: http://blog.golang.org/2011/04/go-at-heroku.html http://blog.golang.org/2011/04/go-at-heroku.html / https://github.com/ha/doozerd https://github.com/ha/doozerd
- vecter 14y agoRecommended reading: Paxos Made Simple by Leslie Lamport (http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf 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/lamport-paxos.pdf http://research.microsoft.com/en-us/um/people/lamport/pubs/l...
- mwcremer 14y agoSee also "Paxos Made Live" http://www.read.seas.harvard.edu/~kohler/class/08w-dsi/chandra07paxos.pdf http://www.read.seas.harvard.edu/~kohler/class/08w-dsi/chand...
- loeg 14y agoI've read both Paxos papers from the parent and grandparent comments. Comparatively, the linked article is succinct, well-written, and (relatively) easy to understand.
- DenisM 14y agoWhich linked article of the three?
- saurik 14y ago(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.
- loeg 14y agoYes, I meant the topic article. I have some dog-eared printouts of "Paxos Made Simple" and "Paxos Made Live" lying on my floor.
- deleted 14y ago[deleted]
- argvzero 14y agoIf 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 http://www.cs.cornell.edu/courses/cs7412/2011sp/paxos.pdf
- einarvollset 14y agoRobbert 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)
- DenisM 14y agoGoogle search for "randomized consensus" turns up a paper comparing several such algorithms. Which one did you have in mind?
- deleted 14y ago[deleted]
- iradik 14y agoWhy isn't there a good open-source paxos implementation out there? Or is there?
- stock_toaster 14y agohttps://news.ycombinator.com/item?id=4052123 https://news.ycombinator.com/item?id=4052123 ?
- jackowayed 14y agoI 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 14y agoZookeeper uses its own consensus protocol - ZAB (http://wiki.apache.org/hadoop/ZooKeeper/Zab http://wiki.apache.org/hadoop/ZooKeeper/Zab).
- nicolast 14y agohttp://www.arakoon.org http://www.arakoon.org uses (Multi-)Paxos. Version 2.0 in development at https://github.com/Incubaid/arakoon https://github.com/Incubaid/arakoon (e.g. see https://github.com/Incubaid/arakoon/blob/2.0/src/hope/mp.ml https://github.com/Incubaid/arakoon/blob/2.0/src/hope/mp.ml for the state machine implementation).