Paxos in 25 Lines

nil.csail.mit.edu

49 points·Cieplak··3 comments

I'm fascinated by consensus algorithms and would love to implement one myself to synchronize unreliable systems (e.g. a network of independent sensors with a common database running on ESP8266 modules). I didn't study CS, so I didn't absorb all the underlying theory with my breastmilk. So big questions remain unanswered so far.

How exactly do I know that the algorithm is correct? (Proof, of course, but how?)

How do I know that my implementation is correct? (Unit test, of course, but how? How do I simulate/test asynchronous systems with failing communication? How do I catch all possible edge cases?)

Is there an comparative overview of consensus algorithms detailing pros and cons? (A few days ago there was a post about Paxos/Raft having abmysal worst-case performance.)

The first is a proof published in a paper that you can read. I recall the proof is for single decree paxos. In reality, you need multiple rounds. There are many subtle variations and I am not aware of a proof for that.

Is an implementation correct? Frankly, that is a PhD thesis that is still to have been written. If you want to do a PhD and this topic burns inside you, go for it.

Regarding consensus algorithm overview, no .. not that I know of. Here is a good video on Paxos: https://www.youtube.com/watch?v=JEpsBg0AO6o&t=2545s

Enjoy my friend.

Algorithm correctness: google "tla+"

Implementation correctness: google "jepsen"

Comparative overview: I'm not aware of one, but I'm sure there's one out there. If you find one, post it. Make sure it's very recent because there have been some very significant papers in the last few months.

Reply on news.ycombinator.com