Analysis of the Raft Consensus Protocol

This is an idea proposed in 2012 as a Cambridge Computer Science Part II project, and has been completed by Heidi Howard.

The Paxos algorithm, despite being synonymous with distributed consensus for a decade, is famously difficult to reason about and implement due to its non-intuitive approach and underspecification. In response, this project aimed to implement and evaluate a framework for constructing fault-tolerant applications, utilising the recently proposed Raft algorithm for distributed consensus. Constructing a simulation framework for our implementation would enable us to evaluate the protocol on everything from understandability and efficiency to correctness and performance in diverse network environments.

In retrospect, the complexity of the project far exceeded initial expectations: reproducing research from a paper that was still under submission and was modified regularly proved a big challenge alongside Raft's many subtleties. Nevertheless, the project achieved optoinal extensions by using our work to propose a range of optimisations to the Raft protocol. The project successfully conducted a thorough analysis of the protocol and released to the community a testbed for developing further optimisations and investigating optimal protocol parameters for real-world deployments.

Related Reading

• In Search of an Understandable Consensus Algorithm, Diego Ongaro and John Ousterhout
• Real World OCaml: Functional Programming for the Masses

Links

The dissertation is available as UCAM-CL-TR-857 in the Cambridge Computer Laboratory technical report series. Heidi Howard continued work on Raft subsequent to submitting this project and published it later in the year as Raft Refloated: Do We Have Consensus?.

You can watch Heidi Howard talk about her work in a Computerphile video from 2016:

Heidi Howard also continued to work on Raft and distributed consensus later: