Finding beauty in consensus protocols
The peculiar story of the Paxos algorithm, how Leslie Lamport makes complex ideas fun, and academic papers as an interface.
Finding beauty in software is easier when it’s visual - that’s the sense we use the most.
Before we touch anything, before we hear it, we see it. The eye is surprisingly well-trained at recognizing what has good aesthetic qualities.
But in places where the visual aspect is not dominant, or doesn’t exist at all, recognizing beauty takes more than intuitive taste.
There’s nothing less visual than a distributed system, a set of computers attempting to act coherently. The diagrams we make to illustrate such systems are the closest we can get to a visual representation of them, but even they are just abstract projections.
These services don’t exist. They’re not ordered like they are in the diagrams we draw on whiteboards.
What is beauty when it comes to processes?
What’s elegance when it comes to network communication?
Consensus protocols
Distributed systems need to behave like a single organism, and a prerequisite for that is the ability to agree on things like the shape of the data that lives in a database’s replicas.
Consensus is easier to achieve if your means of communication are reliable.
But these systems communicate over an inherently unreliable network, which creates opportunities for data to diverge.
Consensus protocols create rules that help services to communicate and agree on things, even if some of them lag or contradict each other. While many developers told me that Paxos shouldn’t be the first protocol I start reading about, I decided to look for beauty in it.
The part-time parliament
I had heard about the notorious “The Part-Time Parliament” paper before, but never read it myself. I knew it wasn’t the typical academic paper, and the archeological immersion starts from the first sentence.
This submission was recently discovered behind a filing cabinet in the TOCS editorial office. Despite its age, the editor-in-chief felt that it was worth publishing.
It’s a (fictional) story about how the (real) island of Paxos is governed, but it’s so convincingly written that I had to double-check if it’s actually true.
Early in this millennium, the Aegean island of Paxos was a thriving mercantile center. Wealth led to political sophistication, and the Paxons replaced their ancient theocracy with a parliamentary form of government. But trade came before civic duty, and no one in Paxos was willingto devote his life to Parliament
The paper was originally written in 1989, but it wasn’t considered serious enough because of its narrative style, so it took a decade for it to get published.
It’s quite an unusual approach for a computer science paper.
Much of the wisdom we have as a species we pass down through stories and fables, but the academic world usually sticks to more formal language that’s not widely accessible.
The first requirement of the parliamentary protocol was the consistency of ledgers, meaning that no two ledgers could contain contradictory information. If legislator Φισ∂ ρ had the entry 132: Lamps must use only olive oil in his ledger, then no other legislator’s ledger could have a different entry for decree 132.
This writing style allowed Lamport to be precise in the things he wanted to highlight and remain vague where he didn’t. A technical spec would’ve forced him to write out everything.
Writing about a lost civilization allowed me to eliminate uninteresting details and indicate generalizations by saying that some details of the parliamentary protocol had been lost. To carry the image further, I gave a few lectures in the persona of an Indiana-Jones-style archaeologist, replete with Stetson hat and hip flask.
I did something similar when I published Tao of React a few years ago. Many people asked me to show them a boilerplate, some repo with all my principles implemented in it.
But specifics steal from the abstract, and I still refuse to make one.
The narrative abstraction of “The Part-Time Parliament“ is beautifully written. It’s incredibly immersive. But you need to map everything Lamport describes to a computer concept.
I was trying to think of examples with every word I read, and it is a bit difficult.
A messenger could be counted on not to garble messages, but he might forget that he had already delivered a message, and deliver it again. Like the legislators they served, messengers devoted only part of their time to parliamentary duties. A messenger might leave the Chamber to conduct some business—perhaps taking a six-month voyage—before delivering a message. He might even leave forever, in which case the message would never be delivered.
I understand what this means, but I have to jump a few mental hoops to get there.
A few years later, Lamport finally succumbed to industry pressure and wrote a version of his paper called “Paxos Made Simple”, which focused entirely on the algorithm and removed the narrative layer.
I got tired of everyone saying how difficult it was to understand the Paxos algorithm, published in [122]. Although people got so hung up in the pseudo-Greek names that they found the paper hard to understand, the algorithm itself is very simple…The current version is 13 pages long, and contains no formula more complicated than n1 > n2.
This is how the paragraph about messaging which I mentioned before sounds without the Greek narrative:
Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are not corrupted.
Yeah, it’s much simpler.
Apparently, Dijkstra’s “Dining Philosophers” concurrency problem has been an inspiration for Lamport, but Dijkstra’s scope in this problem is more limited, and you need to do less mental mapping when you’re reading.
Paxos’ narrative style just quickly gets out of hand:
After receiving a LastVote(b, v) message from every priest in some majority set Q, priest p initiates a new ballot with number b, quorum Q, and decree d, where d is chosen to satisfy B3. He then records the ballot in the back of his ledger and sends a BeginBallot(b, d) message to every priest in Q.
Once you’re familiar with the algorithm, you can follow through, but again, you need to map every term. I take into account that I’m a bit denser than the intended audience for this work, but if it took a decade to accept it, there might be something to it.
One touch I appreciated is how he added multiple proofs with different parameters for his quorum algorithm, almost as if it were a unit test suite:
Paxos made even simpler
If we strip down the Greek flavor, Paxos comes down to three roles that any service in a distributed system can play (and they can play multiple at the same time):
Proposers - suggest a value
Acceptors - vote on values
Learners - learn what value was chosen
And a simplistic summary of how it works would be:
A proposer picks a value and sends a prepare message to a majority of acceptors. Since two majorities have at least one overlapping member, this means that if we can reach a majority quorum, we can’t have contradictions.
Each acceptor responds whether they agree with that value or they’ve already agreed to a different one. If the acceptor has agreed to something different, they respond with the value they’ve agreed to (this is how services that lag behind learn what they’ve missed).
If the proposer receives a different value from an acceptor instead of an accept message, they propagate that value.
The proposer then sends an accept message to a majority of acceptors, and once each of them commits the value, it is chosen.
The clever thing (and the part that confused me the most) was that if a value was already chosen, any new proposer would discover it when they suggested a new value.
Since they will send accept messages to a majority, at least one of them will have accepted the new value already.
Paxos successors
Historically, Paxos has served as more of an inspiration than a ready-made solution.
Lamport left many engineering decisions open, and different systems answered them differently (Google Chubby, Zookeeper). Two products can be built on a foundation inspired by Paxos, but they can differ greatly in their implementation and be incompatible.
In practice, services need to agree on a sequence of values, not a single one.
There are Multi-Paxos algorithms that build on top of Paxos to support this, and they introduce optimizations like skipping the proposal step if there’s an elected leader.
Raft is another consensus protocol, created by Diego Ongaro and John Ousterhout - the same Ousterhout who wrote “A Philosophy of Software Design”, a book I greatly admire.
At the time of this writing, I haven’t read the Raft paper, but from what I understand, it reduces the complexity by relying on a strong leader and introducing well-defined leader election mechanisms.
In contrast to Paxos, Raft is focused on being understandable.
Even the paper is called “In Search of an Understandable Consensus Algorithm”.
Beauty
These are the stories I love in tech.
After reading excerpts from the Paxos paper, digging through explanations and examples, I’m convinced that this is one of those problems where you can’t have a simple explanation.
The problem is just too complex.
But Lamport made it fun.
There are many moving pieces, many things that could go wrong. It’s an area of computer science that warrants its complexity.
But Lamport’s paper is elegant. It shows mastery. It shows that the author cared about presentation, not just the idea. The paper itself is an interface to the underlying idea.
Raft has what you’d call a serious paper.
It’s not fun, it doesn’t have Greek names or a narrative structure. It has diagrams, bullet points, and empirical studies. It’s a feat of engineering knowledge, but it’s not the kind of paper I’d tell my friends about over coffee.
I tell them about Paxos, though.
People told me not to start with Paxos, but I’m glad I did.
It showed me that the interface matters to people working in distributed systems, too.