Leslie Lamport, a world renounced computer scientist, first published the paper “Part-time parliament” back in 1990. Unfortunately, that paper well not well received, primarily due to the fact that the consensus protocol was described in the context of obscure ancient Paxos civilization. The paper was not was received among computer scientists and Leslie Lamport followed up by publishing another version of paper titled “Paxos made simple.”
Over the last couple days, I’ve been reading and carefully studying the paper, making (so far) three passes. From the title, you would think that the paper is written such that it could be easily understood by us computer scientists. It’s supposed to be simple, right?
Nope.
In fact, I’m finding it incredibly difficult to conceptualize the consensus protocol, unable to succinctly describe the protocol in my own words. The paper’s title misleads its readers!
Frustrated with my own inability to understand the paper, I set it aside and decided to pick up another (optional) reading assignment prescribed by my distributed systems course, the paper titled “In Search of an Understandable Consensus Algorithm.” After reading the first couple paragraphs, I feel a sense of relief because on the second page, the authors share both my frustration and confusion about PAXOS:
“The first drawback is that Paxos is exceptionally difficult to understand. The full explanation [15] is notoriously opaque; few people succeed in understanding it, and only with great effort. As a result, there have been several attempts to explain Paxos in simpler terms [16, 20, 21]. These explanations focus on the single-decree subset, yet they are still challenging. In an informal survey of attendees at NSDI 2012, we found few people who were comfortable with Paxos, even among seasoned researchers. We struggled with Paxos ourselves; we were not able to understand the complete protocol until after reading several simplified explanations and designing our own alternative protocol, a process that took almost a year”
After realizing that I’m not alone in failing to grok PAXOS, I started searching the internet for other resources that better describe PAXOS. I found a couple great write-ups as well as the “defacto” lecture describing PAXOS:
So, sorry “PAXOS made simple”, it’s not me, it’s you.