Computer science is full of complex hard-to-understand algorithms. Understandability of an algorithm - ability to explain an algorithm in simple terms - is generally under appreciated. Often poor understandability of an algorithm has a direct impact on practical real-world applications. In my opinion, if we can’t develop intuitions about algorithm it will be very difficult to implement or extend the algorithm for real-world use cases. There are only a few occasions when an algorithm was designed for understandability or influenced by intuition.

In this article, we will be talking about the Raft – a consensus algorithm used in distributed computing. Raft was specifically developed to overcome the challenges posed by Paxos – another consensus algorithm which dominated the distributed computing domain for more than 10 years. Paxos is exceptionally hard to understand. Paxos is so difficult that even seasoned computer science researchers can’t explain it forget about computer science students and engineers. Several people have tried to explain Paxos in more simple language but only after great efforts.

History of Paxos

Paxos protocol was first published by Leslie Lamport in 1989 as a report. It was later published as paper with a title The Part-Time Parliament in journal ACM Transactions on Computer Systems in the year 1998. In this paper, Lamport used a fictional legislative consensus system used by an obscure ancient Paxon civilization to describe Paxos consensus protocol. He also discussed the obvious correspondence between this distributed system and the Paxon Parliament. As editor of the Journal commented,

even though the obscure ancient Paxon civilization he describes is of little interest to most computer scientists, its legislative system is an excellent model for how to implement a distributed computer system in an asynchronous environment. Indeed, some of the refinements the Paxons made to their protocol appear to be unknown in the systems literature.

Even after formal publication, the algorithm was poorly understood by many in computer science community. Eventually, Lamport wrote a simpler version of Paxos Paxos Made Simple in 2001. This was definitely more readable but it still lacked the understandability.