You are viewing...

Learning about Paxos and CASPaxos

Updated on December 14, 2021 at the 17th hour
Posted under:

DISCLAIMER: Expressed views on this blog are my own.

Paxos is regarded as a complicated consensus algorithm much like how Kubernetes is seen as a complicated system. That doesn't mean you should not  be curious and take some learnings and insight from them. I don't shy away from complex algorithms or systems for long though Paxos is one of those algorithms that has eluded me for some time.

I learned about Raft and implemented the leader election part for systems I was building which worked out really well long ago.A log was too heavy for what I required in the past which is why I neglected that portion when I implemented Raft in my system. Hell if I could do it over MySQL was too heavy to be the primary storage system and Web Sockets was an expedient choice. I will recreate the system again in the future likely with Paxos though.

Why Paxos? Well, CASPaxos (or Active Disk Paxos hehe 😉) caught my interest. It is Paxos without a log, which is exactly what I needed for a "leaderless" (or unstable leader for every commit) system. Had I knew about this Paxos I probably would have implemented it over Raft since I like the properties of a leaderless system being that they are highly fault tolerant therefore available.

If I had to learn Paxos today don't know if I would learn about Raft first then learn about Paxos or learn about intro to Paxos, learn about Raft then dig more into Paxos. The easiest way to learn in my opinion though is to have a project (One that will be used in production) that will sufficiently motivate you to learn about these algorithms. Take advantage of the momentum to learn about many things outside of them and put the ideas together to get something novel.


Random Fact: Leslie Lamport came up with the formalization of Paxos while trying to prove Nancy Lynch and Barbara Liskov's research wrong! Ha!

Never heard of them I bet, but they did it without proofs, but you've heard of Leslie Lamport.


Here's an Intro to Paxos.


If you like to think in terms of transactions then this could help https://blog.the-pans.com/understanding-paxos/

This one is a good summarized list of Paxos Variants: https://vadosware.io/post/paxosmon-gotta-concensus-them-all/


While I'll dig into CASPaxos and Paxos more, now why isn't there a KV store that uses CASPaxos yet? Highly available and strongly consistent distributed locks anyone? A great underpinning for a network file system or object store.


There aren't many people in the world who want to work on infrastructure such as a distributed key value store since the techniques can get really crazy and the research quite intense. That said who cares, just do it if you got interest. While I had interest into consensus algorithms and distributed system intensified in college I did not pursue it too much until later when I wanted to figure out leader election and consistent hashing (for the systems I did in the past) even though I felt it daunting to learn.

You just read "Learning about Paxos and CASPaxos". Please share if you liked it!
You can read more recent posts here.