This is missing what to me is the most important part of the algorithm: a quorum of acceptors must propagate writes to the learners. With just what's shown here, you're not tolerant to network partitions that cause a subset of the "accept" messages to be lost.<p>That process can of course be optimized in a number of ways that drastically cut down on the network overhead as compared to the naive MxN write pattern, but what's written here is not safe on its own.
I realize this is pseudocode, but I still feel like the bigger challenge is not in implementing a theoretically correct Paxos, but a production-ready one. It's probably pretty well-known the Chubby[1] team's experiences dealing with unexpected complexity from using Paxos in production.<p>A choice quote: "While Paxos can be described with a page of pseudo-code, our complete implementation contains several thousand lines of C++ code."<p>1: <a href="https://static.googleusercontent.com/media/research.google.com/en//archive/paxos_made_live.pdf" rel="nofollow">https://static.googleusercontent.com/media/research.google.c...</a>
<p><pre><code> 1 proposer(v):
2 while not decided:
2 choose n, unique and higher than any n seen so far
</code></pre>
26 lines.<p>It's pseudocode, so not really only 26 lines as it needs some more supporting functions to "choose n, unique and..." and other stuff to make setting variable states atomic.<p>Good way to explain the algo though.
Curiously, Paxos takes exactly as many lines as a self contained interpreter for a pure functional programming language, written in C :-)<p><a href="http://www.ioccc.org/2012/tromp/tromp.c" rel="nofollow">http://www.ioccc.org/2012/tromp/tromp.c</a><p><a href="http://www.ioccc.org/2012/tromp/hint.html" rel="nofollow">http://www.ioccc.org/2012/tromp/hint.html</a>
For me this shows the difference between theoretical setting and what you would want to do in practice. I have been following 6.824 (where this is sourced from), to learn something about distributed systems programming and it was great fun to shed a lot of figurative sweat to convert those 26 (actually) lines into working "production" code. Hundreds lines of code, because in real-life we have packet loss, network partitions, etc. But the pseudo-code in the link itself is correct, however, it doesn't tell the whole story.<p>Now I am repeating that experience, as Akka project contributor ( <a href="http://akka.io/news/2017/03/17/akka-2.5.0-RC1-released.html" rel="nofollow">http://akka.io/news/2017/03/17/akka-2.5.0-RC1-released.html</a> ) on getting delta-CRDTs into Akka. And again - what was a few lines of pseudo-code in the original paper, or even tens of lines of real code but in some ideal setting ( <a href="https://github.com/CBaquero/delta-enabled-crdts" rel="nofollow">https://github.com/CBaquero/delta-enabled-crdts</a> ) is becoming literally thousands lines of "production grade" code.<p>Finally - I wholeheartedly recommend the 6.824 course to anyone interested in distributed systems. Even if you don't like strong consistency, you'll learn a lot about testing and debugging distributed systems, the knowledge you can re-use later in your career.
Here's a version I wrote in C++ for ScalienDB about 5-6 years ago, this startup has since folded so it's dead code:<p><a href="https://github.com/scalien/scaliendb/tree/master/src/Framework/Replication" rel="nofollow">https://github.com/scalien/scaliendb/tree/master/src/Framewo...</a><p>Paxos: for replicating data<p>PaxosLease: for negotiating a lease, eg. leader<p>Quorum: pluggable "majority" rules, not that important<p>ReplicatedLog: use Paxos for each append, initiated by leader
everyone, please, read the following blog post before using any 'wow!'s in your next exclamation:<p>RAFT Explained – Part 1/3: Introduction to the Consensus Problem <a href="http://container-solutions.com/raft-explained-part-1-the-consenus-problem/" rel="nofollow">http://container-solutions.com/raft-explained-part-1-the-con...</a><p>"While Paxos can be described with a page of pseudo-code, our complete implementation contains several thousand lines of C++ code."
I miss numbed code, cba scrolling up to a line and doing: end, return, space space, delete, enter, mouse, space space, end.<p>just type 8.5: code here<p>(float to insert between lines)<p>also no nesting.<p>then run a processor like go-fmt that checks the format for you.<p>and use the directory structure for class and methods, directory is a class, and a filename is a method.
Or if you're interested in the opposite of pseudocode, here's a TLA+ spec for Paxos.<p>Related to yesterday's TLA+ video post <a href="https://news.ycombinator.com/item?id=13918648" rel="nofollow">https://news.ycombinator.com/item?id=13918648</a>
This is what I mean when I tend to say that all scientific papers should have a minimal reproducable working sample with instructions attached.
Lets say I am interested in dam building with turbines and all its glory: One would assume that this is really complex cross cutting tech, but I still firmly believe that if you cant show me how to build a tiny sample dam that powers my mobile phone or my computer, you havent done your part to make your theory sufficiently reproduceable.